Cutting Plane Approaches

Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VI. The Curious Case of Two-Sided Discontinuous Functions

  • Matthias Köppe
  • Yuan Zhou
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    We construct a two-sided discontinuous piecewise linear minimal valid function for the 1-row Gomory–Johnson model which is not extreme, but which is not a convex combination of other piecewise linear minimal valid functions. This anomalous behavior results from combining features of Hildebrand’s two-sided discontinuous extreme functions and Basu–Hildebrand–Koeppe’s piecewise linear extreme function with irrational breakpoints. … Read more

    Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. V. Software for the continuous and discontinuous 1-row case

  • Chun Yu Hong
  • Matthias Köppe
  • Yuan Zhou
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    We present software for investigations with cut generating functions in the Gomory-Johnson model and extensions, implemented in the computer algebra system SageMath. CitationAn extended abstract of 8 pages appeared under the title “Software for cut-generating functions in the Gomory–Johnson model and beyond” in Proc. International Congress on Mathematical Software 2016ArticleDownload View PDF

    A Polyhedral Study on Chance Constrained Program with Random Right-Hand Side

  • Kai Huang
  • Bo Zeng
  • Ming Zhao
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Stochastic Programming Tags , , , , ,

    The essential structure of the mixed–integer programming formulation for chance–constrained program (CCP) is the intersection of multiple mixing sets with a $0-1$ knapsack. To improve our computational capacity on CCP, an underlying substructure, the (single) mixing set with a $0-1$ knapsack, has received substantial attentions recently. In this study, we consider a CCP problem with … 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

    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 Polyhedral Study of the Static Probabilistic Lot-Sizing Problem

  • Simge Küçükyavuz
  • Xiao Liu
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Cutting Plane Approaches

    We study the polyhedral structure of the static probabilistic lot-sizing (SPLS) problem and propose facets that subsume existing inequalities for this problem. In addition, the proposed inequalities give the convex hull description of a related stochastic lot-sizing problem. We propose a new compact formulation that exploits the simple recourse structure, which can be applied to … Read more

    Analysis of Sparse Cutting-plane for Sparse MILPs with Applications to Stochastic MILPs

  • Santanu S. Dey
  • Marco Molinaro
  • Qianyi Wang
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags ,

    In this paper, we present an analysis of the strength of sparse cutting-planes for mixed integer linear programs (MILP) with sparse formulations. We examine three kinds of problems: packing problems, covering problems, and more general MILPs with the only assumption that the objective function is non-negative. Given a MILP instance of one of these three … Read more

    Bilevel mixed-integer linear programs and the zero forcing set

  • Claudia D'Ambrosio
  • Leo Liberti
  • Pierre-Louis Poirion
  • Sonia Toubaline
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Integer Programming

    We study a class of bilevel binary linear programs with lower level variables in the upper-level constraints. Under certain assumptions, we prove that the problem can be reformulated as a single-level binary linear program, and propose a finitely terminating cut generation algorithm to solve it. We then relax the assumptions by means of a general … Read more

    A Benders Decomposition Approach for the Charging Station Location Problem with Plug-in Hybrid Electric Vehicles

  • Okan Arslan
  • Oya Ekin Karasan
    • Categories Cutting Plane Approaches, Facility Planning and Design, Network Optimization Tags , , , , ,

    The flow refueling location problem (FRLP) locates $p$ stations in order to maximize the flow volume that can be accommodated in a road network respecting the range limitations of the vehicles. This paper introduces the charging station location problem with plug-in hybrid electric vehicles (CSLP-PHEV) as a generalization of the FRLP. We consider not only … Read more