Combinatorial Optimization

Minimizing Total Earliness and Tardiness with Periodically Supplied Non-renewable Resource Profiles

  • Aleida Braaksma
  • Mohammad Mahdavi Mazdeh
  • Mohammad Namakshenas
    • Categories Approximation Algorithms, Scheduling Tags , , ,

    We consider a special class of resource-constrained single machine scheduling problems. In the classical scheduling context, resource types are classi ed into renewable and non-renewable; however, a large variety of real-world problems may not fit into one of these classes, e.g., labor regulations in project scheduling, budget allocation to different phases of a construction project, and … Read more

    Decomposing the Train Scheduling Problem into Integer Optimal Polytopes

  • Masoud Barah
  • James Ostrowski
  • Abbas Seifi
    • Categories (Mixed) Integer Linear Programming, Polyhedra, Transportation Tags , ,

    This paper presents conditions for which the linear relaxation for the train scheduling problem is integer-optimal. These conditions are then used to identify how to partition a general problem’s feasible region into integer-optimal polytopes. Such an approach yields an extended formulation that contains far fewer binary variables. Our computational experiments show that this approach results … Read more

    Equivalences among the chi measure, Hoffman constant, and Renegar’s distance to ill-posedness

  • Javier F. Peña
  • Juan C. Vera
  • Luis F. Zuluaga
    • Categories Convex Optimization, Linear Programming, Polyhedra Tags , , , ,

    We show the equivalence among the following three condition measures of a full column rank matrix $A$: the chi measure, the signed Hoffman constant, and the signed distance to ill-posedness. The latter two measures are constructed via suitable collections of matrices obtained by flipping the signs of some rows of $A$. Our results provide a … Read more

    A Solution Approach to Distributionally Robust Chance-Constrained Assignment Problems

  • Jinlin Li
  • Sanjay Mehrotra
  • Shanshan Wang
    • Categories Applications - OR and Management Sciences, Branch and Cut Algorithms, Scheduling

    We study assignment problem with chance constraints (CAP) and its distributionally robust counterpart (DR-CAP). We present a technique for estimating big-M in such a formulation that takes advantage of the ambiguity set. We consider a 0-1 bilinear knapsack set to develop valid inequalities for CAP and DR-CAP. This is generalized to the joint chance constraint … Read more

    New characterizations of Hoffman constants for systems of linear constraints

  • Javier F. Peña
  • Juan C. Vera
  • Luis F. Zuluaga
    • Categories Convex Optimization, Polyhedra Tags , ,

    We give a characterization of the Hoffman constant of a system of linear constraints in $\R^n$ relative to a reference polyhedron $R\subseteq\R^n$. The reference polyhedron $R$ represents constraints that are easy to satisfy such as box constraints. In the special case $R = \R^n$, we obtain a novel characterization of the classical Hoffman constant. More … Read more

    A Scenario-Based Approach for the Vehicle Routing Problem with Roaming Delivery Locations under Stochastic Travel Times

  • Joris Kinable
  • Afonso Sampaio
  • Lucas Veelenturf
  • Tom Van Woensel
    • Categories Meta Heuristics, Stochastic Programming, Transportation Tags , ,

    We address a stochastic variant of the Vehicle Routing Problem with Roaming Delivery Locations. In this model, direct-to-consumer deliveries can be made in the trunk of the customer’s car, while the vehicle is parked at a location along the customer’s itinerary. The stochasticity arises from the uncertainty in travel times and the problem is formulated … Read more

    An analysis of noise folding for low-rank matrix recovery

  • Wang Hailin
  • Jianjun Wang
  • Jianwen Huang
  • Wang Wendong
  • Feng Zhang
    • Categories Approximation Algorithms, Convex Optimization, Data-Mining

    Previous work regarding low-rank matrix recovery has concentrated on the scenarios in which the matrix is noise-free and the measurements are corrupted by noise. However, in practical application, the matrix itself is usually perturbed by random noise preceding to measurement. This paper concisely investigates this scenario and evidences that, for most measurement schemes utilized in … Read more

    A Combinatorial Algorithm for the Multi-commodity Flow Problem

  • Pengfei Liu
    • Categories Combinatorial Optimization Tags ,

    This paper researches combinatorial algorithms for the multi-commodity flow problem. We relax the capacity constraints and introduce a \emph{penalty function} \(h\) for each arc. If the flow exceeds the capacity on arc \(a\), arc \(a\) would have a penalty cost. Based on the \emph{penalty function} \(h\), a new conception , \emph{equilibrium pseudo-flow}, is introduced. Then … Read more

    A Combinatorial Algorithm for the Multi-commodity Flow Problem

  • Pengfei Liu
    • Categories Combinatorial Optimization, Network Optimization Tags ,

    This paper researches combinatorial algorithms for the multi-commodity flow problem. We relax the capacity constraints and introduce a \emph{penalty function} \(h\) for each arc. If the flow exceeds the capacity on arc \(a\), arc \(a\) would have a penalty cost. Based on the \emph{penalty function} \(h\), a new conception , \emph{equilibrium pseudo-flow}, is introduced. Then … Read more

    Knapsack Polytopes – A Survey

  • Tristan Gally
  • Oliver Habeck
  • Christopher Hojny
  • Frederic Matter
  • Marc E. Pfetsch
  • Andreas Schmitt
  • Hendrik Lüthen
    • Categories 0-1 Programming, Polyhedra Tags , , , , ,

    The 0/1 knapsack polytope is the convex hull of all 0/1 vectors that satisfy a given single linear inequality with non-negative coefficients. This paper provides a comprehensive overview of knapsack polytopes. We discuss basic polyhedral properties, (lifted) cover and other valid inequalities, cases for which complete linear descriptions are known, geometric properties for small dimensions, … Read more