×

zbMATH — the first resource for mathematics

Incremental and encoding formulations for mixed integer programming. (English) Zbl 1287.90040
Summary: The standard way to represent a choice between \(n\) alternatives in Mixed Integer Programming is through \(n\) binary variables that add up to one. Unfortunately, this approach commonly leads to unbalanced branch-and-bound trees and diminished solver performance. In this paper, we present an encoding formulation framework that encompasses and expands existing approaches to mitigate this behavior. Through this framework, we generalize the incremental formulation for piecewise linear functions to any finite union of polyhedra with identical recession cones.
Reviewer: Reviewer (Berlin)

MSC:
90C11 Mixed integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adams, W. P.; Henry, S. M., Base-2 expansions for linearizing products of functions of discrete variables, Operations Research, 60, 1477-1490, (2012) · Zbl 1287.90033
[2] Appleget, J. A.; Wood, R. K., (Explicit-Constraint Branching for Solving Mixed-Integer Programs, Operations Research/Computer Science Interfaces Series, vol. 12, (2000), Kluwer), 245-261
[3] Balas, E., On the convex-hull of the union of certain polyhedra, Operations Research Letters, 7, 279-283, (1988) · Zbl 0663.90061
[4] E.M.L. Beale, J.A. Tomlin, Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables, in: OR 69: Proceedings of the Fifth International Conference on Operational Research, pp. 447-454.
[5] Blair, C., Representation for multiple right-hand sides, Mathematical Programming, 49, 1-5, (1990) · Zbl 0717.90100
[6] Bricker, D. L., Reformulation of special ordered sets for implicit enumeration algorithms with applications in nonconvex separable programming, AIIE Transactions, 9, 195-203, (1977)
[7] Cavalcante, C. C.B.; deSouza, C. C.; Savelsbergh, M. W.P.; Wang, Y.; Wolsey, L. A., Scheduling projects with labor constraints, Discrete Applied Mathematics, 112, 27-52, (2001) · Zbl 0984.90012
[8] Dantzig, G. B., On the significance of solving linear-programming problems with some integer variables, Econometrica, 28, 30-44, (1960) · Zbl 0089.16101
[9] Dantzig, G. B., Linear programming and extensions, (1963), Princeton University Press Princeton · Zbl 0108.33103
[10] Geißler, B.; Martin, A.; Morsi, A.; Schewe, L., Using piecewise linear functions for solving minlps, (Lee, J.; Leyffer, S., Mixed Integer Nonlinear Programming, The IMA Volumes in Mathematics and its Applications, vol. 154, (2012), Springer), 287-314 · Zbl 1242.90132
[11] Ibaraki, T., Integer programming formulation of combinatorial optimization problems, Discrete Mathematics, 16, 39-52, (1976) · Zbl 0357.90042
[12] Jeroslow, R. G., A simplification for some disjunctive formulations, European Journal of Operational Research, 36, 116-121, (1988) · Zbl 0647.90055
[13] Jeroslow, R. G.; Lowe, J. K., Modeling with integer variables, Mathematical Programming Studies, 22, 167-184, (1984) · Zbl 0554.90081
[14] Li, H. L.; Lu, H. C., Global optimization for generalized geometric programs with mixed free-sign variables, Operations Research, 57, 701-713, (2009) · Zbl 1226.90078
[15] Lin, E. Y.H.; Bricker, D. L., On the calculation of true and pseudo penalties in multiple choice integer programming, European Journal of Operational Research, 55, 228-236, (1991) · Zbl 0748.90044
[16] Lin, E. Y.H.; Bricker, D. L., Connecting special ordered inequalities and transformation and reformulation technique in multiple choice programming, Computers & Operations Research, 29, 1441-1446, (2002) · Zbl 0994.90106
[17] J.K. Lowe, Modelling with Integer Variables, Ph.D. Thesis, Georgia Institute of Technology, 1984. · Zbl 0554.90081
[18] Luedtke, J.; Ahmed, S.; Nemhauser, G. L., An integer programming approach for linear programs with probabilistic constraints, Mathematical Programming, 122, 247-272, (2010) · Zbl 1184.90115
[19] Markowitz, H.; Manne, A., On the solution of discrete programming problems, Econometrica, 25, 84-110, (1957) · Zbl 0078.34005
[20] Möhring, R. H.; Schulz, A. S.; Stork, F.; Uetz, M., On project scheduling with irregular starting time costs, Operations Research Letters, 28, 149-154, (2001) · Zbl 1027.90040
[21] Ogryczak, W., A note on modeling multiple choice requirements for simple mixed integer programming solvers, Computers & Operations Research, 23, 199-205, (1996) · Zbl 0868.90086
[22] Padberg, M., Approximating separable nonlinear functions via mixed zero-one programs, Operations Research Letters, 27, 1-5, (2000) · Zbl 0960.90065
[23] Padberg, M. W.; Rijal, M. P., (Location, Scheduling, Design and Integer Programming, International Series in Operations Research & Management Science, vol. 3, (1996), Springer)
[24] Ryan, D. M.; Foster, B. A., An integer programming approach to scheduling, (Wren, A., Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling, (1981), North-Holland), 269-280
[25] D.C. Sommer, Computational experience with the ophelie mixed integer code, Talk presented at the International TIMS Conference, Houston, 1972.
[26] C.C. Souza, L.A. Wolsey, Scheduling Projects with Labour Constraints, Relatório Técnico IC-97-22, IC - UNICAMP, 1997.
[27] J.P. Vielma, Mixed integer linear programming formulation techniques, Optimization Online 2012,http://www.optimization-online.org/DB_HTML/2012/07/3539.html.
[28] Vielma, J. P.; Ahmed, S.; Nemhauser, G. L., Mixed-integer models for nonseparable piecewise-linear optimization: unifying framework and extensions, Operations Research, 58, 303-315, (2010) · Zbl 1226.90046
[29] Vielma, J. P.; Ahmed, S.; Nemhauser, G. L., Mixed integer linear programming formulations for probabilistic constraints, Operations Research Letters, 40, 153-158, (2012) · Zbl 1245.90066
[30] Vielma, J. P.; Keha, A. B.; Nemhauser, G. L., Nonconvex, lower semicontinuous piecewise linear optimization, Discrete Optimization, 5, 467-488, (2008) · Zbl 1190.90149
[31] Vielma, J. P.; Nemhauser, G. L., Modeling disjunctive constraints with a logarithmic number of binary variables and constraints, Mathematical Programming, 128, 49-72, (2011) · Zbl 1218.90137
[32] D.L. Wilson, Polyhedral methods for piecewise-linear functions, Ph.D. Thesis, University of Kentucky, Lexington, KY, USA, 1998.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.