mixed integer nonlinear programming

www.it-ebooks.info

For further volumes:

The IMA Volumes in Mathematics

and its Applications

Volume 154

http://www.springer.com/series/811

www.it-ebooks.info

Institute for Mathematics and

its Applications (IMA)

The Institute for Mathematics and its Applications was estab￾lished by a grant from the National Science Foundation to the University

of Minnesota in 1982. The primary mission of the IMA is to foster research

of a truly interdisciplinary nature, establishing links between mathematics

of the highest caliber and important scientific and technological problems

from other disciplines and industries. To this end, the IMA organizes a wide

variety of programs, ranging from short intense workshops in areas of ex￾ceptional interest and opportunity to extensive thematic programs lasting

a year. IMA Volumes are used to communicate results of these programs

that we believe are of particular value to the broader scientific community.

The full list of IMA books can be found at the Web site of the Institute

for Mathematics and its Applications:

http://www.ima.umn.edu/springer/volumes.html.

Presentation materials from the IMA talks are available at

http://www.ima.umn.edu/talks/.

Video library is at

http://www.ima.umn.edu/videos/.

Fadil Santosa, Director of the IMA

**********

IMA ANNUAL PROGRAMS

1982–1983 Statistical and Continuum Approaches to Phase Transition

1983–1984 Mathematical Models for the Economics of Decentralized

Resource Allocation

1984–1985 Continuum Physics and Partial Differential Equations

1985–1986 Stochastic Differential Equations and Their Applications

1986–1987 Scientific Computation

1987–1988 Applied Combinatorics

1988–1989 Nonlinear Waves

1989–1990 Dynamical Systems and Their Applications

1990–1991 Phase Transitions and Free Boundaries

1991–1992 Applied Linear Algebra

Continued at the back www.it-ebooks.info

Jon Lee • Sven Leyffer

Mixed Integer Nonlinear

Programming

Editors

www.it-ebooks.info

Printed on acid-free paper

Springer is part of Springer Science+Business Media (www.springer.com)

Jon Lee

University of Michigan

Ann Arbor, Michigan 48109

USA

Editors

Sven Leyffer

Mathematics and Computer Science

Argonne National Laboratory

Argonne, Illinois 60439

USA

Industrial and Operations Engineering

1205 Beal Avenue

ISSN

Springer New York Dordrecht Heidelberg London

ISBN 978-1-4614-1926-6

DOI 10.1007/978-1-4614-1927-3

e-ISBN 978-1-4614-1927-3

¤ Springer Science+Business Media, LLC 2012

0940-6573

Library of Congress Control Number: 2011942482

All rights reserved. This work may not be translated or copied in whole or in part without the written

permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York,

NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in

connection with any form of information storage and retrieval, electronic adaptation, computer

software, or by similar or dissimilar methodology now known or hereafter developed is forbidden.

The use in this publication of trade names, trademarks, service marks, and similar terms, even if they

are not identified as such, is not to be taken as an expression of opinion as to whether or not they are

subject to proprietary rights.

Mathematics Subject Classification (2010): 05C25, 20B25, 49J15, 49M15, 49M37, 49N90, 65K05,

90C10, 90C11, 90C22, 90C25, 90C26, 90C27, 90C30, 90C35, 90C51, 90C55, 90C57, 90C60,

90C90, 93C95

www.it-ebooks.info

FOREWORD

This IMA Volume in Mathematics and its Applications

MIXED INTEGER NONLINEAR PROGRAMMING

contains expository and research papers based on a highly successful IMA

Hot Topics Workshop “Mixed-Integer Nonlinear Optimization: Algorith￾mic Advances and Applications”. We are grateful to all the participants

for making this occasion a very productive and stimulating one.

We would like to thank Jon Lee (Industrial and Operations Engineer￾ing, University of Michigan) and Sven Leyffer (Mathematics and Computer

Science, Argonne National Laboratory) for their superb role as program or￾ganizers and editors of this volume.

