valid inequalities

Strengthening Dual Bounds for Multicommodity Capacitated Network Design with Unsplittable Flow Constraints

  • Lacy M. Greening
  • Santanu S. Dey
  • Alan L. Erera
    • Categories Integer Programming, Network Optimization, Production and Logistics Tags , , ,

    Multicommodity capacitated network design (MCND) models can be used to optimize the consolidation of shipments within e-commerce fulfillment networks. In practice, fulfillment networks require that shipments with the same origin and destination follow the same transfer path. This unsplittable flow requirement complicates the MCND problem, requiring integer programming (IP) formulations with binary variables replacing continuous … Read more

    Polynomial-Time Algorithms for Setting Tight Big-M Coefficients in Transmission Expansion Planning with Disconnected Buses

  • Behnam Jabbari Marand
  • Adolfo Escobedo
    • Categories Combinatorial Optimization, Cutting Plane Approaches, Energy Tags , , ,

    The increasing penetration of renewable energy into power systems necessitates the development of effective methodologies to integrate initially disconnected generation sources into the grid. This paper introduces the Longest Shortest-Path-Connection (LSPC) algorithm, a graph-based method to enhance the mixed-integer linear programming disjunctive formulation of Transmission Expansion Planning (TEP) using valid inequalities (VIs). Traditional approaches for … Read more

    Cover-based inequalities for the single-source capacitated facility location problem with customer preferences

  • Christina Büsing
  • Markus Leitner
  • Sophia Wrede
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    The single-source capacitated facility location problem with customer preferences (SSCFLPCP) is known to be strongly NP-hard. Computational tests imply that state-of-the-art solvers struggle with computing exact solutions. In this paper, we contribute two novel preprocessing methods which reduce the size of the considered integer programming formulation, and introduce sets of valid inequalities which decrease the … Read more

    Facets of the knapsack polytope from non-minimal covers

  • Guneshwar Anand
  • Sachin Jayaswal
  • B. Srirangacharyulu
    • Categories (Mixed) Integer Linear Programming, Polyhedra, Transportation Tags , , , , ,

    We propose two new classes of valid inequalities (VIs) for the binary knapsack polytope, based on non-minimal covers. We also show that these VIs can be obtained through neither sequential nor simultaneous lifting of well-known cover inequalities. We further provide conditions under which they are facet-defining. The usefulness of these VIs is demonstrated using computational … Read more

    Fair and Risk-averse Urban Air Mobility Resource Allocation Under Uncertainties

  • Luying Sun
  • Weijun Xie
    • Categories Applications - OR and Management Sciences Tags , , , ,

    Urban Air Mobility (UAM) is an emerging air transportation mode to alleviate the ground traffic burden and achieve zero direct aviation emissions. Due to the potential economic scaling effects, the UAM traffic flow is expected to increase dramatically once implemented, and its market can be substantially large. To be prepared for the era of UAM, … Read more

    Theoretical Insights and a New Class of Valid Inequalities for the Temporal Bin Packing Problem with Fire-Ups

  • John Martinovic
  • Nico Strasdat
    • Categories (Mixed) Integer Linear Programming, Scheduling Tags , , , ,

    The temporal bin packing problem with fire-ups (TBPP-FU) is a two-dimensional packing problem where one geometric dimension is replaced by a time horizon. The given items (jobs) are characterized by a resource consumption, that occurs exclusively during an activity interval, and they have to be placed on servers so that the capacity constraint is respected … Read more

    Sparse multi-term disjunctive cuts for the epigraph of a function of binary variables

  • Rui Chen
  • James R. Luedtke
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , ,

    We propose a new method for separating valid inequalities for the epigraph of a function of binary variables. The proposed inequalities are disjunctive cuts defined by disjunctive terms obtained by enumerating a subset $I$ of the binary variables. We show that by restricting the support of the cut to the same set of variables $I$, … Read more

    Exact and Heuristic Solution Techniques for Mixed-Integer Quantile Minimization Problems

  • Diego Cattaruzza
  • Martine Labbé
  • Matteo Petris
  • Marius Roland
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering, Stochastic Programming Tags , , , ,

    We consider mixed-integer linear quantile minimization problems that yield large-scale problems that are very hard to solve for real-world instances. We motivate the study of this problem class by two important real-world problems: a maintenance planning problem for electricity networks and a quantile-based variant of the classic portfolio optimization problem. For these problems, we develop … Read more

    Multi-depot routing with split deliveries: Models and a branch-and-cut algorithm

  • Luís Gouveia
  • Markus Leitner
  • Mario Ruthmair
    • Categories Applications - OR and Management Sciences Tags , , , ,

    We study the multi-depot split-delivery vehicle routing problem (MDSDVRP) which combines the advantages and potential cost-savings of multiple depots and split-deliveries and develop the first exact algorithm for this problem. We propose an integer programming formulation using a small number of decision variables and several sets of valid inequalities. These inequalities focus on ensuring the … Read more

    Distributionally Robust Fair Transit Resource Allocation During a Pandemic

  • Luying Sun
  • Weijun Xie
  • Tim Witten
    • Categories Applications - OR and Management Sciences Tags , , ,

    This paper studies Distributionally robust Fair transit Resource Allocation model (DrFRAM) under Wasserstein ambiguity set to optimize the public transit resource allocation during a pandemic. We show that the proposed DrFRAM is highly nonconvex and nonlinear and is, in general, NP-hard. Fortunately, we show that DrFRAM can be reformulated as a mixed-integer linear programming (MILP) … Read more