A polytope for a product of real linear functions in 0/1 variables. (English) Zbl 1242.90111
Lee, Jon (ed.) et al., Mixed integer nonlinear programming. Selected papers based on the presentations at the IMA workshop mixed-integer nonlinear optimization: Algorithmic advances and applications, Minneapolis, MN, USA, November 17–21, 2008. New York, NY: Springer (ISBN 978-1-4614-1926-6/hbk; 978-1-4614-1927-3/ebook). The IMA Volumes in Mathematics and its Applications 154, 513-529 (2012).
Summary: In the context of integer programming, we develop a polyhedral method for linearizing a product of a pair of real linear functions in 0/1 variables. As an example, by writing a pair of integer variables in binary expansion, we have a technique for linearizing their product. We give a complete linear description for the resulting polytope, and we provide an efficient algorithm for the separation problem. Along the way to establishing the complete description, we also give a complete description for an extended-variable formulation, and we point out a generalization.
For the entire collection see [Zbl 1230.90005].
For the entire collection see [Zbl 1230.90005].
References:
| [1] | Kim Allemand, Komei Fukuda, Thomas M. Liebling, and Erich Steiner. A polynomial case of unconstrained zero-one quadratic optimization. Math. Program., 91(1, Ser. A):49-52, 2001. · Zbl 1055.90051 |
| [2] | Egon Balas. Projection and lifting in combinatorial optimization. In Computational combinatorial optimization (Schloß Dagstuhl, 2000), Volume 2241 of Lecture Notes in Comput. Sci., pages 26-56. Springer, Berlin, 2001. · Zbl 1052.90061 |
| [3] | Tamas Badics and Endre Boros, Minimization of half-products, Math. Oper. Res., 23, 3, 649-660 (1998) · Zbl 0977.90026 |
| [4] | Balas, Egon; Pulleyblank, William R., The perfectly matchable subgraph polytope of a bipartite graph, Networks, 13, 4, 495-516 (1983) · Zbl 0525.90069 |
| [5] | Balas, Egon; Pulleyblank, William R., The perfectly matchable subgraph polytope of an arbitrary graph, Combinatorica, 9, 4, 321-337 (1989) · Zbl 0723.05087 |
| [6] | Don Coppersmith, Oktay G¨unl¨uk, Jon Lee, and Janny Leung. A polytope for a product of real linear functions in 0/1 variables, 2003. Manuscript, November 2003. · Zbl 1242.90111 |
| [7] | Cheng, Jinliang; Kubiak, Wieslaw, A half-product based approximation scheme for agreeably weighted completion time variance, European J. Oper. Res., 162, 1, 45-54 (2005) · Zbl 1132.90322 |
| [8] | Eranda C¸ ela, Bettina Klinz, and Christophe Meyer. Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem. J. Comb. Optim., 12(3):187-215, 2006. · Zbl 1255.90081 |
| [9] | Don Coppersmith, Jon Lee, and Janny Leung. A polytope for a product of real linear functions in 0/1 variables, 1999. IBM Research Report RC21568, September 1999. |
| [10] | Michel Deza and Monique Laurent. Geometry of cuts and metrics. Springer-Verlag, Berlin, 1997. · Zbl 0885.52001 |
| [11] | Caterina De Simone, The cut polytope and the Boolean quadric polytope, Discrete Math., 79, 1, 71-75 (1989) · Zbl 0683.90068 |
| [12] | Ferrez, Jean-Albert; Fukuda, Komei; Liebling, Thomas M., Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm, European J. Oper. Res., 166, 1, 35-50 (2005) · Zbl 1066.90101 |
| [13] | Martin Gr¨otschel, L´aszl´o Lov´asz, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169-197, 1981. · Zbl 0492.90056 |
| [14] | Martin Gr¨otschel, L´aszl´o Lov´asz, and Alexander Schrijver. Corrigendum to our paper: “The ellipsoid method and its consequences in combinatorial optimization”. Combinatorica, 4(4):291-295, 1984. · Zbl 0555.90080 |
| [15] | Martin Gr¨otschel, L´aszl´o Lov´asz, and Alexander Schrijver. Geometric algorithms and combinatorial optimization. Springer-Verlag, Berlin, second edition, 1993. · Zbl 0837.05001 |
| [16] | Peter L. Hammer, Pierre Hansen, Panos M. Pardalos, and David J. Rader, Jr. Maximizing the product of two linear functions in 0-1 variables. Optimization, 51(3):511-537, 2002. · Zbl 1006.65065 |
| [17] | Alan J. Hoffman and Joseph B. Kruskal. Integral boundary points of convex polyhedra. In Linear inequalities and related systems, pages 223-246. Princeton University Press, Princeton, N. J., 1956. Annals of Mathematics Studies, no. 38. · Zbl 0072.37803 |
| [18] | Adam Janiak, Mikhail Y. Kovalyov, Wieslaw Kubiak, and Frank Werner. Positive half-products and scheduling with controllable processing times. European J. Oper. Res., 165(2):416-422, 2005. · Zbl 1066.90031 |
| [19] | Wieslaw Kubiak, Minimization of ordered, symmetric half-products, Discrete Appl. Math., 146, 3, 287-300 (2005) · Zbl 1084.90030 |
| [20] | Lee, J., In situ column generation for a cutting-stock problem, Computers and Operations Research, 34, 8, 2345-2358 (2007) · Zbl 1149.90187 · doi:10.1016/j.cor.2005.09.007 |
| [21] | George L. Nemhauser and Laurence A. Wolsey. Integer and combinatorial optimization. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons Inc., New York, 1988. A Wiley-Interscience Publication. · Zbl 0652.90067 |
| [22] | ManfredW. Padberg. The Boolean quadric polytope: Some characteristics, facets and relatives. Math. Programming, Ser. B, 45(1):139-172, 1989. · Zbl 0675.90056 |
| [23] | Itamar Pitowsky. Correlation polytopes: their geometry and complexity. Math. Programming, 50(3, (Ser. A)):395-414, 1991. · Zbl 0741.90054 |
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.