We take this opportunity to thank the National Science Foundation

for its support of the IMA.

Series Editors

Fadil Santosa, Director of the IMA

Markus Keel, Deputy Director of the IMA

v

www.it-ebooks.info

www.it-ebooks.info

PREFACE

Many engineering, operations, and scientific applications include a mixture

of discrete and continuous decision variables and nonlinear relationships

involving the decision variables that have a pronounced effect on the set

of feasible and optimal solutions. Mixed-integer nonlinear programming

(MINLP) problems combine the numerical difficulties of handling nonlin￾ear functions with the challenge of optimizing in the context of nonconvex

functions and discrete variables. MINLP is one of the most flexible model￾ing paradigms available for optimization; but because its scope is so broad,

in the most general cases it is hopelessly intractable. Nonetheless, an ex￾panding body of researchers and practitioners — including chemical en￾gineers, operations researchers, industrial engineers, mechanical engineers,

economists, statisticians, computer scientists, operations managers, and

mathematical programmers — are interested in solving large-scale MINLP

instances.

Of course, the wealth of applications that can be accurately mod￾eled by using MINLP is not yet matched by the capability of available

optimization solvers. Yet, the two key components of MINLP — mixed￾integer linear programming (MILP) and nonlinear programming (NLP) —

have experienced tremendous progress over the past 15 years. By cleverly

incorporating many theoretical advances in MILP research, powerful aca￾demic, open-source, and commercial solvers have paved the way for MILP

to emerge as a viable, widely used decision-making tool. Similarly, new

paradigms and better theoretical understanding have created faster and

more reliable NLP solvers that work well, even under adverse conditions

such as failure of constraint qualifications.

In the fall of 2008, a Hot-Topics Workshop on MINLP was organized

at the IMA, with the goal of synthesizing these advances and inspiring new

ideas in order to transform MINLP. The workshop attracted more than 75

attendees, over 20 talks, and over 20 posters. The present volume collects

22 invited articles, organized into nine sections on the diverse aspects of

MINLP. The volume includes survey articles, new research material, and

novel applications of MINLP.

In its most general and abstract form, a MINLP can be expressed as

minimize x f(x) subject to x ∈ F, (1)

where f : Rn → R is a function and the feasible set F contains both non￾linear and discrete structure. We note that we do not generally assume

smoothness of f or convexity of the functions involved. Different realiza￾tions of the objective function f and the feasible set F give rise to key

classes of MINLPs addressed by papers in this collection.

vii

www.it-ebooks.info

viii PREFACE

Part I. Convex MINLP. Even though mixed-integer optimization prob￾lems are nonconvex as a result of the presence of discrete variables, the

term convex MINLP is commonly used to refer to a class of MINLPs for

which a convex program results when any explicit restrictions of discrete￾ness on variables are relaxed (i.e., removed). In its simplest definition, for

a convex MINLP, we may assume that the objective function f in (1) is a

convex function and that the feasible set F is described by a set of convex

nonlinear function, c : Rn → Rm, and a set of indices, I⊂{1,...,n}, of

integer variables:

F = {x ∈ Rn | c(x) ≤ 0, and xi ∈ Z, ∀i ∈ I}. (2)

Typically, we also demand some smoothness of the functions involved.

Sometimes it is useful to expand the definition of convex MINLP to sim￾ply require that the functions be convex on the feasible region. Besides

problems that can be directly modeled as convex MINLPs, the subject has

relevance to methods that create convex MINLP subproblems.

Algorithms and software for convex mixed-integer nonlinear programs

(P. Bonami, M. Kilin¸c, and J. Linderoth) discusses the state of the art for

algorithms and software aimed at convex MINLPs. Important elements of

successful methods include a tree search (to handle the discrete variables),

NLP subproblems to tighten linearizations, and MILP master problems to

collect and exploit the linearizations.

A special type of convex constraint is a second-order cone constraint:

