On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming | SpringerLink
Skip to main content
Springer Nature Link
Log in

On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming

  • Conference paper
  • First Online:
Integer Programming and Combinatorial Optimization (IPCO 2020)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 12125))

  • 1276 Accesses

Abstract

Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solvers can often successfully handle a moderate presence of nonconvexities, which opens the door for the use of potentially tighter nonconvex relaxations. In this work, we exploit this fact and make use of a nonconvex relaxation obtained via aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in an MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithm’s ability to generate strong dual bounds through extensive computational experiments.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 7435
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 9294
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. MUMPS: Multifrontal massively parallel sparse direct solver. http://mumps.enseeiht.fr

  2. Achterberg, T.: Constraint integer programming. Ph.D. thesis, Technische Universität Berlin (2007). https://doi.org/10.14279/depositonce-1634. URN:nbn:de:kobv:83-opus-16117

  3. Achterberg, T., Wunderling, R.: Mixed integer programming: analyzing 12 years of progress. In: Jünger, M., Reinelt, G. (eds.) Facets of Combinatorial Optimization, pp. 449–481. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38189-8_18

    Chapter  MATH  Google Scholar 

  4. van Ackooij, W., Frangioni, A., de Oliveira, W.: Inexact stabilized benders’ decomposition approaches with application to chance-constrained problems with finite support. Comput. Optim. Appl. 65(3), 637–669 (2016). https://doi.org/10.1007/s10589-016-9851-z

    Article  MathSciNet  MATH  Google Scholar 

  5. Alidaee, B.: Zero duality gap in surrogate constraint optimization: a concise review of models. Eur. J. Oper. Res. 232(2), 241–248 (2014). https://doi.org/10.1016/j.ejor.2013.04.023

    Article  MathSciNet  MATH  Google Scholar 

  6. Amor, H.M.B., Desrosiers, J., Frangioni, A.: On the choice of explicit stabilizing terms in column generation. Discrete Appl. Math. 157(6), 1167–1184 (2009). https://doi.org/10.1016/j.dam.2008.06.021

    Article  MathSciNet  MATH  Google Scholar 

  7. Balas, E.: Discrete programming by the filter method. Oper. Res. 15(5), 915–957 (1967). https://doi.org/10.1287/opre.15.5.915

    Article  MathSciNet  MATH  Google Scholar 

  8. Balas, E.: Disjunctive programming: properties of the convex hull of feasible points. Discrete Appl. Math. 89(1–3), 3–44 (1998). https://doi.org/10.1016/s0166-218x(98)00136-x

    Article  MathSciNet  MATH  Google Scholar 

  9. Banerjee, K.: Generalized Lagrange multipliers in dynamic programming. Ph.D. thesis, University of California, Berkeley (1971)

    Google Scholar 

  10. Bonami, P., Lodi, A., Tramontani, A., Wiese, S.: On mathematical programming with indicator constraints. Math. Program. 151(1), 191–223 (2015). https://doi.org/10.1007/s10107-015-0891-4

    Article  MathSciNet  MATH  Google Scholar 

  11. COIN-OR: CppAD, a package for differentiation of C++ algorithms. http://www.coin-or.org/CppAD

  12. COIN-OR: Ipopt, Interior point optimizer. http://www.coin-or.org/Ipopt

  13. Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust Region Methods. Society for Industrial and Applied Mathematics, Philadelphia (2000). https://doi.org/10.1137/1.9780898719857

    Book  MATH  Google Scholar 

  14. Djerdjour, M., Mathur, K., Salkin, H.M.: A surrogate relaxation based algorithm for a general quadratic multi-dimensional knapsack problem. Oper. Res. Lett. 7(5), 253–258 (1988). https://doi.org/10.1016/0167-6377(88)90041-7

    Article  MathSciNet  MATH  Google Scholar 

  15. Dyer, M.E.: Calculating surrogate constraints. Math. Program. 19(1), 255–278 (1980). https://doi.org/10.1007/bf01581647

    Article  MathSciNet  MATH  Google Scholar 

  16. Fisher, M., Lageweg, B., Lenstra, J., Kan, A.: Surrogate duality relaxation for job shop scheduling. Discrete Appl. Math. 5(1), 65–75 (1983). https://doi.org/10.1016/0166-218x(83)90016-1

    Article  MATH  Google Scholar 

  17. Gavish, B., Pirkul, H.: Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality. Math. Program. 31(1), 78–105 (1985). https://doi.org/10.1007/bf02591863

    Article  MathSciNet  MATH  Google Scholar 

  18. Geoffrion, A.M.: Implicit enumeration using an imbedded linear program. Technical report, May 1967. https://doi.org/10.21236/ad0655444

  19. Glover, F.: A multiphase-dual algorithm for the zero-one integer programming problem. Oper. Res. 13(6), 879–919 (1965). https://doi.org/10.1287/opre.13.6.879

    Article  MATH  Google Scholar 

  20. Glover, F.: Surrogate constraints. Oper. Res. 16(4), 741–749 (1968). https://doi.org/10.1287/opre.16.4.741

    Article  MathSciNet  MATH  Google Scholar 

  21. Glover, F.: Surrogate constraint duality in mathematical programming. Oper. Res. 23(3), 434–451 (1975). https://doi.org/10.1287/opre.23.3.434

    Article  MathSciNet  MATH  Google Scholar 

  22. Glover, F.: Heuristics for integer programming using surrogate constraints. Decis. Sci. 8(1), 156–166 (1977). https://doi.org/10.1111/j.1540-5915.1977.tb01074.x

    Article  Google Scholar 

  23. Glover, F.: Tutorial on surrogate constraint approaches for optimization in graphs. J. Heuristics 9(3), 175–227 (2003). https://doi.org/10.1023/a:1023721723676

    Article  MATH  Google Scholar 

  24. Gomory, R.E.: An algorithm for the mixed integer problem. Technical report. P-1885, The RAND Corporation, June 1960

    Google Scholar 

  25. Greenberg, H.J., Pierskalla, W.P.: Surrogate mathematical programming. Oper. Res. 18(5), 924–939 (1970). https://doi.org/10.1287/opre.18.5.924

    Article  MathSciNet  MATH  Google Scholar 

  26. Grossmann, I.E., Sahinidis, N.V.: Special issue on mixed integer programmingand its application to engineering, part I. Optim. Eng. 3(4), 52–76 (2002)

    Google Scholar 

  27. Hendel, G.: Empirical analysis of solving phases in mixed integer programming. Master’s thesis, Technische Universität Berlin, August 2014. URN:nbn:de: http://nbn-resolving.de/urn:nbn:de:0297-zib-54270

  28. Horst, R., Tuy, H.: Global Optimization. Springer, Berlin Heidelberg (1996). DOI: https://doi.org/10.1007/978-3-662-03199-5

  29. ILOG, I.: ILOG CPLEX: High-performance software for mathematical programming and optimization. http://www.ilog.com/products/cplex/

  30. Kelley Jr., J.E.: The cutting-plane method for solving convex programs. J. Soc. Ind. Appl. Math. 8(4), 703–712 (1960). https://doi.org/10.1137/0108053

    Article  MathSciNet  MATH  Google Scholar 

  31. Junttila, T., Kaski, P.: Bliss: a tool for computing automorphism groups and canonical labelings of graphs. (2012). http://www.tcs.hut.fi/Software/bliss/

  32. Karwan, M.H.: Surrogate constraint duality and extensions in integer programming. Ph.D. thesis, Georgia Institute of Technology, January 1976

    Google Scholar 

  33. Karwan, M.H., Rardin, R.L.: Some relationships between Lagrangian and surrogate duality in integer programming. Math. Program. 17(1), 320–334 (1979). https://doi.org/10.1007/bf01588253

    Article  MathSciNet  MATH  Google Scholar 

  34. Karwan, M.H., Rardin, R.L.: Surrogate dual multiplier search procedures in integer programming. Oper. Res. 32(1), 52–69 (1984). https://doi.org/10.1287/opre.32.1.52

    Article  MathSciNet  MATH  Google Scholar 

  35. Kim, S.L., Kim, S.: Exact algorithm for the surrogate dual of an integer programming problem: subgradient method approach. J. Optim. Theory Appl. 96(2), 363–375 (1998). https://doi.org/10.1023/a:1022622231801

    Article  MathSciNet  MATH  Google Scholar 

  36. McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: Part i – convex underestimating problems. Math. Program. 10(1), 147–175 (1976). https://doi.org/10.1007/bf01580665

    Article  MATH  Google Scholar 

  37. du Merle, O., Villeneuve, D., Desrosiers, J., Hansen, P.: Stabilized column generation. Discrete Math. 194(1–3), 229–237 (1999). https://doi.org/10.1016/s0012-365x(98)00213-1

    Article  MathSciNet  MATH  Google Scholar 

  38. MINLP library. http://www.minlplib.org/

  39. Nakagawa, Y.: An improved surrogate constraints method for separable nonlinear integer programming. J. Oper. Res. Soc. Jpn 46(2), 145–163 (2003). https://doi.org/10.15807/jorsj.46.145

    Article  MathSciNet  MATH  Google Scholar 

  40. Narciso, M.G., Lorena, L.A.N.: Lagrangean/surrogate relaxation for generalized assignment problems. Eur. J. Oper. Res. 114(1), 165–177 (1999). https://doi.org/10.1016/s0377-2217(98)00038-1

    Article  MATH  Google Scholar 

  41. Nemhauser, G.L., Wolsey, L.A.: A recursive procedure to generate all cuts for 0–1 mixed integer programs. Math. Program. 46(1–3), 379–390 (1990). https://doi.org/10.1007/bf01585752

    Article  MathSciNet  MATH  Google Scholar 

  42. Quesada, I., Grossmann, I.E.: A global optimization algorithm for linear fractional and bilinear programs. J. Glob. Optim. 6(1), 39–76 (1995). https://doi.org/10.1007/bf01106605

    Article  MathSciNet  MATH  Google Scholar 

  43. Ryoo, H., Sahinidis, N.: Global optimization of nonconvex NLPs and MINLPs with applications in process design. Comput. Chem. Eng. 19(5), 551–566 (1995). https://doi.org/10.1016/0098-1354(94)00097-2

    Article  Google Scholar 

  44. Sarin, S., Karwan, M.H., Rardin, R.L.: A new surrogate dual multiplier search procedure. Naval Res. Logistics 34(3), 431–450 (1987). https://doi.org/10.1002/1520-6750(198706)34:3<431::aid-nav3220340309>3.0.co;2-p

    Article  MathSciNet  MATH  Google Scholar 

  45. SCIP - Solving Constraint Integer Programs. http://scip.zib.de

  46. Sherali, H.D., Adams, W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Springer, New York (1999). https://doi.org/10.1007/978-1-4757-4388-3

    Book  MATH  Google Scholar 

  47. Sherali, H.D., Fraticelli, B.M.P.: Enhancing RLT relaxations via a new class of semidefinite cuts. J. Glob. Optim. 22(1/4), 233–261 (2002). https://doi.org/10.1023/a:1013819515732

    Article  MathSciNet  MATH  Google Scholar 

  48. Templeman, A.B., Xingsi, L.: A maximum entropy approach to constrained non-linear programming. Eng. Optim. 12(3), 191–205 (1987). https://doi.org/10.1080/03052158708941094

    Article  Google Scholar 

  49. Vielma, J.P.: Small and strong formulations for unions of convex sets from the Cayley embedding. Math. Program. 177(1–2), 21–53 (2018). https://doi.org/10.1007/s10107-018-1258-4

    Article  MathSciNet  MATH  Google Scholar 

  50. Vigerske, S.: Decomposition in multistage stochastic programming and a constraint integer programming approach to mixed-integer nonlinear programming. Ph.D. thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II (2013). URN:nbn:de:kobv:11-100208240

  51. Vigerske, S., Gleixner, A.: SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework. Optim. Methods Softw. 33(3), 563–593 (2017). https://doi.org/10.1080/10556788.2017.1335312

    Article  MathSciNet  MATH  Google Scholar 

  52. Wächter, A., Biegler, L.T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106(1), 25–57 (2005). https://doi.org/10.1007/s10107-004-0559-y

    Article  MathSciNet  MATH  Google Scholar 

  53. Xingsi, L.: An aggregate constraint method for non-linear programming. J. Oper. Res. Soc. 42(11), 1003–1010 (1991). https://doi.org/10.1057/jors.1991.190

    Article  MATH  Google Scholar 

