Combinatorial Optimization

Relating Single-Scenario Facets to the Convex Hull of the Extensive Form of a Stochastic Single-Node Flow Polytope

  • Victor A. Gonzalez
  • Andrew J. Schaefer
  • Mehdi Hemmati
  • David T. Mildebrath
    • Categories (Mixed) Integer Linear Programming, Polyhedra, Stochastic Programming Tags , ,

    Stochastic mixed-integer programs (SMIPs) are a widely-used modeling paradigm for sequential decision making under uncertainty. One popular solution approach to solving SMIPs is to solve the so-called “extensive form” directly as a large-scale (deterministic) mixed-integer program. In this work, we consider the question of when a facet-defining inequality for the convex hull of a deterministic, … Read more

    Arc routing with electric vehicles: dynamic charging and speed-dependent energy consumption

  • Elena Fernandez
  • Markus Leitner
  • Ivana Ljubić
  • Mario Ruthmair
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Production and Logistics Tags , , , , , ,

    Concerns about greenhouse gas emissions and government regulations foster the use of electric vehicles. Several recently published articles study the use of electric vehicles (EVs) in node-routing problems. In contrast, this article considers EVs in the context of arc routing while also addressing practically relevant aspects that have not been addressed sufficiently so far. These … Read more

    Globalized Robust Optimization with Gamma-Uncertainties

  • Andreas Bärmann
  • Christina Büsing
  • Frauke Liers
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Robust Optimization Tags , , ,

    Globalized robust optimization has been proposed as a generalization of the standard robust optimization framework in order to allow for a controlled decrease in protection depending on the distance of the realized scenario from the predefined uncertainty set. In this work, we specialize the notion of globalized robustness to Gamma-uncertainty in order to extend its … Read more

    Anomalous Behaviour of Dual-Based Heuristics

  • Trivikram Dokka
  • Adam N. Letchford
  • M. Hasan Mansoor
    • Categories 0-1 Programming, Combinatorial Optimization, Meta Heuristics Tags , , ,

    Some popular heuristics for combinatorial optimisation start by constructing a feasible solution to a dual of the problem. We show that such dual-based heuristics can exhibit highly counter-intuitive behaviour. In particular, for some problem classes, solving the dual exactly invariably leads to much worse primal solutions than solving the dual with a simple greedy heuristic. … Read more

    A Generic Exact Solver for Vehicle Routing and Related Problems

  • Artur Alves Pessoa
  • Ruslan Sadykov
  • Eduardo Uchoa
  • François Vanderbeck
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Modeling Languages and Systems Tags , ,

    Major advances were recently obtained in the exact solution of Vehicle Routing Problems (VRPs). Sophisticated Branch-Cut-and-Price (BCP) algorithms for some of the most classical VRP variants now solve many instances with up to a few hundreds of customers. However, adapting and reimplementing those successful algorithms for other variants can be a very demanding task. This … Read more

    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

    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