Cutting Plane Approaches

Facets for Continuous Multi-Mixing Set with General Coefficients and Bounded Integer Variables

  • Manish Bansal
  • Kiavash Kianfar
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Integer Programming Tags , , , , ,

    Bansal and Kianfar introduced continuous multi-mixing set where the coefficients satisfy the so-called n-step MIR conditions and developed facet-defining inequalities for this set. In this paper, we first generalize their inequalities for the continuous multi-mixing set with general coefficients (where no conditions are imposed on the coefficients) and show that they are facet-defining in many … Read more

    Operations that preserve the covering property of the lifting region

  • Amitabh Basu
  • Joseph Paat
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches

    We contribute to the theory for minimal liftings of cut-generating functions. In particular, we give three operations that preserve the so-called covering property of certain structured cut-generating functions. This has the consequence of vastly expanding the set of undominated cut generating functions which can be used computationally, compared to known examples from the literature. The … Read more

    An Exact Extended Formulation for the Unrelated Parallel Machine Total Weighted Completion Time Problem

  • Kerem Bülbül
  • Halil Sen
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Scheduling

    The plethora of research on NP-hard parallel machine scheduling problems is focused on heuristics due to the theoretically and practically challenging nature of these problems. Only a handful of exact approaches are available in the literature, and most of these suffer from scalability issues. Moreover, the majority of the papers on the subject are restricted … Read more

    On the exact separation of rank inequalities for the maximum stable set problem

  • Stefano Coniglio
  • Stefano Gualandi
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Polyhedra Tags , , , , ,

    When addressing the maximum stable set problem on a graph G = (V,E), rank inequalities prescribe that, for any subgraph G[U] induced by U ⊆ V , at most as many vertices as the stability number of G[U] can be part of a stable set of G. These inequalities are very general, as many of … Read more

    n-step cycle inequalities: facets for continuous n-mixing set and strong cuts for multi-module capacitated lot-sizing problem

  • Manish Bansal
  • Kiavash Kianfar
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Production and Logistics Tags , , , , ,

    In this paper, we introduce a generalization of the continuous mixing set (which we refer to as the continuous n-mixing set). This set is closely related to the feasible set of the multi-module capacitated lot-sizing (MML) problem with(out) backlogging. We develop new classes of valid inequalities for this set, referred to as n’-step cycle inequalities, … Read more

    The split-demand one-commodity pickup-and-delivery travelling salesman problem

  • Juan-José Salazar-González
  • Beatriz Santos-Hernández
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches, Transportation

    This paper introduces a new vehicle routing problem transferring one commodity between customers with a capacitated vehicle that can visit a customer more than once,although a maximum number of visits must be respected. It generalizes the capacitated vehicle routing problem with split demands and some other variants recently addressed in the literature. We model the … Read more

    Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. III. Foundations for the k-Dimensional Case with Applications to k=2

  • Amitabh Basu
  • Robert Hildebrand
  • Matthias Köppe
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    We develop foundational tools for classifying the extreme valid functions for the k-dimensional infinite group problem. In particular, (1) we present the general regular solution to Cauchy’s additive functional equation on bounded convex domains. This provides a k-dimensional generalization of the so-called interval lemma, allowing us to deduce affine properties of the function from certain … Read more

    Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse

  • Merve Bodur
  • Sanjeeb Dash
  • Oktay Gunluk
  • James R. Luedtke
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Stochastic Programming Tags , ,

    With stochastic integer programming as the motivating application, we investigate techniques to use integrality constraints to obtain improved cuts within a Benders decomposition algorithm. We compare the effect of using cuts in two ways: (i) cut-and-project, where integrality constraints are used to derive cuts in the extended variable space, and Benders cuts are then used … Read more

    Decomposition Algorithm for Optimizing Multi-server Appointment Scheduling with Chance Constraints

  • Yan Deng
  • Siqian Shen
    • Categories Cutting Plane Approaches, Stochastic Programming

    We schedule appointments with random service durations on multiple servers with operating time limits. We minimize the costs of operating servers and serving appointments, subject to a joint chance constraint limiting the risk of server overtime. Using finite samples of the uncertainty, we formulate the problem as a mixed-integer linear program, and propose a two-stage … Read more