Month: April 2016

Bi-objective branch–and–cut algorithms: Applications to the single source capacitated facility location problem

  • Matthias Ehrgott
  • Sune Lauth Gadegaard
  • Lars Relund Nielsen
    • Categories Branch and Cut Algorithms, Multi-Criteria Optimization Tags , , ,

    Most real–world optimization problems are of a multi–objective nature, involving objectives which are conflicting and incomparable. Solving a multi–objective optimization problem requires a method which can generate the set of rational compromises between the objectives. In this paper, we propose two distinct bound set based branch–and–cut algorithms for bi–objective combinatorial optimization problems, based on implicitly … Read more

    Stochastic geometric optimization with joint probabilistic constraints

  • Zhiping Chen
  • Abdel Lisser
  • Jia Liu
    • Categories Stochastic Programming Tags , , ,

    This paper discusses geometric programs with joint probabilistic constraints. When the stochastic parameters are normally distributed and independent of each other, we approximate the problem by using piecewise polynomial functions with non-negative coefficients, and transform the approximation problem into a convex geometric program. We prove that this approximation method provides a lower bound. Then, we … Read more

    A Non-metric Bilevel Location Problem

  • Claudio Arbib
  • Matteo Tonelli
    • Categories Applications - OR and Management Sciences, Facility Planning and Design, Finance and Economics Tags , ,

    We address a bilevel location problem where a leader first decides which facilities to open and their access prices; then, customers make individual decisions minimizing individual costs. In this note we prove that, when access costs do not fulfill metric properties, the problem is NP-hard even if facilities can be opened at no fixed cost. … Read more

    Robust Multiclass Queuing Theory for Wait Time Estimation in Resource Allocation Systems

  • Chaithanya Bandi
  • Nikolaos Trichakis
  • Phebe Vayanos
    • Categories Applications - OR and Management Sciences, Robust Optimization

    In this paper we study systems that allocate different types of scarce resources to heterogeneous allocatees based on predetermined priority rules, e.g., the U.S. deceased-donor kidney allocation system or the public housing program. We tackle the problem of estimating the wait time of an allocatee who possesses incomplete system information with regard, for example, to … Read more

    Penalty Alternating Direction Methods for Mixed-Integer Optimization: A New View on Feasibility Pumps

  • Björn Geißler
  • Antonio Morsi
  • Lars Schewe
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , ,

    Feasibility pumps are highly effective primal heuristics for mixed-integer linear and nonlinear optimization. However, despite their success in practice there are only few works considering their theoretical properties. We show that feasibility pumps can be seen as alternating direction methods applied to special reformulations of the original problem, inheriting the convergence theory of these methods. … Read more

    Low-Complexity Relaxations and Convex Hulls of Disjunctions on the Positive Semidefinite Cone and General Regular Cones

  • Fatma Kılınç-Karzan
  • Sercan Yildiz
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    In this paper we analyze general two-term disjunctions on a regular cone $\K$ and derive a general form for a family of convex inequalities which are valid for the resulting nonconvex sets. Under mild technical assumptions, these inequalities collectively describe the closed convex hulls of these disjunctions, and if additional conditions are satisfied, a single … Read more

    Combinatorial Benders Cuts for Assembly Line Balancing Problems with Setups

  • Sener Akpinar
  • Tolga Bektas
  • Atabak Elmi
    • Categories Combinatorial Optimization Tags , , , ,

    The classical assembly line balancing problem consists of assigning assembly work to workstations. In the presence of setup times that depend on the sequence of tasks assigned to each workstation, the problem becomes more complicated given that two interdependent problems, namely assignment and sequencing, must be solved simultaneously. The hierarchical nature of these two problems … Read more

    Distributionally Robust Stochastic Optimization with Wasserstein Distance

  • Anton J. Kleywegt
  • Rui Gao
    • Categories Infinite Dimensional Optimization, Robust Optimization, Stochastic Programming

    Distributionally robust stochastic optimization (DRSO) is an approach to optimization under uncertainty in which, instead of assuming that there is an underlying probability distribution that is known exactly, one hedges against a chosen set of distributions. In this paper, we consider sets of distributions that are within a chosen Wasserstein distance from a nominal distribution. … Read more

    Computing Restricted Isometry Constants via Mixed-Integer Semidefinite Programming

  • Tristan Gally
  • Marc E. Pfetsch
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , ,

    One of the fundamental tasks in compressed sensing is finding the sparsest solution to an underdetermined system of linear equations. It is well known that although this problem is NP-hard, under certain conditions it can be solved by using a linear program which minimizes the 1-norm. The restricted isometry property has been one of the … Read more

    A Framework for Solving Mixed-Integer Semidefinite Programs

  • Tristan Gally
  • Marc E. Pfetsch
  • Stefan Ulbrich
    • Categories (Mixed) Integer Nonlinear Programming, Optimization Software and Modeling Systems, Semi-definite Programming

    Mixed-integer semidefinite programs arise in many applications and several problem-specific solution approaches have been studied recently. In this paper, we investigate a generic branch-and-bound framework for solving such problems. We first show that strict duality of the semidefinite relaxations is inherited to the subproblems. Then solver components like dual fixing, branching rules, and primal heuristics … Read more