Using separation algorithms to generate mixed integer model reformulations (Q1178714): Difference between revisions
From MaRDI portal
Latest revision as of 11:47, 15 May 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Using separation algorithms to generate mixed integer model reformulations |
scientific article |
Statements
Using separation algorithms to generate mixed integer model reformulations (English)
0 references
26 June 1992
0 references
The linear relaxation of mixed integer programming models can be strengthened by introducing auxiliary variables. The author develops a new method for generating auxiliary variable reformulations for problems where the separation algorithm for finding violated cuts can be formulated as a linear program. The results have important consequences for integrality proofs and efficient formulations. Typical examples of the method are graph optimization and fixed charged problems. Computational results for one of the graph optimization problems (a traversal matroid) suggest that the new method is more stable than a conventional cutting plane method in the computational time required.
0 references
model reformulation
0 references
linear relaxation
0 references
auxiliary variables
0 references
separation algorithm
0 references
graph optimization
0 references
traversal matroid
0 references
cutting plane
0 references
0 references
0 references
