A center-cut algorithm for quickly obtaining feasible solutions and solving convex MINLP problems

A1 Originalartikel i en vetenskaplig tidskrift (referentgranskad)

Interna författare/redaktörer

Publikationens författare: J. Kronqvist, D.E. Bernal, A. Lundell, T. Westerlund
Förläggare: Elsevier
Publiceringsår: 2019
Tidskrift: Computers and Chemical Engineering
Tidskriftsakronym: Comput. Chem. Eng.
Volym: 122
Artikelns första sida, sidnummer: 105
Artikelns sista sida, sidnummer: 113
Antal sidor: 9
ISSN: 0098-1354
eISSN: 1873-4375


Here we present a center-cut algorithm for convex mixed-integer nonlinear programming (MINLP) that can either be used as a primal heuristic or as a deterministic solution technique. Like several other algorithms for convex MINLP, the center-cut algorithm constructs a linear approximation of the original problem. The main idea of the algorithm is to use the linear approximation differently in order to find feasible solutions within only a few iterations. The algorithm chooses trial solutions as the center of the current linear outer approximation of the nonlinear constraints, making the trial solutions more likely to satisfy the constraints. The ability to find feasible solutions within only a few iterations makes the algorithm well suited as a primal heuristic, and we prove that the algorithm finds the optimal solution within a finite number of iterations. Numerical results show that the algorithm obtains feasible solutions quickly and is able to obtain good solutions.


Center-cut algorithm, Convex MINLP, Cutting plane techniques, Outer approximation, Primal heuristics

Senast uppdaterad 2020-28-09 vid 02:50