Combinatorial Optimization

Toward breaking the curse of dimensionality: an FPTAS for stochastic dynamic programs with multidimensional action and scalar state

  • Nir Halman
  • Giacomo Nannicini
    • Categories Approximation Algorithms, Dynamic Programming, Supply Chain Management Tags , , , ,

    We propose a Fully Polynomial-Time Approximation Scheme (FPTAS) for stochastic dynamic programs with multidimensional action, scalar state, convex costs and linear state transition function. The action spaces are polyhedral and described by parametric linear programs. This type of problems finds applications in the area of optimal planning under uncertainty, and can be thought of as … Read more

    Disruption Recovery at Airports: Integer Programming Formulations and Polynomial time algorithms

  • Prabhu Manyem
    • Categories 0-1 Programming, Airline Optimization, Approximation Algorithms Tags , , , ,

    We study disruptions at a major airport. Disruptions could be caused by bad weather, for example. Our study is from the perspective of the airport, the air services provider (such as air traffic control) and the travelling public, rather than from the perspective of a single airline. Disruptions cause flights to be subjected to ground … Read more

    A branch-and-bound algorithm for the minimum radius k-enclosing ball problem

  • Farid Alizadeh
  • Marta Cavaleiro
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization Tags , , ,

    The minimum $k$-enclosing ball problem seeks the ball with smallest radius that contains at least $k$ of $m$ given points in a general $n$-dimensional Euclidean space. This problem is NP-hard. We present a branch-and-bound algorithm on the tree of the subsets of $k$ points to solve this problem. The nodes on the tree are ordered … Read more

    Improved Space-State Relaxation for Constrained Two-Dimensional Guillotine Cutting Problems

  • Eduardo Uchoa
  • André Velasco
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization Tags , ,

    Christofides and Hadjiconstantinou introduced a dynamic programming state space relaxation for obtaining upper bounds for the Constrained Two-dimensional Guillotine Cutting Problem. The quality of those bounds depend on the chosen item weights, they are adjusted using a subgradient-like algorithm. This paper proposes Algorithm X, a new weight adjusting algorithm based on integer programming that provably … Read more

    The job shop scheduling problem with convex costs

  • Kerem Bülbül
  • Reinhard Bürgy
    • Categories Applications - OR and Management Sciences, Meta Heuristics, Scheduling

    The job shop scheduling literature has been dominated by a focus on regular objective functions — in particular the makespan — in its half a century long history. The last twenty years have encountered a spike of interest in other objectives, such as the total weighted tardiness, but research on non-regular objective functions has always … Read more

    On the Linear Extension Complexity of Stable Set Polytopes for Perfect Graphs

  • Hao Hu
  • Monique Laurent
    • Categories Graphs and Matroids, Linear Programming Tags , ,

    We study the linear extension complexity of stable set polytopes of perfect graphs. We make use of known structural results permitting to decompose perfect graphs into basic perfect graphs by means of two graph operations: 2-join and skew partitions. Exploiting the link between extension complexity and the nonnegative rank of an associated slack matrix, we … Read more

    Improved Conic Reformulations for K-means Clustering

  • Grani A. Hanasusanto
  • Madhushini Narayana Prasad
    • Categories Combinatorial Optimization, Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    In this paper, we show that the popular K-means clustering problem can equivalently be reformulated as a conic program of polynomial size. The arising convex optimization problem is NP-hard, but amenable to a tractable semidefinite programming (SDP) relaxation that is tighter than the current SDP relaxation schemes in the literature. In contrast to the existing … Read more

    Structure and Interpretation of Dual-Feasible Functions

  • Matthias Köppe
  • Jiawei Wang
    • Categories Combinatorial Optimization, Cutting Plane Approaches

    We study two techniques to obtain new families of classical and general Dual-Feasible Functions: A conversion from minimal Gomory–Johnson functions; and computer-based search using polyhedral computation and an automatic maximality and extremality test. Citation6 pages extended abstract to appear in Proc. LAGOS 2017, with 21 pages of appendix.ArticleDownload View PDF

    Size Matters: Cardinality-Constrained Clustering and Outlier Detection via Conic Optimization

  • Daniel Kuhn
  • Napat Rujeerapaiboon
  • Kilian Schindler
  • Wolfram Wiesemann
    • Categories Approximation Algorithms, Data-Mining, Linear, Cone and Semidefinite Programming Tags , , ,

    Plain vanilla K-means clustering is prone to produce unbalanced clusters and suffers from outlier sensitivity. To mitigate both shortcomings, we formulate a joint outlier-detection and clustering problem, which assigns a prescribed number of datapoints to an auxiliary outlier cluster and performs cardinality-constrained K-means clustering on the residual dataset. We cast this problem as a mixed-integer … Read more

    On the complexity of the Unit Commitment Problem

  • Pascale Bendotti
  • Pierre Fouilhoux
  • Cécile Rottner
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization

    This article analyzes how the Unit Commitment Problem (UCP) complexity evolves with respect to the number n of units and T of time periods.A classical reduction from the knapsack problem shows that the UCP is NP-hard in the ordinary sense even for T=1. The UCP is proved to be strongly NP-hard.When either a unitary cost … Read more