Branch and Cut Algorithms

The Robust Bike Sharing Rebalancing Problem: Formulations and a Branch-and-Cut Algorithm

  • Bruno Petrato Bruck
  • Walton P. Coutinho
  • Pedro Munari
    • Categories Branch and Cut Algorithms, Robust Optimization, Transportation Tags , , ,

    Bike Sharing Systems (BSSs) offer a sustainable and efficient urban transportation solution, bringing flexible and eco-friendly alternatives to city logistics. During their operation, BSSs may suffer from unbalanced bike distribution among stations, requiring rebalancing operations throughout the system. The inherent uncertain demand at the stations further complicates these rebalancing operations, even when performed during downtime. … Read more

    DeLuxing: Deep Lagrangian Underestimate Fixing for Column-Generation-Based Exact Methods

  • Yu Yang
    • Categories Branch and Cut Algorithms, Integer Programming, Transportation

    In this paper, we propose an innovative variable fixing strategy called deep Lagrangian underestimate fixing (DeLuxing). It is a highly effective approach for removing unnecessary variables in column-generation (CG)-based exact methods used to solve challenging discrete optimization problems commonly encountered in various industries, including vehicle routing problems (VRPs). DeLuxing employs a novel linear programming (LP) … Read more

    Optimal Multi-Agent Pickup and Delivery Using Branch-and-Cut-and-Price

  • Edward Lam
    • Categories Branch and Cut Algorithms, Integer Programming, Transportation

    Given a set of agents and a set of pickup-delivery requests located on a two-dimensional map, the Multi-Agent Pickup and Delivery problem assigns the requests to the agents such that every agent moves from its start location to the locations of its assigned requests and finally to its end location without colliding into any other … Read more

    Fair stochastic vehicle routing with partial deliveries

  • Natasja Sluijk
  • Walter Rei
  • Joris Kinable
  • Michel Gendreau
  • Tom Van Woensel
    • Categories Branch and Cut Algorithms, Stochastic Programming, Transportation Tags , , ,

    A common assumption in the models for the vehicle routing problem with stochastic demands is that all demands must be satisfied. This is achieved by including recourse actions in two-stage stochastic programming formulations or by ensuring with a high probability that all demand fits within the vehicle capacity (chance-constrained formulations). In this work, we relax … Read more

    Column Elimination for Capacitated Vehicle Routing Problems

  • Anthony Karahalios
  • Willem-Jan van Hoeve
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Dynamic Programming Tags , , ,

    We introduce a column elimination procedure for the capacitated vehicle routing problem. Our procedure maintains a decision diagram to represent a relaxation of the set of feasible routes, over which we define a constrained network flow. The optimal solution corresponds to a collection of paths in the decision diagram and yields a dual bound. The … Read more

    On solving the MAX-SAT using sum of squares

  • Lennart Sinjorgo
  • Renata Sotirov
    • Categories 0-1 Programming, Branch and Cut Algorithms, Semi-definite Programming Tags , , , ,

    We consider semidefinite programming (SDP) approaches for solving the maximum satisfiabilityproblem (MAX-SAT) and the weighted partial MAX-SAT. It is widely known that SDP is well-suitedto approximate the (MAX-)2-SAT. Our work shows the potential of SDP also for other satisfiabilityproblems, by being competitive with some of the best solvers in the yearly MAX-SAT competition.Our solver combines … Read more

    The min-Knapsack Problem with Compactness Constraints and Applications in Statistics

  • Alberto Santini
  • Enrico Malaguti
    • Categories Branch and Cut Algorithms, Dynamic Programming, Statistics Tags , ,

    In the min-Knapsack problem, one is given a set of items, each having a certain cost and weight. The objective is to select a subset with minimum cost, such that the sum of the weights is not smaller than a given constant. In this paper we introduce an extension of the min-Knapsack problem with additional … Read more

    The Hamiltonian p-median Problem: Polyhedral Results and Branch-and-Cut Algorithm

  • Michele Barbato
  • Luís Gouveia
    • Categories Branch and Cut Algorithms, Combinatorial Optimization, Polyhedra Tags , , , ,

    In this paper we study the Hamiltonian \(p\)-median problem, in which a weighted graph on \(n\) vertices is to be partitioned into \(p\) simple cycles of minimum total weight. We introduce two new families of valid inequalities for a formulation of the problem in the space of natural edge variables. Each one of the families … Read more

    A comparison of different approaches for the vehicle routing problem with stochastic demands

  • Matheus Jun Ota
  • Ricardo Fukasawa
    • Categories Branch and Cut Algorithms, Production and Logistics, Stochastic Programming Tags , ,

    The vehicle routing problem with stochastic demands (VRPSD) is a well studied variant of the classic (deterministic) capacitated vehicle routing problem (CVRP) where the customer demands are given by random variables. Two prominent approaches for solving the VRPSD model it either as a chance-constraint program (CC-VRPSD) or as a two-stage stochastic program (2S-VRPSD). In this … Read more

    The Largest Unsolved QAP Instance Tai256c Can Be Converted into A 256-dimensional Simple BQOP with A Single Cardinality Constraint

  • Koichi Fujii
  • Sunyoung Kim
  • Masakazu Kojima
  • Hans D Mittelmann
  • Yuji Shinano
    • Categories 0-1 Programming, Branch and Cut Algorithms, Semi-definite Programming Tags , , , , ,

    Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB; a 1.48\% gap remains between the best known feasible objective value and lower bound of the unknown optimal value. This paper shows that the instance can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which … Read more