Branch and Cut Algorithms

Solving bilevel combinatorial optimization as bilinear min-max optimization via a branch-and-cut algorithm

  • Artur Alves Pessoa
  • Michael Poss
  • Marcos Costa Roboredo
    • Categories Branch and Cut Algorithms Tags , , ,

    In this paper, we propose a generic branch-and -cut algorithm for a special class of bi-level combinatorial optimization problems. Namely, we study such problems that can be reformulated as bilinear min-max combinatorial optimization problems. We show that the reformulation can be efficiently solved by a branch-and-cut algorithm whose cuts represent the inner maximization feasibility set. … Read more

    The split-demand one-commodity pickup-and-delivery travelling salesman problem

  • Juan-José Salazar-González
  • Beatriz Santos-Hernández
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches, Transportation

    This paper introduces a new vehicle routing problem transferring one commodity between customers with a capacitated vehicle that can visit a customer more than once,although a maximum number of visits must be respected. It generalizes the capacitated vehicle routing problem with split demands and some other variants recently addressed in the literature. We model the … Read more

    A Cut-and-Branch Algorithm for the Quadratic Knapsack Problem

  • Franklin Djeumou Fomeni
  • Konstantinos Kaparis
  • Adam N. Letchford
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms

    The Quadratic Knapsack Problem (QKP) is a well-known NP-hard combinatorial optimisation problem, with many practical applications. We present a ‘cut-and-branch’ algorithm for the QKP, in which a cutting-plane phase is followed by a branch-and-bound phase. The cutting-plane phase is more sophisticated than the existing ones in the literature, incorporating several classes of cutting planes, two … Read more

    Decomposition Algorithms for Two-Stage Chance-Constrained Programs

  • Simge Küçükyavuz
  • James R. Luedtke
  • Xiao Liu
    • Categories Branch and Cut Algorithms, Integer Programming, Stochastic Programming Tags , , ,

    We study a class of chance-constrained two-stage stochastic optimization problems where second-stage feasible recourse decisions incur additional cost. In addition, we propose a new model, where “recovery” decisions are made for the infeasible scenarios to obtain feasible solutions to a relaxed second-stage problem. We develop decomposition algorithms with specialized optimality and feasibility cuts to solve … Read more

    A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for some NP-Hard Graph Optimization Problems

  • Elspeth Adams
  • Miguel F. Anjos
  • Franz Rendl
  • Angelika Wiegele
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches, Semi-definite Programming

    Many important NP-hard combinatorial problems can be efficiently approximated using semidefinite programming relaxations. We propose a new hierarchy of semidefinite relaxations for classes of such problems that based on graphs and for which the projection of the problem onto a subgraph shares the same structure as the original problem. This includes the well-studied max-cut and … Read more

    Exact Algorithms for Arc and Node Routing Problems

  • Rafael Martinelli
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches, Dynamic Programming

    Routing problems stand among the hardest combinatorial problems to find high quality bounds or to prove new optimal solutions. In this thesis, we tackle the Capacitated Arc Routing Problem (CARP) and the Generalized Vehicle Routing Problem (GVRP). For both problems, there are a set of customers spread over a given graph, where each customer has … Read more

    On Solving a Hard Quadratic 3-Dimensional Assignment Problem

  • Hans D Mittelmann
  • Domenico Salvagnin
    • Categories Branch and Cut Algorithms, Telecommunications Tags , ,

    We address the exact solution of a very challenging (and previously unsolved) instance of the quadratic 3-dimensional assignment problem, arising in digital wireless communications. The paper describes the techniques developed to solve this instance to proven optimality, from the choice of an appropriate mixed-integer programming formulation, to cutting planes and symmetry handling. Using these techniques … Read more

    Ancestral Benders’ Cuts and Multi-term Disjunctions for Mixed-Integer Recourse Decisions in Stochastic Programming

  • Yunwei Qi
  • Suvrajeet Sen
    • Categories Branch and Cut Algorithms, Stochastic Programming Tags , ,

    This paper focuses on solving two-stage stochastic mixed integer programs (SMIPs) with general mixed integer decision variables in both stages. We develop a decomposition algorithm in which the first stage approximation is solved using a branch-and-bound tree with nodes inheriting Benders’ cuts that are valid for their ancestor nodes. In addition, we develop two closely … Read more

    Exact and Heuristic Approaches for Directional Sensor Control

  • Hans D Mittelmann
  • Domenico Salvagnin
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Control Applications Tags , , ,

    Directional sensors are gaining importance due to applications, in- cluding surveillance, detection, and tracking. Such sensors have a limited fi eld-of-view and a discrete set of directions they can be pointed to. The Directional Sensor Control problem (DSCP) consists in assigning a direction of view to each sensor. The location of the targets is known with … Read more

    Improving the LP bound of a MILP by dual concurrent branching and the relationship to cut generation methods

  • H. Georg Büsching
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Cutting Plane Approaches Tags ,

    In this paper branching for attacking MILP is investigated. Under certain circumstances branches can be done concurrently. By introducing a new calculus it is shown there are restrictions for dual values. As a second result of this study a new class of cuts for MILP is found, which are defined by those values. This class … Read more