Branch-and-price for a class of nonconvex mixed-integer nonlinear programs

Andrew Allman, Qi Zhang

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


This work attempts to combine the strengths of two major technologies that have matured over the last three decades: global mixed-integer nonlinear optimization and branch-and-price. We consider a class of generally nonconvex mixed-integer nonlinear programs (MINLPs) with linear complicating constraints and integer linking variables. If the complicating constraints are removed, the problem becomes easy to solve, e.g. due to decomposable structure. Integrality of the linking variables allows us to apply a discretization approach to derive a Dantzig-Wolfe reformulation and solve the problem to global optimality using branch-andprice. It is a remarkably simple idea; but to our surprise, it has barely found any application in the literature. In this work, we show that many relevant problems directly fall or can be reformulated into this class of MINLPs. We present the branch-and-price algorithm and demonstrate its effectiveness (and sometimes ineffectiveness) in an extensive computational study considering multiple large-scale problems of practical relevance, showing that, in many cases, orders-of-magnitude reductions in solution time can be achieved.

Original languageEnglish (US)
Pages (from-to)861-880
Number of pages20
JournalJournal of Global Optimization
Issue number4
StatePublished - Dec 2021

Bibliographical note

Funding Information:
The authors gratefully acknowledge financial support from the University of Minnesota and the Minnesota Supercomputing Institute (MSI) at the University of Minnesota for providing resources that contributed to the research results reported within this paper. We also thank Angela Flores-Quiroz for insightful discussions on our work.

Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.


  • Branch-and-price
  • Decomposition
  • Mixed-integer nonlinear programming
  • Nonconvex optimization


Dive into the research topics of 'Branch-and-price for a class of nonconvex mixed-integer nonlinear programs'. Together they form a unique fingerprint.

Cite this