Polytopes Associated with Symmetry Handling

This paper investigates a polyhedral approach to handle symmetries in mixed-binary programs. We study symretopes, i.e., the convex hulls of all binary vectors that are lexicographically maximal in their orbit with respect to the symmetry group. These polytopes turn out to be quite complex. For practical use, we therefore develop an integer programming formulation with … Read more

On the Structure of Linear Programs with Overlapping Cardinality Constraints

Cardinality constraints enforce an upper bound on the number of variables that can be nonzero. This article investigates linear programs with cardinality constraints that mutually overlap, i.e., share variables. We present the components of a branch-and-cut solution approach, including new branching rules that exploit the structure of the corresponding conflict hypergraph. We also investigate valid … Read more

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

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

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

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

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

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

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

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

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