Monoidal Cut Strengthening and Generalized Mixed-Integer Rounding for Disjunctions and Complementarity Constraints

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

    In the early 1980s, Balas and Jeroslow presented monoidal disjunctive cuts exploiting the integrality of variables. This article investigates the relation of monoidal cut strengthening to other classes of cutting planes for general two-term disjunctions. We introduce a generalization of mixed-integer rounding cuts and show equivalence to monoidal disjunctive cuts. Moreover, we demonstrate the effectiveness … Read more

    Minimization and Maximization Versions of the Quadratic Traveling Salesman Problem

  • Oswin Aichholzer
  • Anja Fischer
  • Frank Fischer
  • J. Fabian Meier
  • Ulrich Pferschy
  • Alexander Pilz
  • Rostislav Stanek
    • Categories Combinatorial Optimization, Integer Programming Tags , , , ,

    The traveling salesman problem (TSP) asks for a shortest tour through all vertices of a graph with respect to the weights of the edges. The symmetric quadratic traveling salesman problem (SQTSP) associates a weight with every three vertices traversed in succession. If these weights correspond to the turning angles of the tour, we speak of … Read more

    Computational study of valid inequalities for the maximum hBccut problem

  • Miguel F. Anjos
  • Sébastien Le Digabel
  • Vilmar Jefté Rodrigues de Sousa
    • Categories Combinatorial Optimization, Cutting Plane Approaches, Semi-definite Programming Tags , , ,

    We consider the maximum k-cut problem that consists in partitioning the vertex set of a graph into k subsets such that the sum of the weights of edges joining vertices in different subsets is maximized. We focus on identifying effective classes of inequalities to tighten the semidefinite programming relaxation. We carry out an experimental study … Read more

    An Adaptive Partition-based Level Decomposition for Solving Two-stage Stochastic Programs with Fixed Recourse

  • Welington de Oliveira
  • Yongjia Song
  • Wim van Ackooij
    • Categories Stochastic Programming

    We present a computational study of several strategies to solve two-stage stochastic linear programs by integrating the adaptive partition-based approach with level decomposition. A partition-based formulation is a relaxation of the original stochastic program, obtained by aggregating variables and constraints according to a scenario partition. Partition refinements are guided by the optimal second-stage dual vectors … Read more

    A polyhedral study of the cardinality constrained multi-cycle and multi-chain problem on directed graphs

  • Vicky Mak-Hau
    • Categories Polyhedra Tags , , , ,

    In this paper, we study the Cardinality Constrained Multi-cycle Problem (CCMcP) and the Car- dinality Constrained Cycle and Chain Problem (CCCCP). A feasible solution allows one or more cardinality-constrained cycles to exist on the digraph. A vertex can only be involved in at most one cycle, and there may be vertices not involved in any … Read more

    Solving Large Aircraft Landing Problems on Multiple Runways by Applying a Constraint Programming Approach

  • Amir Salehipour
    • Categories Applications - OR and Management Sciences Tags , ,

    Aircraft Landing Problem is to assign an airport’s runways to the arrival aircraft as well as to schedule the landing time of these aircraft. In this paper, due to the complexity of the problem, which is NP-hard, we develop an iterative-based heuristic by exploiting special characteristics of the problem. Computational results show the developed approach … 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

    On quantile cuts and their closure for chance constrained optimization problems

  • Shabbir Ahmed
  • Weijun Xie
    • Categories Cutting Plane Approaches, Stochastic Programming Tags , ,

    A chance constrained optimization problem over a finite distribution involves a set of scenario constraints from which a small subset can be violated. We consider the setting where all scenario constraints are mixed-integer convex. Existing works typically consider a mixed integer nonlinear programming (MINLP) formulation of this problem by introducing binary variables to indicate which … Read more

    A doubly nonnegative relaxation for modularity density maximization

  • Yoichi Izunaga
  • Tomomi Matsui
  • Yoshitsugu Yamamoto
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    Modularity proposed by Newman and Girvan is the most commonly used measure when the nodes of a graph are grouped into communities consisting of tightly connected nodes. However, some authors pointed out drawbacks of the modularity, the main issue of which is resolution limit. Resolution limit refers to the sensitivity of the modularity to the … Read more

    Optimization Driven Scenario Grouping

  • Shabbir Ahmed
  • Santanu S. Dey
  • Deepak Rajan
  • Kevin Ryan
    • Categories 0-1 Programming, Stochastic Programming Tags ,

    Scenario decomposition algorithms for stochastic programs compute bounds by dualizing all nonanticipativity constraints and solving individual scenario problems independently. We develop an approach that improves upon these bounds by re-enforcing a carefully chosen subset of nonanticipativity constraints, effectively placing scenarios into ‘groups’. Specifically, we formulate an optimization problem for grouping scenarios that aims to improve … Read more