branch-and-cut

Solving Linear Programs with Complementarity Constraints using Branch-and-Cut

  • John E. Mitchell
  • Jong-Shi Pang
  • Bin Yu
    • Categories Branch and Cut Algorithms, Complementarity and Variational Inequalities Tags , ,

    A linear program with linear complementarity constraints (LPCC) requires the minimization of a linear objective over a set of linear constraints together with additional linear complementarity constraints. This class has emerged as a modeling paradigm for a broad collection of problems, including bilevel programs, Stackelberg games, inverse quadratic programs, and problems involving equilibrium constraints. The … Read more

    Branch-and-Cut approaches for p-Cluster Editing

  • Teobaldo Bulhões
  • Lucídio Cabral
  • Anand Subramanian
  • Gilberto Sousa
    • Categories Branch and Cut Algorithms Tags , ,

    This paper deals with a variant of the well-known Cluster Editing Problem (CEP), more precisely, the \textit{p}-CEP, in which a given input graph should be edited by adding and/or removing edges in such a way that \textit{p} vertex-disjoint cliques (clusters) are generated with the minimum number of editions. We introduce several valid inequalities where some … Read more

    Bi-objective branch–and–cut algorithms: Applications to the single source capacitated facility location problem

  • Matthias Ehrgott
  • Sune Lauth Gadegaard
  • Lars Relund Nielsen
    • Categories Branch and Cut Algorithms, Multi-Criteria Optimization Tags , , ,

    Most real–world optimization problems are of a multi–objective nature, involving objectives which are conflicting and incomparable. Solving a multi–objective optimization problem requires a method which can generate the set of rational compromises between the objectives. In this paper, we propose two distinct bound set based branch–and–cut algorithms for bi–objective combinatorial optimization problems, based on implicitly … Read more

    Projection Results for the k-Partition Problem

  • Jamie Fairbrother
  • Adam N. Letchford
    • Categories Branch and Cut Algorithms, Polyhedra Tags , ,

    The k-partition problem is an NP-hard combinatorial optimisation problem with many applications. Chopra and Rao introduced two integer programming formulations of this problem, one having both node and edge variables, and the other having only edge variables. We show that, if we take the polytopes associated with the `edge-only’ formulation, and project them into a … Read more

    Column Generation based Alternating Direction Methods for solving MINLPs

  • Ivo Nowak
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Parallel Algorithms Tags , , , , , ,

    Traditional decomposition based branch-and-bound algorithms, like branch-and-price, can be very efficient if the duality gap is not too large. However, if this is not the case, the branch-and-bound tree may grow rapidly, preventing the method to find a good solution. In this paper, we present a new decompositon algorithm, called ADGO (Alternating Direction Global Optimization … Read more

    A Computational Comparison of Symmetry Handling Methods for Mixed Integer Programs

  • Marc E. Pfetsch
  • Thomas Rehn
    • Categories (Mixed) Integer Linear Programming Tags , , , ,

    The handling of symmetries in mixed integer programs in order to speed up the solution process of branch-and-cut solvers has recently received significant attention, both in theory and practice. This paper compares different methods for handling symmetries using a common implementation framework. We start by investigating the computation of symmetries and analyze the symmetries present … Read more

    Mathematical programming algorithms for spatial cloaking

  • Alberto Ceselli
  • Maria Luisa Damiani
  • Giovanni Righini
  • Diego Valorsi
    • Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering, Combinatorial Optimization Tags , , ,

    We consider a combinatorial optimization problem for spatial information cloaking. The problem requires to compute one or several disjoint arborescences on a graph from a predetermined root or subset of candidate roots, so that the number of vertices in the arborescences is minimized but a given threshold on the overall weight associated with the vertices … Read more

    Branch-and-Cut for Linear Programs with Overlapping SOS1 Constraints

  • Tobias Fischer
  • Marc E. Pfetsch
    • Categories Integer Programming Tags , , , , ,

    SOS1 constraints require that at most one of a given set of variables is nonzero. In this article, we investigate a branch-and-cut algorithm to solve linear programs with SOS1 constraints. We focus on the case in which the SOS1 constraints overlap. The corresponding conflict graph can algorithmically be exploited, for instance, for improved branching rules, … Read more

    Single-Commodity Robust Network Design with Finite and Hose Demand Sets

  • Valentina Cacchiani
  • Frauke Liers
  • Andrea Lodi
  • Michael Juenger
  • Daniel Schmidt
    • Categories Branch and Cut Algorithms, Network Optimization, Robust Optimization Tags , , ,

    We study a single-commodity Robust Network Design problem (sRND) defined on an undirected graph. Our goal is to determine minimum cost capacities such that any traffic demand from a given uncertainty set can be satisfied by a feasible single-commodity flow. We consider two ways of representing the uncertainty set, either as a finite list of … Read more

    A Polyhedral Investigation of Star Colorings

  • Christopher Hojny
  • Marc E. Pfetsch
    • Categories Polyhedra Tags , , , ,

    Given a weighted undirected graph~$G$ and a nonnegative integer~$k$, the maximum~$k$-star colorable subgraph problem consists of finding an induced subgraph of~$G$ which has maximum weight and can be star colored with at most~$k$ colors; a star coloring does not color adjacent nodes with the same color and avoids coloring any 4-path with exactly two colors. … Read more