Potential reduction algorithms for structured combinatorial optimization problems

Potential reduction algorithms for structured combinatorial optimization problems

0.00 Avg rating0 Votes
Article ID: iaor19992001
Country: Netherlands
Volume: 21
Issue: 2
Start Page Number: 55
End Page Number: 64
Publication Date: Sep 1997
Journal: Operations Research Letters
Authors: , , ,
Keywords: combinatorial optimization
Abstract:

Recently Karmarkar proposed a potential reduction algorithm for binary feasibility problems. In this paper, a modified potential function that has more attractive properties is introduced. Furthermore, as the main result, for a specific class of binary feasibility problems a concise reformulation as nonconvex quadratic optimization problems is developed. We introduce a potential function to optimize the new model and report on computational experience with the graph coloring problem, comparing the performance of the three potential functions.

Reviews

Required fields are marked *. Your email address will not be published.