y2 ≤ z, where y is vector variable and z is a scalar variable. Subgradient￾based outer approximation for mixed-integer second-order cone program￾ming (S. Drewes and S. Ulbrich) demonstrates how such constraints can be

handled by using outer-approximation techniques. A main difficulty, which

the authors address using subgradients, is that at the point (y, z) = (0, 0),

the function y2 is not differentiable.

Many convex MINLPs have “off/on” decisions that force a continuous

variable either to be 0 or to be in a convex set. Perspective reformula￾tion and applications (O. G¨unl¨uk and J. Linderoth) describes an effective

reformulation technique that is applicable to such situations. The perspec￾tive g(x, t) = tc(x/t) of a convex function c(x) is itself convex, and this

property can be used to construct tight reformulations. The perspective

reformulation is closely related to the subject of the next section: disjunc￾tive programming.

Part II. Disjunctive programming. Disjunctive programs involve con￾tinuous variable together with Boolean variables which model logical propo￾sitions directly rather than by means of an algebraic formulation.

Generalized disjunctive programming: A framework for formulation

and alternative algorithms for MINLP optimization (I.E. Grossmann and

J.P. Ruiz) addresses generalized disjunctive programs (GDPs), which are

MINLPs that involve general disjunctions and nonlinear terms. GDPs can

www.it-ebooks.info

PREFACE ix

be formulated as MINLPs either through the “big-M” formulation, or by

using the perspective of the nonlinear functions. The authors describe

two approaches: disjunctive branch-and-bound, which branches on the dis￾junctions, and and logic-based outer approximation, which constructs a

disjunctive MILP master problem.

Under the assumption that the problem functions are factorable (i.e.,

the functions can be computed in a finite number of simple steps by us￾ing unary and binary operators), a MINLP can be reformulated as an

equivalent MINLP where the only nonlinear constraints are equations in￾volving two or three variables. The paper Disjunctive cuts for nonconvex

MINLP (P. Belotti) describes a procedure for generating disjunctive cuts.

First, spatial branching is performed on an original problem variable. Next,

bound reduction is applied to the two resulting relaxations, and linear

relaxations are created from a small number of outer approximations of

each nonlinear expression. Then a cut-generation LP is used to produce a

new cut.

Part III. Nonlinear programming. For several important and practical

approaches to solving MINLPs, the most important part is the fast and

accurate solution of NLP subproblems. NLPs arise both as nodes in branch￾and-bound trees and as subproblems for fixed integer or Boolean variables.

The papers in this section discuss two complementary techniques for solving

NLPs: active-set methods in the form of sequential quadratic programming

(SQP) methods and interior-point methods (IPMs).

Sequential quadratic programming methods (P.E. Gill and E. Wong)

is a survey of a key NLP approach, sequential quadratic programming

(SQP), that is especially relevant to MINLP. SQP methods solve NLPs by

a sequence of quadratic programming approximations and are particularly

well-suited to warm starts and re-solves that occur in MINLP.

IPMs are an alternative to SQP methods. However, standard IPMs

can stall if started near a solution, or even fail on infeasible NLPs, mak￾ing them less suitable for MINLP. Using interior-point methods within an

outer approximation framework for mixed-integer nonlinear programming

(H.Y. Benson) suggests a primal-dual regularization that penalizes the con￾straints and bounds the slack variables to overcome the difficulties caused

by warm starts and infeasible subproblems.

Part IV. Expression graphs. Expression graphs are a convenient way

to represent functions. An expression graph is a directed graph in which

each node represents an arithmetic operation, incoming edges represent op￾erations, and outgoing edges represent the result of the operation. Expres￾sion graphs can be manipulated to obtain derivative information, perform

problem simplifications through presolve operations, or obtain relaxations

of nonconvex constraints.

Using expression graphs in optimization algorithms (D.M. Gay) dis￾cusses how expression graphs allow gradients and Hessians to be computed

www.it-ebooks.info

x PREFACE

efficiently by exploiting group partial separability. In addition, the author

describes how expression graphs can be used to tighten bounds on variables

