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: | Roos C., Terlaky T., Jansen B., Warners J.P. |
Keywords: | combinatorial optimization |
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.