Optimization Over Integers.pdf
Linda Berens
1 Optimization over Integers Dimitris Bertsimas Massachusetts Institute of Technology Robert Weismantel University of Magdeburg Technische Universitat Darmstadt Fachbereich 1 Betriebswirtschaftliche Bibliothek Inventar-Nr.: Abstell-Nr.: Dynamic Ideas, Belmont, Massachusetts
2 1 Formulations Modeling techniques Guidelines for strong formulations Modeling with exponentially many constraints Modeling with exponentially many variables Summary Exercises Notes and sources 33 2 Methods to enhance formulations Methods to generate valid inequalities Methods to generate facet defining inequalities Valid inequalities in independence systems On the strength of valid inequalities Nonlinear formulations Summary Exercises.'' Notes and sources 76 3 Ideal formulations Total unimodularity Dual methods Randomized rounding methods The minimal counterexample method The method of lift and project Ill 3.6 Summary Exercises Notes and sources Duality in integer optimization Duality of binary optimization Superadditive duality Lagrangean duality Geometry and solution of Lagrangean duals 149 vii
3 viii 4.5 Summary Exercises Notes and sources Algorithms for solving relaxations The key geometric result behind the ellipsoid method The ellipsoid method for the feasibility problem The ellipsoid method for optimization From separation to optimization Summary Exercises Notes and sources Lattices and their applications Integer points in lattices Reduced bases for lattices Simultaneous diophantine approximation The approximate nearest vector problem The maximum volume inscribed ellipsoid Integer optimization in fixed dimension Summary Exercises Notes and sources Algebraic geometry and integer optimization Background from algebraic geometry Applications to binary optimization Grobner bases for integer optimization Applications of real algebraic geometry Generating functions for integer points in polyhedra Summary Exercises Notes and sources Geometry of integer optimization Definitions and examples Integral generating sets in cones Optimality conditions From cones to polyhedra Algorithms to compute integral generating sets Total dual integrality Summary Exercises Notes and sources 323
4 ix 9 Cutting plane methods Cutting planes from integral generating sets The Gomory cutting plane algorithm Cutting planes based on lattices The convex hull of solutions Summary Exercises Notes and sources The integral basis method Dynamic reformulation methods An integer simplex algorithm The integral basis method Algebraic reformulation strategies Combinatorial reformulation strategies Summary Exercises Notes and sources Enumerative and heuristic methods Branch and bound Optimization based heuristic methods Dynamic programming Approximate dynamic programming Local search Simulated annealing Summary Exercises Notes and sources Approximation algorithms Primal-dual methods Cut covering problems Randomized rounding of linear relaxations Randomized rounding of convex relaxations Approximation schemes Limitations in approximability Summary Exercises Notes and sources Mixed integer optimization The mixed integer Farkas lemma Mixed integer lattices Mixed integer optimality conditions Reformulations for mixed integer sets 500
5 x 13.5 Cutting planes for mixed integer optimization Summary Exercises Notes and Sources Robust discrete optimization Robust mixed integer optimization Robust binary optimization Robust network flows Robust inventory theory Summary Exercises Notes and sources 549 A Elements of polyhedral theory 551 A.I Cones 552 A.2 Dimension of polyhedra 553 A.3 Valid inequalities 555 A.4 Exercises 558 B Efficient algorithms and complexity theory 559 B.I Efficient algorithms 560 B.2 Complexity theory 563 References 571 Index 595
1 A NEW LOOK AT CONVEX ANALYSIS AND OPTIMIZATION Dimitri Bertsekas M.I.T. FEBRUARY 2003 2 OUTLINE Convexity issues in optimization Historical remarks Our treatment of the subject Three unifying lines of
2014-2015 The Master s Degree with Thesis Course Descriptions in Industrial Engineering Compulsory Courses IENG540 Optimization Models and Algorithms In the course important deterministic optimization
L. Vandenberghe EE236C (Spring 23-4) Proximal mapping via network optimization minimum cut and maximum flow problems parametric minimum cut problem application to proximal mapping Introduction this lecture:
A Robust Formulation of the Uncertain Set Covering Problem Dirk Degel Pascal Lutter Chair of Management, especially Operations Research Ruhr-University Bochum Universitaetsstrasse 150, 44801 Bochum, Germany
Noncommercial Software for Mixed-Integer Linear Programming J. T. Linderoth T. K. Ralphs December, 2004. Revised: January, 2005. Abstract We present an overview of noncommercial software tools for the
An Overview Of Software For Convex Optimization Brian Borchers Department of Mathematics New Mexico Tech Socorro, NM 87801 borc...@nmt.edu In fact, the great watershed in optimization isn t between linearity
Nonlinear Optimization: Algorithms 3: Interior-point methods INSEAD, Spring 2006 Jean-Philippe Vert Ecole des Mines de Paris Jean-Phil...@mines.org Nonlinear optimization c 2006 Jean-Philippe Vert,
Mathematical finance and linear programming (optimization) Geir Dahl September 15, 2009 1 Introduction The purpose of this short note is to explain how linear programming (LP) (=linear optimization) may
Hub Cover and Hub Center Problems Horst W. Hamacher, Tanja Meyer Department of Mathematics, University of Kaiserslautern, Gottlieb-Daimler-Strasse, 67663 Kaiserslautern, Germany Abstract Using covering
PREPRINT Route optimization applied to school transports A method combining column generation with greedy heuristics Mikael Andersson Peter Lindroth Department of Mathematics CHALMERS UNIVERSITY OF TECHNOLOGY
A Log-Robust Optimization Approach to Portfolio Management Ban Kawas Aurélie Thiele December 2007, revised August 2008, December 2008 Abstract We present a robust optimization approach to portfolio management
MASTER S THESIS Recovery of primal solutions from dual subgradient methods for mixed binary linear programming; a branch-and-bound approach PAULINE ALDENVIK MIRJAM SCHIERSCHER Department of Mathematical
Optimization in R n Introduction Rudi Pendavingh Eindhoven Technical University Optimization in R n, lecture Rudi Pendavingh (TUE) Optimization in R n Introduction ORN / 4 Some optimization problems designing
The purpose of this book is to provide a unified, insightful, and modern treatment of the theory of integer optimization with an eye towards the future. We have selected those topics that we feel have influenced the current state of the art and most importantly we feel will affect the future of the field. We depart from earlier treatments of integer optimization by placing significant emphasis on strong formulations, duality, algebra and most importantly geometry.
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints (other than the integer constraints) are linear.
The feasible integer points are shown in red, and the red dashed lines indicate their convex hull, which is the smallest convex polyhedron that contains all of these points. The blue lines together with the coordinate axes define the polyhedron of the LP relaxation, which is given by the inequalities without the integrality constraint. The goal of the optimization is to move the black dashed line as far upward while still touching the polyhedron. The optimal solutions of the integer problem are the points ( 1 , 2 ) \displaystyle (1,2) and ( 2 , 2 ) \displaystyle (2,2) that both have an objective value of 2. The unique optimum of the relaxation is ( 1.8 , 2.8 ) \displaystyle (1.8,2.8) with objective value of 2.8. If the solution of the relaxation is rounded to the nearest integers, it is not feasible for the ILP.
Another class of algorithms are variants of the branch and bound method. For example, the branch and cut method that combines both branch and bound and cutting plane methods. Branch and bound algorithms have a number of advantages over algorithms that only use cutting planes. One advantage is that the algorithms can be terminated early and as long as at least one integral solution has been found, a feasible, although not necessarily optimal, solution can be returned. Further, the solutions of the LP relaxations can be used to provide a worst-case estimate of how far from optimality the returned solution is. Finally, branch and bound methods can be used to return multiple optimal solutions.
It is often the case that the matrix A \displaystyle A that defines the integer program is sparse. In particular, this occurs when the matrix has a block structure, which is the case in many applications. The sparsity of the matrix can be measured as follows. The graph of A \displaystyle A has vertices corresponding to columns of A \displaystyle A , and two columns form an edge if A \displaystyle A has a row where both columns have nonzero entries. Equivalently, the vertices correspond to variables, and two variables form an edge if they share an inequality. The sparsity measure d \displaystyle d of A \displaystyle A is the minimum of the tree-depth of the graph of A \displaystyle A and the tree-depth of the graph of the transpose of A \displaystyle A . Let a \displaystyle a be the numeric measure of A \displaystyle A defined as the maximum absolute value of any entry of A \displaystyle A . Let n \displaystyle n be the number of variables of the integer program. Then it was shown in 2018[24] that integer programming can be solved in strongly polynomial and fixed-parameter tractable time parameterized by a \displaystyle a and d \displaystyle d . That is, for some computable function f \displaystyle f and some constant k \displaystyle k , integer programming can be solved in time f ( a , d ) n k \displaystyle f(a,d)n^k . In particular, the time is independent of the right-hand side b \displaystyle b and objective function c \displaystyle c . Moreover, in contrast to the classical result of Lenstra, where the number n \displaystyle n of variables is a parameter, here the number n \displaystyle n of variables is a variable part of the input.
e2b47a7662