Download references

Acknowledgements

We gratefully acknowledge support from the Research Campus MODAL (BMBF Grant 05M14ZAM) and the Institute for Data Valorization (IVADO) through an IVADO Postdoctoral Fellowship.

Author information

Authors and Affiliations

  1. Zuse Institute Berlin, Berlin, Germany

    Benjamin Müller, Ambros Gleixner & Felipe Serrano

  2. Universidad de O’Higgins, Rancagua, Chile

    Gonzalo Muñoz

  3. Polytechnique Montréal, Montréal, Canada

    Maxime Gasse & Andrea Lodi

Authors
  1. Benjamin Müller
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gonzalo Muñoz
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Maxime Gasse
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ambros Gleixner
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Andrea Lodi
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Felipe Serrano
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Benjamin Müller .

Editor information

Editors and Affiliations

  1. Department of IEOR, Columbia University, New York, NY, USA

    Daniel Bienstock

  2. Department of Management, London School of Economics and Political Science, London, UK

    Giacomo Zambelli

A Appendix

A Appendix

1.1 A.1 The Effect of Stabilization

To visualize the importance of stabilization techniques, we use the instance genpooling_lee1. Figure 1 shows the achieved dual bounds after each iteration of Algorithm 1 for DEFAULT and NOSTAB. The achieved dual bound of \(-4775.26\) with DEFAULT is significantly better than the dual bound of \(-5006.95\) when using NOSTAB. More importantly, stabilization helps to reach the final dual bound much earlier.

Fig. 1.
figure 1

Dual bounds for DEFAULT (left) and NOSTAB (right) on genpooling_lee1 using \(K=3\). The red dashed curve shows the best found dual bound so far, whereas the blue curve shows the computed dual bound at each iteration. (Color figure online)

Full size image
Table 3. Best known primal vs. the dual bounds computed by SCIP, Algorithm 1, and reported in MINLPLib for all polygon* and four facloc* instances.
Full size table

1.2 A.2 Detailed Results for the DUALBOUND Experiment

Table 4. Detailed results for the DUALBOUND experiment on \(53\) instances for which Algorithm 1 could find a better dual bound in the root node.
Full size table

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Müller, B., Muñoz, G., Gasse, M., Gleixner, A., Lodi, A., Serrano, F. (2020). On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming. In: Bienstock, D., Zambelli, G. (eds) Integer Programming and Combinatorial Optimization. IPCO 2020. Lecture Notes in Computer Science(), vol 12125. Springer, Cham. https://doi.org/10.1007/978-3-030-45771-6_25

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-45771-6_25

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-45770-9

  • Online ISBN: 978-3-030-45771-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics