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

A feasible rounding approach for mixed-integer optimization problems

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

We introduce granularity as a sufficient condition for the consistency of a mixed-integer optimization problem, and show how to exploit it for the computation of feasible points: For optimization problems which are granular, solving certain linear problems and rounding their optimal points always leads to feasible points of the original mixed-integer problem. Thus, the resulting feasible rounding approach is deterministic and even efficient, i.e., it computes feasible points in polynomial time. The optimization problems appearing in the feasible rounding approaches have a structure that is similar to that of the continuous relaxation, and thus our approach has significant advantages over heuristics, as long as the problem is granular. For instance, the computational cost of our approach always corresponds to merely a single step of the feasibility pump. A computational study on optimization problems from the MIPLIB libraries demonstrates that granularity may be expected in various real world applications. Moreover, a comparison with Gurobi indicates that state of the art software does not always exploit granularity. Hence, our algorithms do not only possess a worst-case complexity advantage, but can also improve the CPU time needed to solve problems from practice.

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
Fig. 2

Similar content being viewed by others

References

  1. Achterberg, T., Berthold, T.: Improving the feasibility pump. Discrete Optim. 4, 77–86 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  2. Achterberg, T., Bixby, R., Gu, Z., Rothberg, E., Weninger, D.: Presolve reductions in mixed integer programming, Technical Report pp. 16–44, ZIB

  3. Achterberg, T., Koch, T., Martin, A.: MIPLIB 2003. Oper. Res. Lett. 34, 361–372 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  4. Baum, S.P., Trotter Jr., L.E.: Integer rounding for polymatroid and branching optimization problems. SIAM J. Algebraic Discrete Methods 2, 416–425 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  5. Belotti, P., Kirches, C., Leyffer, S., Linderoth, J., Luedtke, J., Mahajan, A.: Mixed-integer nonlinear optimization. Acta Numer. 22, 1–131 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  6. Bertacco, L., Fischetti, M., Lodi, A.: A feasibility pump heuristic for general mixed-integer problems. Discrete Optim. 4, 63–76 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  7. Berthold, T.: RENS—the optimal rounding. Math. Program. Comput. 6, 33–54 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  8. Berthold, T., Gleixner, A.M.: Undercover: a primal MINLP heuristic exploring a largest sub-MIP. Math. Program. 144, 315–346 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  9. Boland, N.L., Eberhard, A.C., Engineer, F.G., Fischetti, M., Savelsbergh, M.W.P., Tsoukalas, A.: Boosting the feasibility pump. Math. Program. Comput. 6, 255–279 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  10. Bonami, P., Gonçalves, J.P.M.: Heuristics for convex mixed integer nonlinear programs. Comput. Optim. Appl. 51, 729–747 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  11. Conforti, M., Cornuéjols, G., Zambelli, G.: Integer Programming. Springer, New York (2014)

    MATH  Google Scholar 

  12. Fischetti, M., Glover, F., Lodi, A.: The feasibility pump. Math. Program. 104, 91–104 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  13. Fischetti, M., Salvagnin, D.: Feasibility pump 2.0. Math. Program. Comput. 1, 201–222 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  14. Hillier, F.S.: Efficient heuristic procedures for integer linear programming with an interior. Oper. Res. 17, 600–637 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  15. Kannan, R., Bachem, A.: Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM J. Comput. 8, 499–507 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  16. 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. Program. Comput. 3, 103–163 (2011)

    Article  MathSciNet  Google Scholar 

  17. Nannicini, G., Belotti, P.: Rounding-based heuristics for nonconvex MINLPs. Math. Program. Comput. 4, 1–31 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  18. Neumann, C., Stein, O., Sudermann-Merx, N.: Granularity in nonlinear mixed-integer optimization. Optimization Online, Preprint ID 2017-12-6367 (2017)

  19. Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Hoboken (1998)

    MATH  Google Scholar 

  20. Stein, O.: Error bounds for mixed integer linear optimization problems. Math. Program. 156, 101–123 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  21. Stein, O.: Error bounds for mixed integer nonlinear optimization problems. Optim. Lett. 10, 1153–1168 (2016)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors are grateful to Sven Leyffer, Benjamin Müller and two anonymous referees for their precise and substantial remarks, which helped to significantly improve the paper.

Author information

Authors and Affiliations

  1. Institute of Operations Research, Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany

    Christoph Neumann & Oliver Stein

  2. Advanced Business Analytics, BASF Business Services GmbH, Ludwigshafen am Rhein, Germany

    Nathan Sudermann-Merx

Authors
  1. Christoph Neumann
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Oliver Stein
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Nathan Sudermann-Merx
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Oliver Stein.

Appendix

Appendix

See Table 4

Table 4 A comparison of the feasible rounding approaches and Gurobi with regard to time (seconds) and objective value on unaltered models
Full size table

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Neumann, C., Stein, O. & Sudermann-Merx, N. A feasible rounding approach for mixed-integer optimization problems. Comput Optim Appl 72, 309–337 (2019). https://doi.org/10.1007/s10589-018-0042-y

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-018-0042-y

Keywords

Mathematics Subject Classification

Search

Navigation