% This file was created with JabRef 2.3.1. % Encoding: Cp1252 @INPROCEEDINGS{Atamturk2007Conic, author = {Alper Atamt{\"u}rk and Vishnu Narayanan}, title = {Cuts for Conic Mixed-Integer Programming}, booktitle = {IPCO}, year = {2007}, editor = {Matteo Fischetti and David P. Williamson}, volume = {4513}, series = {Lecture Notes in Computer Science}, pages = {16--29}, publisher = {Springer}, abstract = {A conic integer program is an integer programming problem with conic constraints. Conic integer programming has important applications in finance, engineering, statistical learning, and probabilistic integer programming. Here we study mixed-integer sets defined by second-order conic constraints. We describe general-purpose conic mixed-integer rounding cuts based on polyhedral conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that solve continuous conic programming relaxations at the nodes of the search tree. Our preliminary computational experiments with the new cuts show that they are quite effective in reducing the integrality gap of continuous relaxations of conic mixed-integer programs. }, doi = {http://dx.doi.org/10.1007/978-3-540-72792-7_2}, fbooktitle = {Integer Programming and Combinatorial Optimization, 12th International {IPCO} Conference, {I}thaca, {NY}, {USA}, {J}une 25-27, 2007, {P}roceedings}, isbn = {978-3-540-72791-0}, url = {http://www.springerlink.com/content/f28m4175j74n5125/} } @ARTICLE{Bonami2008Framework, author = {Bonami, Pierre and Biegler, Lorenz T. and Conn, Andrew R. and Cornu{\'e}jols, G{\'e}rard and Grossmann, Ignacio E. and Laird, Carl D. and Lee, Jon and Lodi, Andrea and Margot, Fran{\c{c}}ois and Sawaya, Nicolas and W{\"a}chter, Andreas}, title = {An algorithmic framework for convex mixed integer nonlinear programs}, journal = {Discrete Optim.}, year = {2008}, volume = {5}, pages = {186--204}, number = {2}, abstract = {This paper is motivated by the fact that mixed integer nonlinear programming is an important and difficult area for which there is a need for developing new methods and software for solving large-scale problems. Moreover, both fundamental building blocks, namely mixed integer linear programming and nonlinear programming, have seen considerable and steady progress in recent years. Wishing to exploit expertise in these areas as well as on previous work in mixed integer nonlinear programming, this work represents the first step in an ongoing and ambitious project within an open-source environment. COIN-OR is our chosen environment for the development of the optimization software. A class of hybrid algorithms, of which branch-and-bound and polyhedral outer approximation are the two extreme cases, are proposed and implemented. Computational results that demonstrate the effectiveness of this framework are reported. Both the library of mixed integer nonlinear problems that exhibit convex continuous relaxations, on which the experiments are carried out, and a version of the software used are publicly available. }, doi = {http://dx.doi.org/10.1016/j.disopt.2006.10.011}, fjournal = {Discrete Optimization. The Journal of Combinatorial Operations Research}, issn = {1572-5286}, mrclass = {90C30 (90C10)}, mrnumber = {MR2408416}, url = {http://www.ams.org/mathscinet-getitem?mr=2408416} } @BOOK{Boyd2004Book, title = {Convex optimization}, publisher = {Cambridge University Press}, year = {2004}, author = {Boyd, Stephen and Vandenberghe, Lieven}, pages = {xiv+716}, address = {Cambridge}, isbn = {0-521-83378-7}, mrclass = {90-01 (90C05 90C25 90C46 90C51)}, mrnumber = {MR2061575 (2005d:90002)}, mrreview = {During the last decade we were blessed with many books on convex optimization. Some of them present the main results and methods of convex optimization from interesting, new viewpoints. Others focus on specific topics and go deep into the theory and applications of various classes of methods for solving convex programming problems. Most of them are well written treatises addressed to readers able to handle advanced mathematical tools. Few of those books are really intended to be text books for the uninitiated in the subtleties of the theory and applications of mathematical programming and even fewer are written with the economy of mathematical pre-requisites which will make them accessible to practitioners without advanced mathematical training. The book by Boyd and Vandenberghe reviewed here is one of those few and, in this class, the best I have ever seen. It complements two other outstanding text books of convex optimization: that of D. P. Bertsekas [Nonlinear programming, second edition, Athena Scientific, Belmont, MA, 1999; Zbl 1015.90077], which is accessible to readers with undergraduate level of mathematical training in analysis and algebra, and that of A. Ben-Tal and A. Nemirovskii [Lectures on modern convex optimization, SIAM, Philadelphia, PA, 2001; MR1857264 (2003b:90002)], which is addressed to postgraduate students and researchers ``in possession of the basic elements of mathematical culture'' [cf. A. Ben-Tal and A. Nemirovskii, op. cit. (p. xvi)]. These three books represent the three stairs the student should climb in order to enter the world of the modern theory of optimization and learn the basics of the art of modelling and solving practical optimization problems. The book under review should be the first the student will climb. It is a gentle, but rigorous, introduction to the basic concepts and methods of the field. It starts with the elementary notions of convex analysis, it continues with the most fundamental concepts of optimization theory (the Lagrange dual function and problem, the Karush-Kuhn-Tucker conditions, etc.) and, via well chosen and explained models of optimization problems, it reaches the question of how to compute solutions of unconstrained and constrained optimization problems. At this stage descent methods, Newton's method and the logarithmic barrier interior-point method are discussed and the reader is initiated in the art of optimization problem solving. It is at this stage when the reader is confronted with the subtleties and difficulties of the iterative optimization techniques (the choice of a ``good'' initial point, speed of convergence, complexity). As I said before, this book is meant to be a ``first book'' for the student or practitioner of optimization. However, I think that even the experienced researcher in the field has something to gain from reading this book: I have very much enjoyed the easy to follow presentation of many meaningful examples and suggestive interpretations meant to help the student's understanding penetrate beyond the surface of the formal description of the concepts and techniques. For teachers of convex optimization this book can be a gold mine of exercises. Exercises can be found at the end of each chapter, arranged by topic and ordered according to the degree of difficulty. I have tried to solve some of those exercises and I have to confess that some of them were not ``easy''. Since this work is equally addressed to students and to practitioners in various domains, it would have been nice if this book would have included solutions (explained in full details) of some (if not of all) exercises. Boyd's and Vandenberghe's book is a work of initiation. However, for those interested to further investigate the problems and the methods the book approaches, the bibliographic notes at the end of each chapter can be very useful because they point to the best sources of information on each topic. The book also contains 50 pages of ``appendices'' supposed to provide the pre-requisites of mathematics. The presentation of the mathematical notions there makes for pleasant and informative reading, too. When recommending this book to students, one should take care to advise them to read Appendix C first. Some of the topics covered there are not necessarily (central) parts of their regular mathematics training. }, mrreviewer = {Dan Butnariu}, url = {http://www.ams.org/mathscinet-getitem?mr=2061575} } @BOOK{Cornuejols2007Book, title = {Optimization methods in finance}, publisher = {Cambridge University Press}, year = {2007}, author = {Cornuejols, Gerard and T{\"u}t{\"u}nc{\"u}, Reha}, pages = {xii+345}, series = {Mathematics, Finance and Risk}, address = {Cambridge}, isbn = {978-0-521-86170-0}, mrclass = {91-01 (90C90 91B28)}, mrnumber = {MR2294029 (2007j:91001)}, url = {http://www.ams.org/mathscinet-getitem?mr=2294029} } @ARTICLE{Fletcher1994OA, author = {Fletcher, Roger and Leyffer, Sven}, title = {Solving mixed integer nonlinear programs by outer approximation}, journal = {Math. Programming}, year = {1994}, volume = {66}, pages = {327--349}, number = {3, Ser. A}, abstract = {A wide range of optimization problems arising from engineering applications can be formulated as Mixed Integer NonLinear Programming problems (MINLPs). Duran and Grossmann (1986) suggest an outer approximation scheme for solving a class of MINLPs that are linear in the integer variables by a finite sequence of relaxed MILP master programs and NLP subproblems. Their idea is generalized by treating nonlinearities in the integer variables directly, which allows a much wider class of problem to be tackled, including the case of pure INLPs. A new and more simple proof of finite termination is given and a rigorous treatment of infeasible NLP subproblems is presented which includes all the common methods for resolving infeasibility in Phase I. The worst case performance of the outer approximation algorithm is investigated and an example is given for which it visits all integer assignments. This behaviour leads us to include curvature information into the relaxed MILP master problem, giving rise to a new quadratic outer approximation algorithm. An alternative approach is considered to the difficulties caused by infeasibility in outer approximation, in which exact penalty functions are used to solve the NLP subproblems. It is possible to develop the theory in an elegant way for a large class of nonsmooth MINLPs based on the use of convex composite functions and subdifferentials, although an interpretation for the L1 norm is also given. }, coden = {MHPGA4}, doi = {http://dx.doi.org/10.1007/BF01581153}, fjournal = {Mathematical Programming}, issn = {0025-5610}, mrclass = {90C11}, mrnumber = {MR1297070 (95h:90083)}, mrreview = {The paper deals with the problem of solving the mixed integer nonlinear programming problem (P) $\min f(x,y)$, subject to $g(x,y)\leq 0$, $x\in X$, $y$ is an integer, where $X$ is a nonempty compact convex set defined by a system of linear inequality constraints, $f$ and $g$ are convex and once continuously differentiable, and a constraint qualification holds at the solution of every NLP subproblem which is obtained from (P) by fixing the integer variables $y$. A finite algorithm, that generalises Duran and Grossmann's outer approximation scheme, for the case when (P) is nonlinear in the integer variable, is given with a treatment of an infeasible NLP subproblem. In order to avoid the worst case performance that may occur when all integer assignments are visited, a new quadratic outer approximation is suggested. An outer approximation algorithm for nonsmooth problems is also presented. }, mrreviewer = {Vincen{\c{t}}iu Dumitru}, url = {http://www.ams.org/mathscinet-getitem?mr=1297070} } @ARTICLE{Frangioni2006Perspective, author = {Frangioni, A. and Gentile, C.}, title = {Perspective cuts for a class of convex 0-1 mixed integer programs}, journal = {Math. Program.}, year = {2006}, volume = {106}, pages = {225--236}, number = {2, Ser. A}, abstract = {We show that the convex envelope of the objective function of Mixed-Integer Programming problems with a specific structure is the perspective function of the continuous part of the objective function. Using a characterization of the subdifferential of the perspective function, we derive ``perspective cuts'', a family of valid inequalities for the problem. Perspective cuts can be shown to belong to the general family of disjunctive cuts, but they do not require the solution of a potentially costly nonlinear programming problem to be separated. Using perspective cuts substantially improves the performance of Branch & Cut approaches for at least two models that, either ``naturally'' or after a proper reformulation, have the required structure: the Unit Commitment problem in electrical power production and the Mean-Variance problem in portfolio optimization. }, doi = {http://dx.doi.org/10.1007/s10107-005-0594-3}, fjournal = {Mathematical Programming. A Publication of the Mathematical Programming Society}, issn = {0025-5610}, mrclass = {90C11 (90C20 90C57)}, mrnumber = {MR2208082 (2006j:90046)}, mrreview = {The authors show that the convex envelope of the objective function of mixed-integer programming problems with a specific structure is the perspective function of the continuous part of the objective function. This structure corresponds to a mixed-integer program of the form: (1) $\min{f(p)+cu: Ap\leq bu, u\in {0,1}}$, where $p\in \Bbb R^n$, $A\in \Bbb R^{m\times n}$ and $b\in \Bbb R^m$ are such that ${p: Ap\leq 0}={0}$. It is assumed that $\scr P={p\in \Bbb R^n: Ap\leq b}$ is a compact set, and that $f\colon \Bbb R^n\rightarrow \Bbb R$ is a closed convex function that is finite on $\scr P$. The binary variable $u$ decides whether $p=0$ or $p\in \scr P$ at the fixed cost $c$. Usually, (1) is a small fragment of a larger problem. By using a characterization of the subdifferential of the perspective function, perspective cuts are derived. They are a family of valid inequalities for the original problem. These cuts turn out to be a special case of the disjunctive cuts. In Sections 3 and 4, the authors discuss the use of the valid inequalities within a branch and cut approach for two mixed-integer quadratic problems: the unit commitment problem in electrical power production and the mean-variance model in portfolio optimization. In particular, implementation details and computational results are presented. }, mrreviewer = {Klaus Hofstedt}, url = {http://www.ams.org/mathscinet-getitem?mr=2208082} } @ARTICLE{Goemans1995Maxcut, author = {Goemans, Michel X. and Williamson, David P.}, title = {Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming}, journal = {J. Assoc. Comput. Mach.}, year = {1995}, volume = {42}, pages = {1115--1145}, number = {6}, abstract = {We present randomized approximation algorithms for the maximum cut (MAX CUT) and maximum 2-satisfiability (MAX 2SAT) problems that always deliver solutions of expected value at least .87856 times the optimal value. These algorithms use a simple and elegant technique that randomly rounds the solution to a nonlinear programming relaxation. This relaxation can be interpreted both as a semidefinite program and as an eigenvalue minimization problem. The best previously known approximation algorithms for these problems had perfc~rmance guarantees of $\frac{1}{2}$ for MAX CUT and $\frac{3}{4}$ for MAX 2SAT. Slight extensions of our analysis lead to a .79607-approximation algorithm for the maximum directed cut problem (MAX DICUT) and a .758-approximation algorithm for MAX SAT, where the best previously known approxim ation algorithms had performance guarantees of $\frac{1}{4}$ and $\frac{3}{4}$, respectively. Our algorithm gives the first substantial progress in approximating MAX CUT in nearly twenty years, and represents the first use of semidefinite programming in the design of approximation algorithms. }, coden = {JACOAH}, doi = {http://dx.doi.org/10.1145/227683.227684}, fjournal = {Journal of the Association for Computing Machinery}, issn = {0004-5411}, mrclass = {90C27 (68Q25 90C35)}, mrnumber = {MR1412228 (97g:90108)}, mrreview = {The maximum cut problem (MAX CUT) consists in finding a set of vertices $\bold S \subset {V}$ of a graph $\bold G=(V,E)$ that maximizes the weight of the edges in the cut $(\bold S,\widetilde {S})$. An analytical model $\scr Q$ of the problem is presented in the form $\max 0.5\sum_{i 0$. The solution obtained differs from the optimal one by less than $\epsilon$ [see F. Alizadeh, SIAM J. Optim. 5 (1995), no. 1, 13--51; MR1315703 (95k:90065)]. The authors prove that the expected weight of the cut defined by the random hyperplane with normal vector $r$ satisfies $\bold E[W] \geq \alpha ·\bold W$, where ${\bold W}$ is the value of the objective function received by solving $\scr R$, and $\alpha$ is constant, $\alpha > 0.878$. The proposed approach is extended to some other problems (the constant $\alpha$ is different for them): MAX RES CUT, a problem in which pairs of vertices are forced to be on the same side of the cut ($\alpha$ remains the same); the well-known problem MAX SAT $(\alpha > 0.758)$; MAX 2SAT, consisting of MAX SAT instances in which each clause has length at most two ($\alpha$ is the same as for the initial problem MAX CUT); MAX DICUT, the maximum directed cut problem ($\alpha > 0.796$). }, mrreviewer = {Nikolay N. Ivanov}, url = {http://www.ams.org/mathscinet-getitem?mr=1412228} } @ARTICLE{Grossmann2002Review, author = {Ignacio E. Grossmann}, title = {Review of nonlinear mixed-integer and disjunctive programming techniques}, journal = {Optim. Eng.}, year = {2002}, volume = {3}, pages = {227--252}, number = {3}, abstract = {This paper has as a major objective to present a unified overview and derivation of mixed-integer nonlinear programming (MINLP) techniques, Branch and Bound, Outer-Approximation, Generalized Benders and Extended Cutting Plane methods, as applied to nonlinear discrete optimization problems that are expressed in algebraic form. The solution of MINLP problems with convex functions is presented first, followed by a brief discussion on extensions for the nonconvex case. The solution of logic based representations, known as generalized disjunctive programs, is also described. Theoretical properties are presented, and numerical comparisons on a small process network problem. }, doi = {http://dx.doi.org/10.1023/A:1021039126272}, fjournal = {Optimization and Engineering}, issn = {1389-4420}, url = {http://www.springerlink.com/content/h273130uw4277q27/} } @ARTICLE{Lee2007Issues, author = {Jon Lee}, title = {Mixed-integer nonlinear programming: Some modeling and solution issues}, journal = {IBM J. Res. Dev.}, year = {2007}, volume = {51}, pages = {489--497}, number = {3/4}, abstract = {We examine various aspects of modeling and solution via mixed-integer nonlinear programming (MINLP). MINLP has much to offer as a powerful modeling paradigm. Recently, significant advances have been made in MINLP solution software. To fully realize the power of MINLP to solve complex business optimization problems, we need to develop knowledge and expertise concerning MINLP modeling and solution methods. Some of this can be drawn from conventional wisdom of mixed-integer linear programming (MILP) and nonlinear programming (NLP), but theoretical and practical issues exist that are specific to MINLP. This paper discusses some of these, concentrating on an aspect of a classical facility location problem that is well-known in the MILP literature, although here we consider a nonlinear objective function. }, doi = {http://dx.doi.org/10.1147/rd.513.0489}, fjournal = {IBM Journal of Research and Development}, issn = {0018-8646}, url = {http://www.research.ibm.com/journal/rd/513/lee.html} } @ARTICLE{Lovasz1991Cones, author = {Lov{\'a}sz, L. and Schrijver, A.}, title = {Cones of matrices and set-functions and {$0$}-{$1$} optimization}, journal = {SIAM J. Optim.}, year = {1991}, volume = {1}, pages = {166--190}, number = {2}, abstract = {It has been recognized recently that to represent a polyhedron as the projection of a higher-dimensional, but simpler, polyhedron, is a powerful tool in polyhedral combinatorics. A general method is developed to construct higher-dimensional polyhedra (or, in some cases, convex sets) whose projection approximates the convex hull of 0-1 valued solutions of a system of linear inequalities. An important feature of these approximations is that one can optimize any linear objective function over them in polynomial time.In the special case of the vertex packing polytope, a sequence of systems of inequalities is obtained such that the first system already includes clique, odd hole, odd antihole, wheel, and orthogonality constraints. In particular, for perfect (and many other) graphs, this first system gives the vertex packing polytope. For various classes of graphs, including $t$-perfect graphs, it follows that the stable set polytope is the projection of a polytope with a polynomial number of facets. An extension of the method is also discussed which establishes a connection with certain submodular functions and the M{\"o}bius function of a lattice. }, coden = {SJOPE8}, doi = {http://dx.doi.org/10.1137/0801013}, fjournal = {SIAM Journal on Optimization}, issn = {1052-6234}, mrclass = {05C90 (90C09 90C27)}, mrnumber = {MR1098425 (92b:05072)}, mrreview = {In combinatorial optimization a fruitful approach consists in representing each feasible solution as a $0,1$-valued vector and in describing the convex hull of such vectors by a system of linear inequalities. In the best cases a system with a polynomial (in the size of the problem) number of inequalities is obtained. Generally there is an exponential number of inequalities, but in spite of this, there are nice descriptions of polyhedra for some cases (matching polyhedra, matroid polyhedra, stable set polyhedra for perfect graphs, etc.). For some of the other cases, a technique which has led to efficient solution procedures is to construct higher-dimensional polyhedra whose projection approximates the convex hull of $0,1$-valued solutions of a system of linear inequalities (this is interesting because a projection of a polytope may have more facets than the polytope itself). Such a representation can be used to optimize a linear objective function over the convex hull of the initial $0,1$-valued solutions in polynomial time. A general procedure is described to create adequate liftings of polyhedra; it is applied to the stable set problem. Raising the dimension even higher (by introducing exponentially many variables) gives a formulation where simple and elegant polyhedral properties can be derived. The main effort is to reduce the inequalities to a low dimension and to use in the algorithms only a polynomial number of variables and inequalities. }, mrreviewer = {D. de Werra}, url = {http://www.ams.org/mathscinet-getitem?mr=1098425} } @BOOK{Sherali1999Book, title = {A reformulation-linearization technique for solving discrete and continuous nonconvex problems}, publisher = {Kluwer Academic Publishers}, year = {1999}, author = {Sherali, Hanif D. and Adams, Warren P.}, volume = {31}, pages = {xxiv+514}, series = {Nonconvex Optimization and its Applications}, address = {Dordrecht}, isbn = {0-7923-5487-7}, mrclass = {90C26 (90C05 90C25)}, mrnumber = {MR1682748 (2000g:90055)}, mrreview = {The area of global optimization is an exceedingly active one, as evidenced by the rapidly accumulating literature on algorithms, computational testing, applications, and software development. This book addresses a new method for generating tight linear or convex programming relaxations for discrete and continuous nonconvex programming problems. Problems of this type arise in many economics, location-allocation, scheduling and routing, and process control and engineering design applications. The principal thrust is to commence with a model that affords a useful representation and structure, and then to further strengthen this representation through an automatic reformulation and constraint generation technique. The book under review provides very useful information to the general reader. The contents of this book comprise the original work of the authors compiled from several journal publications, and not covered in any other book on this subject. The outstanding feature of this book is that it offers for the first time a unified treatment of discrete and continuous nonconvex programming problems. In essence, the bridge between these two types of nonconvexities is made via a polynomial representation of discrete constraints. The first part of the book deals with discrete nonconvex programs. It includes material on the reformulation-linearization technique (RLT) hierarchy for mixed-integer zero-one problems, the generalized hierarchy for exploiting special structures in mixed-integer zero-one problems, the RLT hierarchy for general discrete mixed-integer problems, generating valid inequalities and facets using RLT, and persistence in discrete optimization. The second part deals with continuous nonconvex programs. The material covered includes RLT-based global optimization algorithms for nonconvex polynomial programming problems, reformulation-convexification techniques for quadratic programs and some convex envelope characterizations, and reformulation-convexification techniques for polynomial programs. The third part of the book is dedicated to special applications to discrete and continuous nonconvex programs. Readers will find the book useful and interesting. The book contains innovative material and original results in the field of nonconvex and discrete optimization from both the mathematical and the numerical point of view. }, mrreviewer = {Panos M. Pardalos}, url = {http://www.ams.org/mathscinet-getitem?mr=1682748} } @ARTICLE{Stubbs1999BC, author = {Stubbs, Robert A. and Mehrotra, Sanjay}, title = {A branch-and-cut method for {$0$}-{$1$} mixed convex programming}, journal = {Math. Program.}, year = {1999}, volume = {86}, pages = {515--532}, number = {3, Ser. A}, abstract = {We generalize the disjunctive approach of Balas, Ceria, and Cornu{\'e}jols [2] and devevlop a branch-and-cut method for solving 0-1 convex programming problems. We show that cuts can be generated by solving a single convex program. We show how to construct regions similar to those of Sherali and Adams [20] and Lov{\'a}sz and Schrijver [12] for the convex case. Finally, we give some preliminary computational results for our method. }, doi = {http://dx.doi.org/10.1007/s101070050103}, fjournal = {Mathematical Programming. A Publication of the Mathematical Programming Society}, issn = {0025-5610}, mrclass = {90C09 (90C59)}, mrnumber = {MR1733745 (2000j:90022)}, mrreview = {Consider the mixed zero-one convex programming problem (MICP): minimize $c^\ssf Tx$ subject to $g_i(x)\leq 0$, $i=1,\cdots,m, x_i\in{0,1}$, $i=1,\cdots,p$, where $c,x\in\bold R^n$, $g_i(x):\bold R^n\to\bold R$ for $i=1,\cdots,m$ are convex functions, and $p\leq n$. The authors generalize the disjunctive approach of E. Balas, S. Ceria and G. Cornu{\'e}jols [Math. Programming 58 (1993), no. 3, Ser. A, 295--324; MR1216789 (94b:90046)] and present a branch-and-cut method for solving (MICP). In Section 2, the theory for generating separating hyperplanes is developed, and it is shown that the resulting separation problem can be reduced to a convex optimization problem. In Section 3, the authors describe how to generate valid inequalities that cut away a given solution. Section 4 provides representations of sets similar to those used by H. D. Sherali and W. P. Adams [SIAM J. Discrete Math. 3 (1990), no. 3, 411--430; MR1061981 (91k:90116)] for the convex case. A branch-and-cut procedure for solving (MICP) is described in Section 5, and it is shown that cuts at any node of the branch-and-bound tree can be lifted for the entire tree. Finally, preliminary computational results are given in Section 6 using four examples with $6\leq n\leq 30$, $3\leq p\leq 25$, $6\leq m\leq 30$ and ${\rm NP}