to provide tighter outer approximations of nonconvex expressions, detect

convexity (e.g., for quadratic constraints), and propagate constraints.

Symmetry arises in many MINLP formulations and can mean that

a problem or subproblem may have many symmetric optima or near op￾tima, resulting in large search trees and inefficient pruning. Symmetry in

mathematical programming (L. Liberti) describes how the symmetry group

of a MINLP can be detected by parsing the expression graph. Once the

symmetry group is known, we can add symmetry-breaking constraints or

employ special branching schemes such as orbital branching that mitigate

the adverse effects of symmetry.

Part V. Convexification and linearization. A popular and classical

approach for handling nonconvex functions is to approximate them by using

piecewise-linear functions. This approach requires the addition of binary

variables that model the piecewise approximation. The advantage of such

an approach is that advanced MILP techniques can be applied. The disad￾vantage of the approach is that the approximations are not exact and that

it suffers from the curse of dimensionality.

Using piecewise linear functions for solving MINLPs (B. Geißler, A.

Martin, A. Morsi, and L. Schewe) details how to carry out piecewise-linear

approximation for MINLP. The authors review two formulations of piece￾wise linearization: the convex combination technique and the incremental

technique. They introduce a piecewise-polyhedral outer-approximation al￾gorithm based on rigorous error estimates, and they demonstrate compu￾tational success on water network and gas network problems.

A global-optimization algorithm for mixed-integer nonlinear programs

having separable nonconvexity (C. D’Ambrosio, J. Lee, and A. W¨achter)

introduces a method for MINLPs that have all of their nonconvexity in

separable form. The approach aims to retain and exploit existing convexity

in the formulation.

Global optimization of mixed-integer signomial programming problems

(A. Lundell and T. Westerlund) describes a global optimization algorithm

for MINLPs containing signomial functions. The method obtains a convex

relaxation through reformulations, by using single-variable transformations

in concert with piecewise-linear approximations of the inverse transforma￾tions.

Part VI. Mixed-integer quadratically-constrained optimization.

In seeking a more structured setting than general MINLP, but with consid￾erably more modeling power than is afforded by MILP, one naturally con￾siders mixed-integer models with quadratic functions, namely, MIQCPs.

Such models are NP-hard, but they have enough structure that can be

exploited in order to gain computational advantages over treating such

problems as general MINLPs.

www.it-ebooks.info

PREFACE xi

The MILP road to MIQCP (S. Burer and A. Saxena) surveys re￾sults in mixed-integer quadratically constrained programming. Strong con￾vex relaxations and valid inequalities are the basis of efficient, practical

techniques for global optimization. Some of the relaxations and inequal￾ities are derived from the algebraic formulation, while others are based

on disjunctive programming. Much of the inspiration derives from MILP

methodology.

Linear programming relaxations of quadratically-constrained quadratic

programs (A. Qualizza, P. Belotti, and F. Margot) investigates the use

of LP tools for approximately solving semidefinite programming (SDP)

relaxations of quadratically-constrained quadratic programs. The authors

present classes of valid linear inequalities based on spectral decomposition,

together with computational results.

Extending a CIP framework to solve MIQCPs (T. Berthold, S. Heinz,

and S. Vigerske) discusses how to build a solver for MIQCPs by extending a

framework for constraint integer programming (CIP). The advantage of this

approach is that we can utilize the full power of advanced MILP and con￾straint programming technologies. For relaxation, the approach employs

an outer approximation generated by linearization of convex constraints

and linear underestimation of nonconvex constraints. Reformulation, sep￾aration, and propagation techniques are used to handle the quadratic con￾straints efficiently. The authors implemented these methods in the branch￾cut-and-price framework SCIP.

Part VII. Combinatorial optimization. Because of the success of

MILP methods and because of beautiful and algorithmically important re￾sults from polyhedral combinatorics, nonlinear functions and formulations

have not been heavily investigated for combinatorial optimization prob￾lems. With improvements in software for general NLP, SDP, and MINLP,

