Integer Programming

On the Exactness of Dantzig-Wolfe Relaxation for Rank Constrained Optimization Problems

  • Yongchun Li
  • Weijun Xie
    • Categories Integer Programming Tags , , , , , ,

    In the rank-constrained optimization problem (RCOP), it minimizes a linear objective function over a prespecified closed rank-constrained domain set and $m$ generic two-sided linear matrix inequalities. Motivated by the Dantzig-Wolfe (DW) decomposition, a popular approach of solving many nonconvex optimization problems, we investigate the strength of DW relaxation (DWR) of the RCOP, which admits the … Read more

    A Consensus-Based Alternating Direction Method for Mixed-Integer and PDE-Constrained Gas Transport Problems

  • Richard Krug
  • Günter Leugering
  • Alexander Martin
  • Martin Schmidt
  • Dieter Weninger
    • Categories (Mixed) Integer Nonlinear Programming, Network Optimization, Optimization of Systems modeled by PDEs Tags , , , ,

    We consider dynamic gas transport optimization problems, which lead to large-scale and nonconvex mixed-integer nonlinear optimization problems (MINLPs) on graphs. Usually, the resulting instances are too challenging to be solved by state-of-the-art MINLP solvers. In this paper, we use graph decompositions to obtain multiple optimization problems on smaller blocks, which can be solved in parallel … Read more

    An Exact Method for Nonlinear Network Flow Interdiction Problems

  • Martin Schmidt
  • Johannes Thürauf
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Network Optimization Tags , , ,

    We study network flow interdiction problems with nonlinear and nonconvex flow models. The resulting model is a max-min bilevel optimization problem in which the follower’s problem is nonlinear and nonconvex. In this game, the leader attacks a limited number of arcs with the goal to maximize the load shed and the follower aims at minimizing … Read more

    A Combinatorial Flow-based Formulation for Temporal Bin Packing Problems

  • John Martinovic
  • Nico Strasdat
  • José Valério de Carvalho
  • Fabio Furini
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization Tags , , , ,

    We consider two neighboring generalizations of the classical bin packing problem: the temporal bin packing problem (TBPP) and the temporal bin packing problem with fire-ups (TBPP-FU). In both cases, the task is to arrange a set of given jobs, characterized by a resource consumption and an activity window, on homogeneous servers of limited capacity. To … Read more

    Vehicle Routing with Heterogeneous Time Windows

  • Petra Mutzel
  • Tim Niemann
  • Sebastian Stiller
  • Andreas M. Tillmann
  • Lukas Schürmann
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Transportation Tags , ,

    We consider a novel variant of the heterogeneous vehicle routing problem (VRP) in which each customer has different availability time windows for every vehicle. In particular, this covers our motivating application of planning daily delivery tours for a single vehicle, where customers can be available at different times each day. The existing literature on heterogeneous … Read more

    Evaluating Mixed-Integer Programming Models over Multiple Right-hand Sides

  • Rachael M. Alfant
  • Temitayo Ajayi
  • Andrew J. Schaefer
    • Categories (Mixed) Integer Linear Programming Tags , ,

    A critical measure of model quality for a mixed-integer program (MIP) is the difference, or gap, between its optimal objective value and that of its linear programming relaxation. In some cases, the right-hand side is not known exactly; however, there is no consensus metric for evaluating a MIP model when considering multiple right-hand sides. In … Read more

    Dual Bounds from Decision Diagram-Based Route Relaxations: An Application to Truck-Drone Routing

  • Z Tang
  • Willem-Jan van Hoeve
    • Categories Integer Programming, Transportation Tags , , , ,

    For vehicle routing problems, strong dual bounds on the optimal value are needed to develop scalable exact algorithms, as well as to evaluate the performance of heuristics. In this work, we propose an iterative algorithm to compute dual bounds motivated by connections between decision diagrams (DDs) and dynamic programming (DP) models used for pricing in … Read more

    A binary linear programming approach for supporting administrative territorial consolidation

  • Radu Buzatu
  • Igor Mandric
    • Categories 0-1 Programming, Combinatorial Optimization, Linear Programming Tags , , ,

    The objective of this paper is to develop a scalable binary linear programming model for finding the optimal aggregation of communes into spatially contiguous administrative territorial units (ATUs) constrained on certain balancing criteria. The requirement for the ATUs to be contiguous represents the main computational bottleneck and, therefore, it prevents one from using such models … Read more

    The complexity of branch-and-price algorithms for the capacitated vehicle routing problem with stochastic demands

  • Ricardo Fukasawa
    • Categories Combinatorial Optimization, Integer Programming, Stochastic Programming Tags , ,

    The capacitated vehicle routing problem with stochastic demands (CVRPSD) is a variant of the deterministic capacitated vehicle routing problem where customer demands are random variables. While the most successful formulations for several deterministic vehicle-routing problem variants are based on a set-partitioning formulation, adapting such formulations for the CVRPSD under mild assumptions on the demands remains … Read more