Integer Programming

Path Cover and Path Pack Inequalities for the Capacitated Fixed-Charge Network Flow Problem

  • Alper Atamturk
  • Simge Küçükyavuz
  • Birce Tezel
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , ,

    Capacitated fixed-charge network flows are used to model a variety of problems in telecommunication, facility location, production planning and supply chain management. In this paper, we investigate capacitated path substructures and derive strong and easy-to-compute path cover and path pack inequalities. These inequalities are based on an explicit characterization of the submodular inequalities through a … Read more

    Global Solution Strategies for the Network-Constrained Unit Commitment Problem With AC Transmission Constraints

  • Anya Castillo
  • Carl D. Laird
  • Jean-Paul Watson
  • Jianfeng Liu
    • Categories Global Optimization, Integer Programming, Nonlinear Optimization Tags , ,

    We propose a novel global solution algorithm for the network-constrained unit commitment problem that incorporates a nonlinear alternating current model of the transmission network, which is a nonconvex mixed-integer nonlinear programming (MINLP) problem. Our algorithm is based on the multi-tree global optimization methodology, which iterates between a mixed-integer lower-bounding problem and a nonlinear upper-bounding problem. … Read more

    Generalized average shadow prices and bottlenecks

  • Alejandro Crema
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences Tags , , ,

    We present a generalization of the average shadow price in 0-1-Mixed Integer Linear Programming problems and its relation with bottlenecks including the analysis relative to the coefficients matrix of resource constraints. A mathematical programming approach to find the strategy for investment in resources is presented. CitationEscuela de Computación, Facultad de Ciencias, Universidad Central de VenezuelaArticleDownload … Read more

    The (not so) Trivial Lifting in Two Dimensions

  • Ricardo Fukasawa
  • Laurent Poirrier
  • Alinson S. Xavier
    • Categories (Mixed) Integer Linear Programming Tags ,

    When generating cutting-planes for mixed-integer programs from multiple rows of the simplex tableau, the usual approach has been to relax the integrality of the non-basic variables, compute an intersection cut, then strengthen the cut coefficients corresponding to integral non-basic variables using the so-called trivial lifting procedure. Although of polynomial-time complexity in theory, this lifting procedure … Read more

    Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations

  • Robert Hildebrand
  • Robert Weismantel
  • Rico Zenklusen
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization Tags ,

    We prove that any mixed-integer linear extended formulation for the matching polytope of the complete graph on $n$ vertices, with a polynomial number of constraints, requires $\Omega(\sqrt{\sfrac{n}{\log n}})$ many integer variables. By known reductions, this result extends to the traveling salesman polytope. This lower bound has various implications regarding the existence of small mixed-integer mathematical … Read more

    A Complete Characterization of Disjunctive Conic Cuts for Mixed Integer Second Order Cone Optimization

  • Pietro Belotti
  • Julio C. Góez
  • Imre Pólik
  • Ted K. Ralphs
  • Tamás Terlaky
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming Tags , ,

    We study the convex hull of the intersection of a disjunctive set defined by parallel hyperplanes and the feasible set of a mixed integer second order cone optimization problem. We extend our prior work on disjunctive conic cuts, which has thus far been restricted to the case in which the intersection of the hyperplanes and … Read more

    Lattice closures of polyhedra

  • Sanjeeb Dash
  • Oktay Gunluk
  • Diego Moran Ramirez
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , , ,

    Given $P\subset\R^n$, a mixed-integer set $P^I=P\cap (\Z^{t}\times\R^{n-t}$), and a $k$-tuple of $n$-dimensional integral vectors $(\pi_1, \ldots, \pi_k)$ where the last $n-t$ entries of each vector is zero, we consider the relaxation of $P^I$ obtained by taking the convex hull of points $x$ in $P$ for which $ \pi_1^Tx,\ldots,\pi^T_kx$ are integral. We then define the $k$-dimensional … Read more

    Novel formulations for general and security Stackelberg games

  • Carlos Casorrán
  • Bernard Fortz
  • Martine Labbé
  • Fernando Ordóñez
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Polyhedra Tags , , ,

    In this paper we analyze general Stackelberg games (SGs) and Stackelberg security games (SSGs). SGs are hierarchical adversarial games where players select actions or strategies to optimize their payoffs in a sequential manner. SSGs are a type of SGs that arise in security applications, where the strategies of the player that acts first consist in … Read more

    A Spatial Branch-and-Cut Method for Nonconvex QCQP with Bounded Complex Variables

  • Alper Atamturk
  • Shmuel Oren
  • Chen Chen
    • Categories (Mixed) Integer Nonlinear Programming

    We develop a spatial branch-and-cut approach for nonconvex Quadratically Constrained Quadratic Programs with bounded complex variables (CQCQP). Linear valid inequalities are added at each node of the search tree to strengthen semidefinite programming relaxations of CQCQP. These valid inequalities are derived from the convex hull description of a nonconvex set of $2 \times 2$ positive … Read more

    Branch-and-bound for biobjective mixed-integer linear programming

  • Nathan Adelgren
  • Akshay Gupte
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Multi-Criteria Optimization Tags , , , ,

    We present a generic branch-and-bound algorithm for finding all the Pareto solutions of a biobjective mixed-integer linear program. The main contributions are new algorithms for obtaining dual bounds at a node, checking node fathoming, presolve, and duality gap measurement. Our branch-and-bound is predominantly a decision space search method because the branching is performed on the … Read more