Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Relaxations and cutting planes for linear programs with complementarity constraints

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

We study relaxations for linear programs with complementarity constraints, especially instances whose complementary pairs of variables are not independent. Our formulation is based on identifying vertex covers of the conflict graph of the instance and contains the extended formulation obtained from the ERLT introduced by Nguyen, Richard, and Tawarmalani as a special case. We demonstrate how to obtain strong cutting planes for our formulation from both the stable set polytope and the boolean quadric polytope associated with a complete bipartite graph. Through an extensive computational study for three types of practical problems, we assess the performance of our proposed linear relaxation and new cutting-planes in terms of the optimality gap closed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Data availability

Data sharing not applicable to this article as no datasets were generated or analysed during the current study.

References

  1. Agra, A., Doostmohammadi, M., de Souza, C.C.: Valid inequalities for a single constrained 0–1 MIP set intersected with a conflict graph. Discrete Optim. 21, 42–70 (2016)

    Article  MathSciNet  Google Scholar 

  2. Atamtürk, A., Nemhauser, G.L., Savelsbergh, M.W.P.: Conflict graphs in solving integer programming problems. Eur. J. Oper. Res. 121(1), 40–55 (2000)

    Article  MathSciNet  Google Scholar 

  3. Atamtürk, A., Nemhauser, G.L., Savelsbergh, M.W.P.: The mixed vertex packing problem. Math. Program. 89(1, Ser. A), 35–53 (2000)

    Article  MathSciNet  Google Scholar 

  4. Balas, E.: Intersection cuts—a new type of cutting planes for integer programming. Oper. Res. 19, 19–39 (1971)

    Article  MathSciNet  Google Scholar 

  5. Balas, E.: Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM J. Algebraic Discrete Methods 6(3), 466–486 (1985)

    Article  MathSciNet  Google Scholar 

  6. Balas, E.: Disjunctive programming: properties of the convex hull of feasible points. Discrete Appl. Math. 89(1–3), 3–44 (1998)

    Article  MathSciNet  Google Scholar 

  7. Beale, E.M.L., Tomlin, J.A.: Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables. OR 69(447–45), 99 (1970)

    Google Scholar 

  8. Cao, B.: Transportation problem with nonlinear side constraints a branch and bound approach. Z. Oper. Res. 36, 185–197 (1992)

    MathSciNet  Google Scholar 

  9. Conforti, M., Cornuejols, G., Zambelli, G.: Integer Programming. Springer Publishing Company, Incorporated (2014)

    Book  Google Scholar 

  10. Davarnia, D., Richard, J.-P.P., Tawarmalani, M.: Simultaneous convexification of bilinear functions over polytopes with application to network interdiction. SIAM J. Optim. 27(3), 1801–1833 (2017)

    Article  MathSciNet  Google Scholar 

  11. de Farias, I.R., Johnson, E.L., Nemhauser, G.L.: Branch-and-cut for combinatorial optimization problems without auxiliary binary variables. Knowl. Eng. Rev. 16(1), 25–39 (2001)

    Article  Google Scholar 

  12. de Farias, I.R., Johnson, E.L., Nemhauser, G.L.: Facets of the complementarity knapsack polytope. Math. Oper. Res. 27(1), 210–226 (2002)

    Article  MathSciNet  Google Scholar 

  13. de Farias, I.R., Kozyreff, E., Zhao, M.: Branch-and-cut for complementarity-constrained optimization. Math. Program. Comput. 6(4), 365–403 (2014)

    Article  MathSciNet  Google Scholar 

  14. de Farias, I.R., Nemhauser, G.L.: A polyhedral study of the cardinality constrained knapsack problem. Math. Program. 96(3, Ser. A:), 439–467 (2003)

    Article  MathSciNet  Google Scholar 

  15. Del Pia, A., Linderoth, J., Zhu, H.: New classes of facets for complementarity knapsack problems. In: International Symposium on Combinatorial Optimization, pp. 3–21. Springer (2022)

  16. Deza, M., Sikirić, M.D.: Enumeration of the facets of cut polytopes over some highly symmetric graphs. Int. Trans. Oper. Res. 23(5), 853–860 (2016)

    Article  MathSciNet  Google Scholar 

  17. Ferris, M.C., Pang, J.-S.: Engineering and economic applications of complementarity problems. SIAM Rev. 39(4), 669–713 (1997)

    Article  MathSciNet  Google Scholar 

  18. Fischer, T., Pfetsch, M.E.: Branch-and-cut for linear programs with overlapping SOS1 constraints. Math. Program. Comput. 10(1), 33–68 (2018)

    Article  MathSciNet  Google Scholar 

  19. Hifi, M., Michrafy, M.: Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem. Comput. Oper. Res. 34(9), 2657–2673 (2007)

    Article  Google Scholar 

  20. Jing, H., Mitchell, J.E., Pang, J.-S., Bennett, K.P., Kunapuli, G.: On the global solution of linear programs with linear complementarity constraints. SIAM J. Optim. 19(1), 445–471 (2008)

    Article  MathSciNet  Google Scholar 

  21. Jing, H., Mitchell, J.E., Pang, J.-S., Bin, Yu.: On linear programs with linear complementarity constraints. J. Glob. Optim. 53(1), 29–51 (2012)

    Article  MathSciNet  Google Scholar 

  22. Ibaraki, T.: The use of cuts in complementary programming. Oper. Res. 21(1), 353–359 (1973)

    Article  MathSciNet  Google Scholar 

  23. Ibaraki, T.: Approximate algorithms for the multiple-choice continuous knapsack problems. J. Oper. Res. Soc. Jpn. 23(1), 28–63 (1980)

    MathSciNet  Google Scholar 

  24. Ibaraki, T., Hasegawa, T., Teranaka, K., Iwase, J.: The multiple-choice knapsack problem. J. Oper. Res. Soc. Jpn 21(1), 59–95 (1978)

    MathSciNet  Google Scholar 

  25. Jeroslow, R.G.: Cutting-planes for complementarity constraints. SIAM J. Control Optim. 16(1), 56–62 (1978)

    Article  MathSciNet  Google Scholar 

  26. Lovász, L.: Semidefinite programs and combinatorial optimization. In: Recent Advances in Algorithms and Combinatorics, pp. 137–194. Springer (2003)

  27. Luiz, T.A., Santos, H.G., Uchoa, E.: Cover by disjoint cliques cuts for the knapsack problem with conflicting items. Oper. Res. Lett. 49(6), 844–850 (2021)

    Article  MathSciNet  Google Scholar 

  28. Nguyen, T.T., Richard, J.-P.P., Tawarmalani, M.: Convexification techniques for linear complementarity constraints. J. Glob. Optim. 80(2), 249–286 (2021)

    Article  MathSciNet  Google Scholar 

  29. Padberg, M.: The Boolean quadric polytope: some characteristics, facets and relatives. Math. Program. 45(1, (Ser. B):), 139–172 (1989)

    Article  MathSciNet  Google Scholar 

  30. Padberg, M.W.: On the facial structure of set packing polyhedra. Math. Program. 5, 199–215 (1973)

    Article  MathSciNet  Google Scholar 

  31. Pferschy, U., Schauer, J.: The knapsack problem with conflict graphs. J. Graph Algorithms Appl. 13(2), 233–249 (2009)

    Article  MathSciNet  Google Scholar 

  32. Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3(3), 411–430 (1990)

    Article  MathSciNet  Google Scholar 

  33. Sherali, H.D., Krishnamurthy, R.S., Al-Khayyal, F.A.: Enhanced intersection cutting-plane approach for linear complementarity problems. J. Optim. Theory Appl. 90(1), 183–201 (1996)

    Article  MathSciNet  Google Scholar 

  34. Sripratak, P., Punnen, A.P., Stephen, T.: The bipartite Boolean quadric polytope. Discrete Optim. 44(2022), 100657 (2021)

    MathSciNet  Google Scholar 

  35. Sun, M.: A tabu search heuristic procedure for solving the transportation problem with exclusionary side constraints. J. Heuristics 3(4), 305–326 (1998)

    Article  Google Scholar 

  36. Syarif, A., Gen, M.: Solving exclusionary side constrained transportation problem by using a hybrid spanning tree-based genetic algorithm. J. Intell. Manuf. 14(3), 389–399 (2003)

    Article  Google Scholar 

Download references

Funding

A. Del Pia is partially funded by ONR grant N00014-19-1-2322. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the Office of Naval Research. The work of J. Linderoth and H. Zhu is supported by the Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Applied Mathematics program under Contract Number DE-AC02-06CH11347.

Author information

Authors and Affiliations

  1. Department of Industrial and Systems Engineering & Wisconsin Institute for Discovery, University of Wisconsin-Madison, Madison, USA

    Alberto Del Pia, Jeff Linderoth & Haoran Zhu

Authors
  1. Alberto Del Pia
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jeff Linderoth
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Haoran Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Haoran Zhu.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Del Pia, A., Linderoth, J. & Zhu, H. Relaxations and cutting planes for linear programs with complementarity constraints. J Glob Optim 90, 27–51 (2024). https://doi.org/10.1007/s10898-024-01397-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-024-01397-x

Keywords

Search

Navigation