On the relative strength of families of intersection cuts arising from pairs of tableau constraints in mixed integer programs

  • Yogesh Awate
  • Gérard Cornuéjols
  • Bertrand Guenin
  • Levent Tunçel
    • Categories (Mixed) Integer Linear Programming Tags , ,

    We compare the relative strength of valid inequalities for the integer hull of the feasible region of mixed integer linear programs with two equality constraints, two unrestricted integer variables and any number of nonnegative continuous variables. In particular, we prove that the closure of Type~2 triangle (resp. Type~3 triangle; quadrilateral) inequalities, are all within a … Read more

    A framework for automated PDE-constrained optimisation

  • P. E. Farrell
  • S. W. Funke
    • Categories Problem Solving Environments Tags , , , , ,

    A generic framework for the solution of PDE-constrained optimisation problems based on the FEniCS system is presented. Its main features are an intuitive mathematical interface, a high degree of automation, and an efficient implementation of the generated adjoint model. The framework is based upon the extension of a domain-specific language for variational problems to cleanly … Read more

    An Augmented Lagrangian Method for Conic Convex Programming

  • Necdet Serhat Aybat
  • Garud Iyengar
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We propose a new first-order augmented Lagrangian algorithm ALCC for solving convex conic programs of the form min{rho(x)+gamma(x): Ax-b in K, x in chi}, where rho and gamma are closed convex functions, and gamma has a Lipschitz continuous gradient, A is mxn real matrix, K is a closed convex cone, and chi is a “simple” … Read more

    Risk-Averse Stochastic Dual Dynamic Programming

  • Vaclav Kozmik
  • David P. Morton
    • Categories Stochastic Programming Tags , , ,

    We formulate a risk-averse multi-stage stochastic program using conditional value at risk as the risk measure. The underlying random process is assumed to be stage-wise independent, and a stochastic dual dynamic programming (SDDP) algorithm is applied. We discuss the poor performance of the standard upper bound estimator in the risk-averse setting and propose a new … Read more

    Exact algorithms for the Traveling Salesman Problem with Draft Limits

  • Maria Battarra
  • Artur Alves Pessoa
  • Anand Subramanian
  • Eduardo Uchoa
    • Categories Branch and Cut Algorithms, Integer Programming Tags , , , ,

    This paper deals with the Traveling Salesman Problem (TSP) with Draft Limits (TSPDL), which is a variant of the well-known TSP in the context of maritime transportation. In this recently proposed problem, draft limits are imposed due to restrictions on the port infrastructures. Exact algorithms based on three mathematical formulations are proposed and their performance … Read more

    Computational aspects of simplex and MBU-simplex algorithms using different anti-cycling pivot rules

  • Nagy Adrienn
  • Tibor Illés
    • Categories Linear Programming, Optimization Software Benchmark Tags , , ,

    Several variations of index selection rules for simplex type algorithms for linear programming, like the Last-In-First-Out or the Most-Often-Selected-Variable are rules not only theoretically finite, but also provide significant flexibility in choosing a pivot element. Based on an implementation of the primal simplex and the monotonic build-up (MBU) simplex method, the practical benefit of the … Read more

    The s-Monotone Index Selection Rule for Criss-Cross Algorithms of Linear Complementarity Problems

  • Nagy Adrienn
  • Zsolt Csizmadia
  • Tibor Illés
    • Categories Complementarity and Variational Inequalities, Linear, Cone and Semidefinite Programming Tags , , ,

    In this paper we introduce the s-monotone index selection rules for the well-known crisscross method for solving the linear complementarity problem (LCP). Most LCP solution methods require a priori information about the properties of the input matrix. One of the most general matrix properties often required for finiteness of the pivot algorithms (or polynomial complexity … Read more

    The Trust Region Subproblem with Non-Intersecting Linear Constraints

  • Samuel Burer
  • Boshi Yang
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming, Second-Order Cone Programming Tags , , ,

    This paper studies an extended trust region subproblem (eTRS)in which the trust region intersects the unit ball with m linear inequality constraints. When m=0, m=1, or m=2 and the linear constraints are parallel, it is known that the eTRS optimal value equals the optimal value of a particular convex relaxation, which is solvable in polynomial … Read more

    Composite Retrieval of Diverse and Complementary Bundles

  • Sihem Amer-Yahia
  • Carlos Castillo
  • Isabel Méndez-Díaz
  • Francesco Bonchi
  • Esteban Feuerstein
  • Paula Zabala
    • Categories Applications - OR and Management Sciences

    Users are often faced with the problem of finding complementary items that together achieve a single common goal (e.g., a starter kit for a novice astronomer, a collection of question/answers related to low-carb nutrition, a set of places to visit on holidays). In this paper, we argue that for some application scenarios returning item bundles … Read more

    Optimal Power Grid Protection through A Defender-Attacker-Defender Model

  • Wei Yuan
  • Bo Zeng
  • Long Zhao
    • Categories Applications - Science and Engineering, Game Theory

    Power grid vulnerability is a major concern of modern society, and its protection problem is often formulated as a tri-level defender-attacker-defender model. However, this tri-level problem is compu- tationally challenging. In this paper, we design and implement a Column-and-Constraint Generation algorithm to derive its optimal solutions. Numerical results on an IEEE system show that: (i) … Read more