however, researchers are now investing considerable effort in trying to ex￾ploit these gains for combinatorial-optimization problems.

Computation with polynomial equations and inequalities arising in

combinatorial optimization (J.A. De Loera, P.N. Malkin, and P.A. Par￾rilo) discusses how the algebra of multivariate polynomials can be used to

create large-scale linear algebra or semidefinite-programming relaxations of

many kinds of combinatorial feasibility and optimization problems.

Matrix relaxations in combinatorial optimization (F. Rendl) discusses

the use of SDP as a modeling tool in combinatorial optimization. The

main techniques to get matrix relaxations of combinatorial-optimization

problems are presented. Semidefiniteness constraints lead to tractable re￾laxations, while constraints that matrices be completely positive or copos￾itive do not. This survey illustrates the enormous power and potential of

matrix relaxations.

A polytope for a product of real linear functions in 0/1 variables (O.

G¨unl¨uk, J. Lee, and J. Leung) uses polyhedral methods to give a tight

www.it-ebooks.info

xii PREFACE

formulation for the convex hull of a product of two linear functions in

0/1 variables. As an example, by writing a pair of general integer vari￾ables in binary expansion, the authors have a technique for linearizing their

product.

Part VIII. Complexity. General MINLP is incomputable, independent

of conjectures such as P=NP. From the point of view of complexity the￾ory, however, considerable room exists for negative results (e.g., incom￾putability, intractablility and inapproximability results) and positive re￾sults (e.g., polynomial-time algorithms and approximations schemes) for

restricted classes of MINLPs.

On the complexity of nonlinear mixed-integer optimization (M. K¨oppe)

is a survey on the computational complexity of MINLP. It includes incom￾putability results that arise from number theory and logic, fully polynomial￾time approximation schemes in fixed dimension, and polynomial-time al￾gorithms for special cases.

Theory and applications of n-fold integer programming (S. Onn) is

an overview of the theory of n-fold integer programming, which enables

the polynomial-time solution of fundamental linear and nonlinear inte￾ger programming problems in variable dimension. This framework yields

polynomial-time algorithms in several application areas, including multi￾commodity flows and privacy in statistical databases.

Part IX. Applications. A wide range of applications of MINLP exist.

This section focuses on two new application domains.

MINLP application for ACH interiors restructuring (E. Klampfl and

Y. Fradkin) describes a very large-scale application of MINLP developed

by the Ford Motor Company. The MINLP models the re-engineering of

42 product lines over 26 manufacturing processes and 50 potential supplier

sites. The resulting MINLP model has 350,000 variables (17,000 binary)

and 1.6 million constraints and is well beyond the size that state-of-the-art

MINLP solvers can handle. The authors develop a piecewise-linearization

scheme for the objective and a decomposition technique that decouples the

problem into two coupled MILPs that are solved iteratively.

A benchmark library of mixed-integer optimal control problems (S.

Sager) describes a challenging new class of MINLPs. These are optimal

control problems, involving differential-algebraic equation constraints and

integrality restrictions on the controls, such as gear ratios. The authors de￾scribe 12 models from a range of applications, including biology, industrial

engineering, trajectory optimization, and process control.

Acknowledgments. We gratefully acknowledge the generous financial

support from the IMA that made this workshop possible, as well as fi￾nancial support from IBM. This work was supported in part by the Of￾fice of Advanced Scientific Computing Research, Office of Science, U.S.

Department of Energy, under Contract DE-AC02-06CH11357. Special

www.it-ebooks.info

PREFACE xiii

thanks are due to Fadil Santosa, Chun Liu, Patricia Brick, Dzung Nguyen,

Holly Pinkerton, and Eve Marofsky from the IMA, who made the organi￾zation of the workshop and the publication of this special volume such an

easy and enjoyable affair.

Jon Lee

University of Michigan

Sven Leyffer

Argonne National Laboratory

www.it-ebooks.info

www.it-ebooks.info