Integer Programming

A Finitely Convergent Cutting Plane, and a Bender’s Decomposition Algorithm for Mixed-Integer Convex and Two-Stage Convex Programs using Cutting Planes

  • Fengqiao Luo
  • Sanjay Mehrotra
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Stochastic Programming Tags , , ,

    We consider a general mixed-integer convex program. We first develop an algorithm for solving this problem, and show its nite convergence. We then develop a finitely convergent decomposition algorithm that separates binary variables from integer and continuous variables. The integer and continuous variables are treated as second stage variables. An oracle for generating a parametric … Read more

    Lower bound on size of branch-and-bound trees for solving lot-sizing problem

  • Santanu S. Dey
  • Prachi Shah
    • Categories 0-1 Programming, Integer Programming Tags , ,

    We show that there exists a family of instances of the lot-sizing problem, such that any branch-and-bound tree that solves them requires an exponential number of nodes, even in the case when the branchings are performed on general split disjunctions. Article Download View Lower bound on size of branch-and-bound trees for solving lot-sizing problem

    Facets of the Total Matching Polytope for bipartite graphs

  • Luca Ferrarini
    • Categories 0-1 Programming, Combinatorial Optimization, Cutting Plane Approaches Tags , , ,

    The Total Matching Polytope generalizes the Stable Set Polytope and the Matching Polytope. In this paper, we give the perfect formulation for Trees and we derive two new families of valid inequalities, the balanced biclique inequalities which are always facet-defining and the non-balanced lifted biclique inequalities obtained by a lifting procedure, which are facet-defining for … Read more

    Recognizing Integrality of Weighted Rectangles Partitions

  • Paul Deuker
  • Ulf Friedrich
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    Given a grid of active and inactive pixels, the weighted rectangles partitioning (WRP) problem is to find a maximum-weight partition of the active pixels into rectangles. WRP is formulated as an integer programming problem and instances with an integral relaxation polyhedron are characterized by a balanced problem matrix. A complete characterization of these balanced instances … Read more

    Freight-on-Transit for urban last-mile deliveries: A Strategic Planning Approach

  • Diego Delle Donne
  • Laurent Alfandari
  • Claudia Archetti
  • Ivana Ljubić
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Transportation Tags , , ,

    We study a delivery strategy for last-mile deliveries in urban areas which combines freight transportation with mass mobility systems with the goal of creating synergies contrasting negative externalities caused by transportation. The idea is to use the residual capacity on public transport means for moving freights within the city. In particular, the system is such … Read more

    Modeling Design and Control Problems Involving Neural Network Surrogates

  • Dominic Yang
  • Prasanna Balaprakash
  • Sven Leyffer
    • Categories (Mixed) Integer Nonlinear Programming, Control Applications, Nonsmooth Optimization Tags , , , ,

    We consider nonlinear optimization problems that involve surrogate models represented by neural net-works. We demonstrate first how to directly embed neural network evaluation into optimization models, highlight a difficulty with this approach that can prevent convergence, and then characterize stationarity of such models. We then present two alternative formulations of these problems in the specific … Read more

    Sparse multi-term disjunctive cuts for the epigraph of a function of binary variables

  • Rui Chen
  • James R. Luedtke
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , ,

    We propose a new method for separating valid inequalities for the epigraph of a function of binary variables. The proposed inequalities are disjunctive cuts defined by disjunctive terms obtained by enumerating a subset $I$ of the binary variables. We show that by restricting the support of the cut to the same set of variables $I$, … Read more

    Schreier-Sims Cuts meet Stable Set: Preserving Problem Structure when Handling Symmetries

  • Christopher Hojny
  • Marc E. Pfetsch
  • José Verschae
    • Categories 0-1 Programming Tags , ,

    Symmetry handling inequalities (SHIs) are a popular tool to handle symmetries in integer programming. Despite their successful application in practice, only little is known about the interaction of SHIs with optimization problems. In this article, we focus on SST cuts, an attractive class of SHIs, and investigate their computational and polyhedral consequences for optimization problems. … Read more

    On the Complexity of Separation From the Knapsack Polytope

  • Alberto Del Pia
  • Jeff Linderoth
  • Haoran Zhu
    • Categories 0-1 Programming Tags , ,

    We close three open problems in the separation complexity of valid inequalities for the knapsack polytope. Specifically, we establish that the separation problems for extended cover inequalities, (1,k)-configuration inequalities, and weight inequalities are all NP-complete. We also give a number of special cases where the separation problem can be solved in polynomial time. Article Download … Read more

    On the Fairness of Aggregator’s Incentives in Residential Demand Response

  • Michael David de Souza Dutra
  • Natalia Alguacil Conde
    • Categories Energy, Integer Programming Tags , , , , ,

    The main motivation of this work is to provide an optimization-based tool for an aggregator involved in residential demand response (DR) programs. The proposed tool comply with the following requirements, which are widely accepted by the residential DR literature: (i) the aggregated consumption should be optimized under a particular utility’s target, such as the minimization … Read more