branch-and-cut

Exact Methods for Discrete Γ-Robust Interdiction Problems with an Application to the Bilevel Knapsack Problem

  • Yasmine Beck
  • Ivana Ljubić
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Robust Optimization Tags , , , ,

    Developing solution methods for discrete bilevel problems is known to be a challenging task – even if all parameters of the problem are exactly known. Many real-world applications of bilevel optimization, however, involve data uncertainty. We study discrete min-max problems with a follower who faces uncertainties regarding the parameters of the lower-level problem. Adopting a … Read more

    Multi-depot routing with split deliveries: Models and a branch-and-cut algorithm

  • Luís Gouveia
  • Markus Leitner
  • Mario Ruthmair
    • Categories Applications - OR and Management Sciences Tags , , , ,

    We study the multi-depot split-delivery vehicle routing problem (MDSDVRP) which combines the advantages and potential cost-savings of multiple depots and split-deliveries and develop the first exact algorithm for this problem. We propose an integer programming formulation using a small number of decision variables and several sets of valid inequalities. These inequalities focus on ensuring the … Read more

    Complexity of optimizing over the integers

  • Amitabh Basu
    • Categories (Mixed) Integer Nonlinear Programming, Convex Optimization Tags , ,

    In the first part of this paper, we present a unified framework for analyzing the algorithmic complexity of any optimization problem, whether it be continuous or discrete in nature. This helps to formalize notions like “input”, “size” and “complexity” in the context of general mathematical optimization, avoiding context dependent definitions which is one of the … Read more

    On the generation of Metric TSP instances with a large integrality gap by branch-and-cut.

  • Luca Maria Gambardella
  • Stefano Gualandi
  • Monaldo Mastrolilli
  • Eleonora Vercesi
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization Tags , , ,

    This paper introduces a computational method for generating metric Travelling Salesperson Problem (TSP) instances having a large integrality gap. The method is based on the solution of an NP-hard problem, called IH-OPT, that takes in input a fractional solution of the Subtour Elimination Problem (SEP) on a TSP instance and compute a TSP instance having … Read more

    On fault-tolerant low-diameter clusters in graphs

  • Yajun Lu
  • Hosseinali Salemi
  • Balabhaskar Balasundaram
  • Austin Buchanan
    • Categories 0-1 Programming, Branch and Cut Algorithms, Network Optimization Tags , , , ,

    Cliques and their generalizations are frequently used to model “tightly knit” clusters in graphs and identifying such clusters is a popular technique used in graph-based data mining. One such model is the $s$-club, which is a vertex subset that induces a subgraph of diameter at most $s$. This model has found use in a variety … Read more

    Solving Graph Partitioning on Sparse Graphs: Cuts, Projections, and Extended Formulations

  • Demetrios Papazaharias
  • Jose L. Walteros
    • Categories Combinatorial Optimization, Network Optimization Tags , , , ,

    This paper explores new solution approaches for the graph partitioning problem. While the classic formulations for graph partitioning are compact, they either suffer from a poor relaxation, symmetry, or contain a cubic number of constraints regardless of the graph density. These shortcomings often result in poor branch-and-bound performance. We approach this problem from perspective of … Read more

    Second-Order Conic and Polyhedral Approximations of the Exponential Cone: Application to Mixed-Integer Exponential Conic Programs

  • Ye Qing
  • Weijun Xie
    • Categories Integer Programming Tags , , , ,

    Exponents and logarithms exist in many important applications such as logistic regression, maximum likelihood, relative entropy and so on. Since the exponential cone can be viewed as the epigraph of perspective of the natural exponential function or the hypograph of perspective of the natural logarithm function, many mixed-integer nonlinear convex programs involving exponential or logarithm … Read more

    Sequential Competitive Facility Location: Exact and Approximate Algorithms

  • Mingyao Qi
  • Ruiwei Jiang
  • Siqian Shen
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Facility Planning and Design Tags , , , , ,

    We study a competitive facility location problem (CFLP), where two firms sequentially open new facilities within their budgets, in order to maximize their market shares of demand that follows a probabilistic choice model. This process is a Stackelberg game and admits a bilevel mixed-integer nonlinear program (MINLP) formulation. We derive an equivalent, single-level MINLP reformulation … Read more

    A Survey on Mixed-Integer Programming Techniques in Bilevel Optimization

  • Thomas Kleinert
  • Martine Labbé
  • Ivana Ljubić
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , , ,

    Bilevel optimization is a field of mathematical programming in which some variables are constrained to be the solution of another optimization problem. As a consequence, bilevel optimization is able to model hierarchical decision processes. This is appealing for modeling real-world problems, but it also makes the resulting optimization models hard to solve in theory and … Read more

    Closing the Gap in Linear Bilevel Optimization: A New Valid Primal-Dual Inequality

  • Thomas Kleinert
  • Martine Labbé
  • Martin Schmidt
  • Fränk Plein
    • Categories (Mixed) Integer Linear Programming, Complementarity and Variational Inequalities, Cutting Plane Approaches Tags , , ,

    Linear bilevel optimization problems are often tackled by replacing the linear lower-level problem with its Karush–Kuhn–Tucker (KKT) conditions. The resulting single-level problem can be solved in a branch-and-bound fashion by branching on the complementarity constraints of the lower-level problem’s optimality conditions. While in mixed-integer single-level optimization branch- and-cut has proven to be a powerful extension … Read more