Convexification techniques for linear complementarity constraints. (English) Zbl 1341.90130
Günlük, Oktay (ed.) et al., Integer programming and combinatoral optimization. 15th international conference, IPCO 2011, New York, NY, USA, June 15–17, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-20806-5/pbk). Lecture Notes in Computer Science 6655, 336-348 (2011).
Summary: We develop convexification techniques for linear programs with linear complementarity constraints (LPCC). In particular, we generalize the reformulation-linearization technique of [H. D. Sherali and W. P. Adams, SIAM J. Discrete Math. 3, No. 3, 411–430 (1990; Zbl 0712.90050)] to complementarity problems and discuss how it reduces to the standard technique for binary mixed-integer programs. Then, we consider a class of complementarity problems that appear in KKT systems and show that its convex hull is that of a binary mixed-integer program. For this class of problems, we study further the case where a single complementarity constraint is imposed and show that all nontrivial facet-defining inequalities can be obtained through a simple cancel-and-relax procedure. We use this result to identify special cases where McCormick inequalities suffice to describe the convex hull and other cases where these inequalities are not sufficient.
For the entire collection see [Zbl 1216.90002].
For the entire collection see [Zbl 1216.90002].
MSC:
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
| 90C05 | Linear programming |
| 90C11 | Mixed integer programming |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
Citations:
Zbl 0712.90050References:
| [1] | Balas, E.: Disjunctive programming: Properties of the convex hull of feasible points. Discrete Applied Mathematics 89(1-3), 3–44 (1998); original manuscript was published as a technical report in 1974 · Zbl 0921.90118 · doi:10.1016/S0166-218X(98)00136-X |
| [2] | Balas, E., Ceria, S., Cornuéjols, G.: A lift-and-project cutting plane algorithm for mixed 0–1 programs. Mathematical Programming 58, 295–324 (1993) · Zbl 0796.90041 · doi:10.1007/BF01581273 |
| [3] | de Farias, I.R., Johnson, E.L., Nemhauser, G.L.: Facets of the complementarity knapsack polytope. Mathematics of Operations Research 27, 210–226 (2002) · Zbl 1082.90586 · doi:10.1287/moor.27.1.210.335 |
| [4] | Ferris, M.C., Pang, J.S.: Engineering and economic applications of complementarity problems. SIAM Review 39, 669–713 (1997) · Zbl 0891.90158 · doi:10.1137/S0036144595285963 |
| [5] | Hu, J., Mitchell, J.E., Pang, J.S., Yu, B.: On linear programs with linear complementarity constraints. Journal of Global Optimization (to appear) · Zbl 1254.90111 · doi:10.1007/s10898-010-9644-3 |
| [6] | Jeroslow, R.G.: Cutting-planes for complementarity constraints. SIAM Journal on Control and Optimization 16(1), 56–62 (1978) · Zbl 0395.90076 · doi:10.1137/0316005 |
| [7] | Rockafellar, R.T.: Convex analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401 · doi:10.1515/9781400873173 |
| [8] | Rockafellar, R.T., Wets, R.J.B.: Variational analysis. A Series of Comprehensive Studies in Mathematics. Springer, Berlin (1998) · Zbl 0888.49001 · doi:10.1007/978-3-642-02431-3 |
| [9] | Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics 3, 411–430 (1990) · Zbl 0712.90050 · doi:10.1137/0403036 |
| [10] | Sherali, H.D., Krishnamurthy, R.S., Al-Khayyal, F.A.: Enumeration approach for linear complementarity problems based on a reformulation-linearization technique. Journal of Optimization Theory and Applications 99, 481–507 (1998) · Zbl 0911.90328 · doi:10.1023/A:1021734613201 |
| [11] | Tawarmalani, M.: Inclusion certificates and disjunctive programming. presented in Operations Research Seminar at GSIA, Carnegie Mellon University (2006) |
| [12] | Tawarmalani, M.: Inclusion certificates and simultaneous convexification of functions. Mathematical Programming (2010) (submitted) |
| [13] | Vandenbussche, D., Nemhauser, G.L.: A polyhedral study of nonconvex quadratic programs with box constraints. Mathematical Programming 102, 531–557 (2005) · Zbl 1137.90009 · doi:10.1007/s10107-004-0549-0 |
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.
