Using separation algorithms to generate mixed integer model reformulations. (English) Zbl 0747.90071
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.
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.
Reviewer: H.Kise (Kyoto)
MSC:
| 90C11 | Mixed integer programming |
| 90C35 | Programming involving graphs or networks |
| 90-08 | Computational methods for problems pertaining to operations research and mathematical programming |
Keywords:
model reformulation; linear relaxation; auxiliary variables; separation algorithm; graph optimization; traversal matroid; cutting planeSoftware:
LINDOReferences:
| [1] | Balas, E., Disjunctive programming and a hierarchy of relaxations for discrete optimization problems, SIAM Journal on Algebraic and Discrete Methods, 6, 466-486 (1985) · Zbl 0592.90070 |
| [2] | Balas, E.; Pulleyblank, W., The perfectly matchable subgraph polytope of a bipartite graph, Networks, 13, 486-516 (1983) · Zbl 0525.90069 |
| [3] | Ball, M. O.; Liu, W.; Pulleyblank, W. R., Two terminal Steiner tree polyhedra, (Research Report CORR 87-33 (September 1987), University of Waterloo) |
| [4] | Barahona, F., On cuts and matchings in planar graphs, (Report No. 88503-OR (January 1988), Institute für Operations Research: Institute für Operations Research Bonn) · Zbl 0795.90017 |
| [5] | Barahona, F.; Mahjoub, A. R., On the cut polytope, Mathematical Programming, 36, 157-173 (1986) · Zbl 0616.90058 |
| [6] | Barany, I.; Van Roy, T.; Wolsey, L., Uncapacitated lot-sizing: The convex hull of solutions, Mathematical Programming Study, 22, 32-43 (1984) · Zbl 0551.90068 |
| [7] | Bratley, P.; Fox, B. L.; Schrage, L. E., A Guide to Simulation (1983), Springer: Springer New York · Zbl 0515.68070 |
| [8] | Cook, W., Operations that preserve total dual integrality, Operations Research Letters, 2, 31-35 (1983) · Zbl 0507.65029 |
| [9] | Cunningham, W. H., Minimum cuts, modular functions, and matroid polyhedra, Networks, 15, 205-215 (1985) · Zbl 0581.90059 |
| [10] | Edmonds, J., Submodular functions, matroids, and certain polyhedra, (Guy, R. K.; etal., Combinatorial Structures (1970), Fordon and Breach: Fordon and Breach New York), 69-87 · Zbl 0268.05019 |
| [11] | Edmonds, J.; Giles, R., A min-max relation of submodular functions on graphs, (Hammer, P. L.; etal., Studies in Integer Programming, Annals of Discrete Mathematics, 1 (1977)), 185-204 · Zbl 0373.05040 |
| [12] | Jeroslow, R. G.; Lowe, J. K., Modelling with integer variables, Mathematical Programming Study, 22, 167-184 (1984) · Zbl 0554.90081 |
| [13] | Jeroslow, R. G.; Martin, R. K.; Rardin, R. L.; Wang, J., Gainfree Leontief flows, (Working Paper CC-89-6 (1989), Purdue University) · Zbl 0778.90080 |
| [14] | Nemhauser, G. L.; Wolsey, L. A., Integer and Combinatorial Optimization (1988), Wiley: Wiley New York · Zbl 0469.90052 |
| [15] | Padberg, M. W.; Wolsey, L. A., Trees and cuts, Annals of Discrete Mathematics, 17, 511-517 (1983) · Zbl 0522.90095 |
| [16] | Picard, J.-C.; Queyranne, M., A network flow solution of some non-linear 0-1 programming problems and applications to graph theory, INFOR, 20, 394-422 (1982) · Zbl 0501.90069 |
| [17] | Rardin, R. L.; Choe, U., Tighter relaxations for fixed charge network flow problems, (Report Series No. J-79-18 (May 1979), Georgia Institute of Technology) |
| [18] | Rardin, R. L.; Wolsey, L. A., Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems, (Report (March 1990), Purdue University) · Zbl 0807.90051 |
| [19] | Rhys, J. M.W., A selection problem of shared fixed costs and network flows, Management Science, 17, 200-207 (1970) · Zbl 0203.52505 |
| [20] | Sahinidis, N. V.; Grossmann, I. E., Reformulation of the multiperiod MILP model for capacity expansion of chemical processes, (Report (July 1989), Carnegie Mellon University) · Zbl 0745.90053 |
| [21] | Schrage, L., (User’s Manual for LINDO (1984), Scientific Press: Scientific Press Palo Alto, CA) |
| [22] | Sherali, H. D.; Adams, W. P., A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems (October 1988), Virginia Polytechnic Institute and State University |
| [23] | Van Roy, T.; Wolsey, L., Valid inequalities and separation for uncapacitated fixed charge networks, Operations Research Letters, 4, 105-112 (1985) · Zbl 0575.90045 |
| [24] | Wolsey, L. A., Uncapacitated lot-sizing problems with start-up costs, Operations Research, 37, 741-747 (1989) · Zbl 0696.90021 |
| [25] | Wong, R., A dual ascent approach for Steiner tree problems on a directed graph, Mathematical Programming, 28, 271-287 (1984) · Zbl 0532.90092 |
| [26] | Yannakakis, M., Expressing combinatorial optimization problems by linear programs, (Extended Abstract, ACM Symposium of Theory of Computing (May 3, 1988)), 223-228 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
