Abstract
We consider the problem of generating inequalities that are valid for one-row relaxations of a simplex tableau, with the integrality constraints preserved for one or more non-basic variables. These relaxations are interesting because they can be used to generate cutting planes for general mixed-integer problems. We first consider the case of a single non-basic integer variable. This relaxation is related to a simple knapsack set with two integer variables and two continuous variables. We study its facial structure by rewriting it as a constrained two-row model, and prove that all its facets arise from a finite number of maximal \(\left( \mathbb {Z}\times \mathbb {Z}_+\right) \)-free splits and wedges. The resulting cuts generalize both MIR and 2-step MIR inequalities. Then, we describe an algorithm for enumerating all the maximal \(\left( \mathbb {Z}\times \mathbb {Z}_+\right) \)-free sets corresponding to facet-defining inequalities, and we provide an upper bound on the split rank of those inequalities. Finally, we run computational experiments to compare the strength of wedge cuts against MIR cuts. In our computations, we use the so-called trivial fill-in function to exploit the integrality of more non-basic variables. To that end, we present a practical algorithm for computing the coefficients of this lifting function.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
If f and \(\rho \) are rational numbers, we can compute geometrically a maximal lattice-free set of that form. Specifically, letting \(d \in \mathbb {Z}\) such that \(fd \in \mathbb {Z}\) and \(\rho d \in \mathbb {Z}\), \(g = \gcd (d, \rho d)\) and \(v = \frac{fd}{g} - \left\lfloor \frac{fd}{g}\right\rfloor \), we get the cut \(\frac{g}{d(1-v)} s_2 + \frac{g}{dv} s_3 \ge 1\), provided that \(\frac{fd}{g} \notin \mathbb {Z}\).
References
Agra, A., Constantino, M.F.: Description of 2-integer continuous knapsack polyhedra. Discrete Optim. 3(2), 95–110 (2006). https://doi.org/10.1016/j.disopt.2005.10.008
Agra, A., Constantino, M.F.: Lifting two-integer knapsack inequalities. Math. Program. 109(1), 115–154 (2007). https://doi.org/10.1007/s10107-006-0705-9
Andersen, K., Louveaux, Q., Weismantel, R., Wolsey, L.: Cutting planes from two rows of a simplex tableau (extended version). Working Paper (2006). http://orbi.ulg.ac.be/handle/2268/82794
Andersen, K., Louveaux, Q., Weismantel, R., Wolsey, L.: Inequalities from two rows of a simplex tableau. In: Fischetti, M., Williamson, D. (eds.) Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 4513, pp. 1–15. Springer, Berlin (2007). https://doi.org/10.1007/978-3-540-72792-7_1
Atamtürk, A., Rajan, D.: Valid inequalities for mixed-integer knapsack from two-integer variable restrictions. Research Report BCOL.04.02, IEOR, University of California, Berkeley (December 2004)
Balas, E.: Intersection cuts—a new type of cutting planes for integer programming. Oper. Res. 1(19), 19–39 (1971)
Balas, E., Jeroslow, R.G.: Combinational optimization strengthening cuts for mixed integer programs. Eur. J. Oper. Res. 4(4), 224–234 (1980). https://doi.org/10.1016/0377-2217(80)90106-X
Balas, E., Margot, F.: Generalized intersection cuts and a new cut generating paradigm. Math. Program. (2011). https://doi.org/10.1007/s10107-011-0483-x
Balas, E., Ceria, S., Cornuéjols, G., Natraj, N.R.: Gomory cuts revisited. Oper. Res. Lett. 19, 1–9 (1996)
Basu, A., Campelo, M., Conforti, M., Cornuéjols, G.: On lifting integer variables in minimal inequalities. In: Eisenbrand, F., Shepherd, F.B. (eds.) Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 6080, pp. 85–95. Springer, Berlin (2010). https://doi.org/10.1007/978-3-642-13036-6_7
Basu, A., Conforti, M., Cornuéjols, G., Zambelli, G.: Minimal inequalities for an infinite relaxation of integer programs. SIAM J. Discrete Math. 24(1), 158–168 (2010). https://doi.org/10.1137/090756375
Basu, A., Bonami, P., Cornuéjols, G., Margot, F.: Experiments with two-row cuts from degenerate tableaux. INFORMS J. Comput. 23, 578–590 (2011)
Basu, A., Hildebrand, R., Köppe, M.: Algorithmic and complexity results for cutting planes derived from maximal lattice-free convex sets (2011). https://arxiv.org/abs/1107.5068v1
Borozan, V., Cornuéjols, G.: Minimal valid inequalities for integer constraints. Math. Oper. Res. 34(3), 538–546 (2009). https://doi.org/10.1287/moor.1080.0370
Conforti, M., Cornuéjols, G., Zambelli, G.: A geometric perspective on lifting. Oper. Res. 59, 569–577 (2011). https://doi.org/10.1287/opre.1110.0916
Conforti, M., Cornuéjols, G., Zambelli, G.: Integer Programming. Springer (2014). ISBN 3319110071, 9783319110073
Cook, W.J., Kannan, R., Schrijver, A.: Chvátal closures for mixed integer programming problems. Math. Progr. 47, 155–174 (1990)
Cook, W.J., Hartmann, M., Kannan, R., McDiarmid, C.: On integer points in polyhedra. Combinatorica 12(1), 27–37 (1992). https://doi.org/10.1007/BF01191202
Cornuéjols, G., Margot, F.: On the facets of mixed integer programs with two integer variables and two constraints. Math. Progr. 120(2), 429–456 (2009). https://doi.org/10.1007/s10107-008-0221-1
Dash, S., Günlük, O.: On the strength of gomory mixed-integer cuts as group cuts. Math. Progr. 115(2), 387–407 (2008). https://doi.org/10.1007/s10107-007-0179-4
Dash, S., Goycoolea, M., Günlük, O.: Two-step MIR inequalities for mixed integer programs. INFORMS J. Comput. 22(2), 236–249 (2010). https://doi.org/10.1287/ijoc.1090.0337
Dey, S.S., Wolsey, L.A.: Lifting integer variables in minimal inequalities corresponding to lattice-free triangles. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.), 13th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2008, Bertinoro, Italy, May 26–28, 2008, Proceedings of Lecture Notes in Computer Science, vol. 5035, Springer, pp. 463–475 (2008)
Dey, S.S., Wolsey, L.A.: Constrained infinite group relaxations of MIPs. CORE Discussion Papers 2009033, Université Catholique de Louvain, Center for Operations Research and Econometrics (CORE), (May 2009). URL http://ideas.repec.org/p/cor/louvco/2009033.html
Dey, S.S., Wolsey, L.A.: Two row mixed-integer cuts via lifting. Math. Progr. 124, 143–174 (2010). https://doi.org/10.1007/s10107-010-0362-x
Dey, S.S., Wolsey, L.A.: Composite lifting of group inequalities and an application to two-row mixing inequalities. Discrete Optim. 7(4), 256–268 (2010). https://doi.org/10.1016/j.disopt.2010.06.001
Fischetti M., Saturni, C.: Mixed-integer cuts from cyclic groups. In: Jünger, M., Kaibel, V. (eds.), 11th International IPCO Conference on Integer Programming and Combinatorial Optimization, Berlin, Germany, June 8–10, 2005. Proceedings, pp. 1–11, Springer, Berlin (2005). https://doi.org/10.1007/11496915_1
Fukasawa, R., Günlük, O.: Strengthening lattice-free cuts using non-negativity. Discrete Optim. 8(2), 229–245 (2011). https://doi.org/10.1016/j.disopt.2010.09.002
Fukasawa, R., Goycoolea, M.: On the exact separation of mixed integer knapsack cuts. Math. Progr. 128(1–2), 19–41 (2011). https://doi.org/10.1007/s10107-009-0284-7
Fukasawa, R., Poirrier, L., Xavier, Á.S.: The (not so) trivial lifting in two dimensions (2016). http://www.optimization-online.org/DB_HTML/2016/11/5706.html
Fukasawa, R., Poirrier, L., Xavier, Á.S.: Intersection cuts for single row corner relaxations: source code (January 2018). https://doi.org/10.5281/zenodo.1064310
Gomory, R.E.: An algorithm for the mixed integer problem. Technical Report RM-2597, The Rand Corporation (1960)
Gomory, R.E.: Some polyhedra related to combinatorial problems. Linear Algebra Appl. 2(4), 451–558 (1969). https://doi.org/10.1016/0024-3795(69)90017-2
Gomory, R.E., Johnson, E.L.: Some continuous functions related to corner polyhedra, part II. Math. Progr. 3(1), 359–389 (1972). https://doi.org/10.1007/BF01585008
Gomory, R.E., Johnson, E.L.: Some continuous functions related to corner polyhedra, part I. Math. Progr. 3, 23–85 (1972)
Granlund, T., GMP Development Team: GNU MP: The GNU Multiple Precision Arithmetic Library, 6.1.0 edn (2015). http://gmplib.org/
Harvey, W.: Computing two-dimensional integer hulls. SIAM J. Comput. 28(6), 2285–2299 (1999)
Hirschberg, D.S., Wong, C.K.: A polynomial-time algorithm for the knapsack problem with two variables. J. ACM 23(1), 147–154 (1976). https://doi.org/10.1145/321921.321936
Koch, T., Achterberg, T., Andersen, E., Bastert, O., Berthold, T., Bixby, R.E., Danna, E., Gamrath, G., Gleixner, A.M., Heinz, S., Lodi, A., Mittelmann, H., Ralphs, T., Salvagnin, D., Steffy, D.E., Wolter, K.: MIPLIB 2010. Math. Progr. Comput. 3(2), 103–163 (2011). https://doi.org/10.1007/s12532-011-0025-9
Louveaux, Q., Poirrier, L.: An algorithm for the separation of two-row cuts. Math. Progr. 143(1–2), 111–146 (2014). https://doi.org/10.1007/s10107-012-0597-9
Louveaux, Q., Poirrier, L., Salvagnin, D.: The strength of multi-row models. Math. Progr. Comput. 7(2), 113–148 (2015). https://doi.org/10.1007/s12532-014-0076-9
Lovász, L.: Geometry of numbers and integer programming. Proc. Math. Appl. Jpn. Ser. 6, 177–201 (1989)
Marchand, H., Wolsey, L.A.: Aggregation and mixed integer rounding to solve MIPs. Oper. Res. 49, 2001 (1998)
Nemhauser, G.L., Wolsey, L.A.: A recursive procedure to generate all cuts for 0–1 mixed integer programs. Math. Progr. 46, 379–390 (1990). https://doi.org/10.1007/BF01585752
Acknowledgements
We would like to thank two anonymous referees for valuable suggestions that led to significant improvements to this manuscript. Fukasawa was supported by NSERC Discovery Grant RGPIN 2014-05623. Poirrier and Xavier were supported by Early Researcher Award Grant ER-11-08-174.
Author information
Authors and Affiliations
Corresponding author
Appendices
A Trivial lifting function for S-free sets
In order to simplify the exposition, we examine here the lifting problem in a more general context and adopt the standard approach of the infinite relaxation, as well as its usual notation. We refer the reader to [16] for an introduction.
Let \(S := \mathbb {Z}^m \cap Q\), where Q is some rational polyhedron. Let \(f \in \mathbb {R}^m \setminus S\). We define
and a lifted version of \(R_f\),
We say that a function \(\psi : \mathbb {R}^m \rightarrow \mathbb {R}\) is valid for \(R_f\) if \( \sum _{r \in \mathbb {R}^m} \psi (r) y_r \ge 1 \) for all \(y \in R_f\). We say that \(\psi , \pi : \mathbb {R}^m \rightarrow \mathbb {R}\) is valid for \(M_f\) if \( \sum _{r \in \mathbb {R}^m} \psi (r) y_r + \sum _{r \in \mathbb {R}^m} \pi (r) z_r \ge 1 \) for all \((y, z) \in M_f\). Given \(\psi \) valid for \(R_f\), we say that \(\pi \) is a lifting of \(\psi \) if \((\psi , \pi )\) is valid for \(M_f\). For example, \((\psi , \psi )\) is a lifting of \(\psi \).
Proposition 19
Let \(\psi : \mathbb {R}^m \rightarrow \mathbb {R}\) be valid for \(R_f\). For any \(w : \mathbb {R}^m \rightarrow \mathbb {Z}^m \cap {\text {rec}}({\text {conv}}(S))\), the function \(\pi (r) := \psi (r + w(r))\) is a lifting of \(\psi \).
Proof
For all \((y, z) \in M_f\), we have
Since \(z_r \ge 0\), \(w(r) \in \mathbb {Z}^m\), and \(w(r) \in {\text {rec}}({\text {conv}}(S))\) for all \(r \in \mathbb {R}^m\), we have \(x + \sum _{r \in \mathbb {R}^m} w(r) z_r \in S\) for all \(x \in S\). In particular,
i.e.,
Because \((\psi , \psi )\) is valid for \(M_f\), we know that
for all \((y, z) \in M_f\). In other words, \((\psi , \pi )\) is valid for \(M_f\).
Corollary 20
Let \(\psi : \mathbb {R}^m \rightarrow \mathbb {R}\) be valid for \(R_f\). Then,
is a lifting of \(\psi \).
Proposition 19 only gives sufficient conditions for \(\pi \) to be a lifting function. But if we insist on building \(\pi \) with a formula of the type \(\pi (r) := \psi (r + w(r))\), then in all generality, it is necessary to have \(w \in \mathbb {Z}^m \cap {\text {rec}}({\text {conv}}(S))\). Proposition 21 shows that otherwise, we could construct \(M_f\) such that \(\pi \) is not a lifting.
Proposition 21
Let \(S := \mathbb {Z}^m \cap Q\), where Q is some rational polyhedron, and \(w \notin \mathbb {Z}^m \cap {\text {rec}}({\text {conv}}(S))\). There exist \(f \in \mathbb {R}^m \setminus S\), \(d \in \mathbb {R}^m\) and \(\psi \) valid for \(R_f\) such that if \(\pi (d) = \psi (d + w)\), then \(\pi \) is not a lifting of \(\psi \).
Proof
Since \(w \notin \mathbb {Z}^m \cap {\text {rec}}({\text {conv}}(S))\), there exists \(\bar{x} \in S\) such that \(\bar{x} + w \notin S\). Let \(f := \bar{x} + w\). There exists \(\varepsilon > 0\) such that \(x \notin S\) for all \(x \in \mathbb {R}^m\) such that \(|x - f| \le \varepsilon \). Let \(\psi (r) := \frac{|r|}{\varepsilon }\). It is easy to verify that \(\psi \) is valid for \(R_f\). We construct
Clearly, \(f + \sum _{r \in \mathbb {R}^m} r \bar{y}_r + \sum _{r \in \mathbb {R}^m} r \bar{z}_r = \bar{x}\) so \((\bar{y}_r, \bar{x}_r) \in M_f\). However, we can let \(d := -w\) and verify that
showing that \((\psi , \pi )\) is not valid for \(M_f\).
B Source code
As previously mentioned, the source code for the wedge cut generator presented in Sect. 6 has been made available online [30] under the GNU General Public License, version 3. In this section, we give a brief overview of its structure and usage.
For clarity and reusability, the code has been split into two modules: the module onerow/library contains the code that generates wedge cuts from a given tableau row, as well helper functions that select and extract tableau rows from CPLEX. This module compiles to a shared library, which can be used by other applications. The module onerow/benchmark, on the other hand, contains the code that measures the performance of the library on instances from the MIPLIB, as well as the scripts that convert the raw outputs into the tables presented in Sect. 6. The structure of the project is presented in Table 4. Complete instructions to compile the source code, run the computational experiments and generate the tables have been included in the file README.md.
Next, we describe the main classes of the library module. Given a tableau row, wedge cuts can be generated by making use of the class WedgeCutGenerator, as follows:
A Constraint is composed by a list of rational coefficients and the right-hand side. A Row is a constraint with some extra information, such as reduced costs and the index of the basic variable. Although it is possible to construct a Row manually, the library comes with a helper class CplexHelper which is able to extract it from a CPLEX model:
We recall that only rows with fractional right-hand side and integral basic variable are suitable for generating single-row cuts. The method CplexHelper::find_good_rows can be used for finding such rows. The method CplexHelper::add_cut simplifies adding the generated cut back into the CPLEX model. Before adding the cut, it verifies that the cut dynamism is within the allowed range, that it does cut off the current fractional solution and, optionally, that it does not cut off a given integral solution. Finally, instead of performing each of the previous steps in isolation, the helper class also includes the convenience method CplexHelper::add_single_row_cuts, which combines, in a single call, finding suitable rows, generating the cuts and adding them back into the model. In addition to WedgeCutGenerator, two other single-row cut generators, GomoryCutGenerator and MIRCutGenerator, have been implemented, and can be similarly used with CplexHelper. For more examples of usage, we refer to the unit tests included in the package, under onerow/library/tests.
Rights and permissions
About this article
Cite this article
Fukasawa, R., Poirrier, L. & Xavier, Á.S. Intersection cuts for single row corner relaxations. Math. Prog. Comp. 10, 423–455 (2018). https://doi.org/10.1007/s12532-018-0132-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12532-018-0132-y