Combinatorial Optimization

Ray Projection for Optimizing Polytopes with Prohibitively Many Constraints in Set-Covering Column Generation

  • Daniel Porumbel
    • Categories Combinatorial Optimization, Polyhedra Tags ,

    A recurrent task in mathematical programming requires optimizing polytopes with prohibitively-many constraints, e.g., the primal polytope in cutting-plane methods or the dual polytope in Column Generation (CG). This paper is devoted to the ray projection technique for optimizing such polytopes: start from a feasible solution and advance on a given ray direction until intersecting a … Read more

    Optimization Methods for Disease Prevention and Epidemic Control

  • Yan Deng
  • Siqian Shen
  • Yevgeniy Vorobeychik
    • Categories 0-1 Programming, Applications - OR and Management Sciences, Meta Heuristics Tags , , , ,

    This paper investigates problems of disease prevention and epidemic control (DPEC), in which we optimize two sets of decisions: (i) vaccinating individuals and (ii) closing locations, given respective budgets with the goal of minimizing the expected number of infected individuals after intervention. The spread of diseases is inherently stochastic due to the uncertainty about disease … Read more

    On Solving a Hard Quadratic 3-Dimensional Assignment Problem

  • Hans D Mittelmann
  • Domenico Salvagnin
    • Categories Branch and Cut Algorithms, Telecommunications Tags , ,

    We address the exact solution of a very challenging (and previously unsolved) instance of the quadratic 3-dimensional assignment problem, arising in digital wireless communications. The paper describes the techniques developed to solve this instance to proven optimality, from the choice of an appropriate mixed-integer programming formulation, to cutting planes and symmetry handling. Using these techniques … Read more

    A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially

  • Volker Kaibel
  • Stefan Weltge
    • Categories Linear Programming, Polyhedra Tags , , , ,

    We establish that the extension complexity of the nXn correlation polytope is at least 1.5^n by a short proof that is self-contained except for using the fact that every face of a polyhedron is the intersection of all facets it is contained in. The main innovative aspect of the proof is a simple combinatorial argument … Read more

    Ancestral Benders’ Cuts and Multi-term Disjunctions for Mixed-Integer Recourse Decisions in Stochastic Programming

  • Yunwei Qi
  • Suvrajeet Sen
    • Categories Branch and Cut Algorithms, Stochastic Programming Tags , ,

    This paper focuses on solving two-stage stochastic mixed integer programs (SMIPs) with general mixed integer decision variables in both stages. We develop a decomposition algorithm in which the first stage approximation is solved using a branch-and-bound tree with nodes inheriting Benders’ cuts that are valid for their ancestor nodes. In addition, we develop two closely … Read more

    Exact and Heuristic Approaches for Directional Sensor Control

  • Hans D Mittelmann
  • Domenico Salvagnin
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Control Applications Tags , , ,

    Directional sensors are gaining importance due to applications, in- cluding surveillance, detection, and tracking. Such sensors have a limited fi eld-of-view and a discrete set of directions they can be pointed to. The Directional Sensor Control problem (DSCP) consists in assigning a direction of view to each sensor. The location of the targets is known with … Read more

    Improved Bounds for the Traveling Umpire Problem: A Stronger Formulation and a Relax-and-Fix Heuristic

  • Lucas de Oliveira
  • Cid C. de Souza
  • Tallys H. Yunes
    • Categories Meta Heuristics Tags , , ,

    Given a double round-robin tournament, the traveling umpire problem (TUP) consists of determining which games will be handled by each one of several umpire crews during the tournament. The objective is to minimize the total distance traveled by the umpires, while respecting constraints that include visiting every team at home, and not seeing a team … Read more

    Scheduling of Two Agents Task Chains with a Central Selection Mechanism

  • Alessandro Agnetis
  • Gaia Nicosia
  • Ulrich Pferschy
  • Andrea Pacifici
    • Categories Combinatorial Optimization, Game Theory, Scheduling Tags , , ,

    In this paper we address a deterministic scheduling problem in which two agents compete for the usage of a single machine. Each agent decides on a fixed order to submit its tasks to an external coordination subject, who sequences them according to a known priority rule. We consider the problem from different perspectives. First, we … Read more