Combinatorial Optimization

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

    Relaxation Analysis for the Dynamic Knapsack Problem with Stochastic Item Sizes

  • Daniel Blado
  • Alejandro Toriello
    • Categories Combinatorial Optimization, Dynamic Programming Tags ,

    We consider a version of the knapsack problem in which an item size is random and revealed only when the decision maker attempts to insert it. After every successful insertion the decision maker can dynamically choose the next item based on the remaining capacity and available items, while an unsuccessful insertion terminates the process. We … Read more

    Novel formulations for general and security Stackelberg games

  • Carlos Casorrán
  • Bernard Fortz
  • Martine Labbé
  • Fernando Ordóñez
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Polyhedra Tags , , ,

    In this paper we analyze general Stackelberg games (SGs) and Stackelberg security games (SSGs). SGs are hierarchical adversarial games where players select actions or strategies to optimize their payoffs in a sequential manner. SSGs are a type of SGs that arise in security applications, where the strategies of the player that acts first consist in … Read more

    Branch-and-bound for biobjective mixed-integer linear programming

  • Nathan Adelgren
  • Akshay Gupte
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Multi-Criteria Optimization Tags , , , ,

    We present a generic branch-and-bound algorithm for finding all the Pareto solutions of a biobjective mixed-integer linear program. The main contributions are new algorithms for obtaining dual bounds at a node, checking node fathoming, presolve, and duality gap measurement. Our branch-and-bound is predominantly a decision space search method because the branching is performed on the … Read more

    Modulation Design for MIMO-CoMP HARQ

  • Zhi Ding
  • Hans D Mittelmann
  • Wenhao Wu
    • Categories Applications - Science and Engineering, Combinatorial Optimization Tags , , , ,

    Modulation diversity (MoDiv) is a simple and practical transmission enhancement technique that utilizes different modulation mappings to reduce packet loss rate and achieve higher link throughput. MoDiv is particularly meaningful and effective in hybrid-ARQ (HARQ) systems. We study the deployment and optimization of MoDiv for HARQ in a MIMOcoordinated multi-point (MIMO-CoMP) scenario under Rician fading … Read more

    An Effective Dynamic Programming Algorithm for the Minimum-Cost Maximal Knapsack Packing

  • Fabio Furini
  • Ivana Ljubić
  • Markus Sinnl
    • Categories Combinatorial Optimization, Dynamic Programming, Integer Programming

    Given a set of n items with profits and weights and a knapsack capacity C, we study the problem of finding a maximal knapsack packing that minimizes the profit of selected items. We propose for the first time an effective dynamic programming (DP) algorithm which has O(nC) time complexity and O(n+C) space complexity. We demonstrate … Read more

    Extended Formulations and Branch-and-Cut Algorithms for the Black-and-White Traveling Salesman Problem

  • Luís Gouveia
  • Markus Leitner
  • Mario Ruthmair
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Transportation

    In this paper we study integer linear programming models and develop branch-and-cut algorithms to solve the Black-and-White Traveling Salesman Problem (BWTSP) (Bourgeois et al., 2003) which is a variant of the well known Traveling Salesman Problem (TSP). Two strategies to model the BWTSP have been used in the literature. The problem is either modeled on … Read more

    Exact algorithms for bi-objective ring tree problems with reliability measures

  • Alessandro Hill
  • Silvia Schwarze
    • Categories Branch and Cut Algorithms, Multi-Criteria Optimization, Network Optimization Tags , , , , ,

    We introduce bi-objective models for ring tree network design with a focus on network reliability within telecommunication applications. Our approaches generalize the capacitated ring tree problem (CRTP) which asks for a partially reliable topology that connects customers with different security requirements to a depot node by combined ring and tree graphs. While the CRTP aims … Read more

    Decomposition-Based Approximation Algorithms for the One-Warehouse Multi-Retailer Problem with Concave Batch Order Costs

  • Maged M. Dessouky
  • Weihong Hu
  • Alejandro Toriello
  • Zhuoting Yu
    • Categories Approximation Algorithms, Production and Logistics, Supply Chain Management Tags , ,

    We study the one-warehouse multi-retailer (OWMR) problem under deterministic dynamic demand and concave batch order costs, where order batches have an identical capacity and the order cost function for each facility is concave within the batch. Under appropriate assumptions on holding cost structure, we obtain lower bounds via a decomposition that splits the two-echelon problem … Read more

    Facets for Node-Capacitated Multicut Polytopes from Path-Block Cycles with Two Common Nodes

  • Michael M. Sørensen
    • Categories Cutting Plane Approaches, Polyhedra

    A path-block cycle is a graph that consists of several cycles that all intersect in a common subset of nodes. The associated path-block-cycle inequalities are valid, and sometimes facet-defining, inequalities for polytopes in connection with graph partitioning problems and corresponding multicut problems. Special cases of the inequalities were introduced by De Souza & Laurent (1995) … Read more