TY  - JOUR
U1  - Wissenschaftlicher Artikel
A1  - Chvátal, Vašek
A1  - Cook, William
A1  - Espinoza, Daniel
T1  - Local cuts for mixed-integer programming
JF  - Mathematical Programming Computation
N2  - A general framework for cutting-plane generation was proposed by Applegate et al. in the context of the traveling salesman problem. The process considers the image of a problem space under a linear mapping, chosen so that a relaxation of the mapped problem can be solved efficiently. Optimization in the mapped space can be used to find a separating hyperplane, if one exists, and via substitution this gives a cutting plane in the original space.We extend this procedure to general mixed-integer programming problems, obtaining a range of possibilities for new sources of cutting planes. Some of these possibilities are explored computationally, both in floating-point arithmetic and in rational arithmetic.
AB  - A general framework for cutting-plane generation was proposed by Applegate et al. in the context of the traveling salesman problem. The process considers the image of a problem space under a linear mapping, chosen so that a relaxation of the mapped problem can be solved efficiently. Optimization in the mapped space can be used to find a separating hyperplane, if one exists, and via substitution this gives a cutting plane in the original space.We extend this procedure to general mixed-integer programming problems, obtaining a range of possibilities for new sources of cutting planes. Some of these possibilities are explored computationally, both in floating-point arithmetic and in rational arithmetic.
KW  - Software
KW  - Theoretical Computer Science
Y1  - 2013
SN  - 1867-2949
SS  - 1867-2949
U6  - https://doi.org/10.1007/s12532-013-0052-9
DO  - https://doi.org/10.1007/s12532-013-0052-9
VL  - 5
IS  - 2
SP  - 171
EP  - 200
S1  - 30
PB  - Springer Science and Business Media LLC
ER  -