(Mixed) Integer Linear Programming

Combining Progressive Hedging with a Frank-Wolfe Method to Compute Lagrangian Dual Bounds in Stochastic Mixed-Integer Programming

  • Natashia Boland
  • Brian Dandurand
  • Andrew C. Eberhard
  • Jeff Linderoth
  • James R. Luedtke
  • Fabricio Oliveira
  • Jeffrey Christiansen
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , ,

    We present a new primal-dual algorithm for computing the value of the Lagrangian dual of a stochastic mixed-integer program (SMIP) formed by relaxing its nonanticipativity constraints. The algorithm relies on the well-known progressive hedging method, but unlike previous progressive hedging approaches for SMIP, our algorithm can be shown to converge to the optimal Lagrangian dual … 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

    The Quadratic Shortest Path Problem: Complexity, Approximability, and Solution Methods

  • Christoph Buchheim
  • Marc Goerigk
  • Federico Malucelli
  • Borzou Rostami
  • André Chassein
  • Davide Frey
  • Michael Hopf
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization Tags

    We consider the problem of finding a shortest path in a directed graph with a quadratic objective function (the QSPP). We show that the QSPP cannot be approximated unless P=NP. For the case of a convex objective function, an n-approximation algorithm is presented, where n is the number of nodes in the graph, and APX-hardness … Read more

    Strong mixed-integer formulations for the floor layout problem

  • Santanu S. Dey
  • Joey Huchette
  • Juan Pablo Vielma
    • Categories (Mixed) Integer Linear Programming, Facility Planning and Design Tags ,

    The floor layout problem (FLP) tasks a designer with positioning a collection of rectangular boxes on a fixed floor in such a way that minimizes total communication costs between the components. While several mixed integer programming (MIP) formulations for this problem have been developed, it remains extremely challenging from a computational perspective. This work takes … Read more

    Generation of Feasible Integer Solutions on a Massively Parallel Computer

  • Utku Koc
  • Sanjay Mehrotra
    • Categories (Mixed) Integer Linear Programming Tags , ,

    We present an approach to parallelize generation of feasible solutions of mixed integer linear programs in distributed memory high performance computing environments. The approach combines a parallel framework with feasibility pump (FP) as the rounding heuristic. The proposed approach runs multiple FP instances with different starting so- lutions concurrently, while allowing them to share information. … Read more

    Online Learning for Strong Branching Approximation in Branch-and-Bound

  • Quentin Louveaux
  • Alejandro Marcos Alvarez
  • Louis Wehenkel
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Data-Mining Tags , ,

    We present an online learning approach to variable branching in branch-and-bound for mixed-integer linear problems. Our approach consists in learning strong branching scores in an online fashion and in using them to take branching decisions. More specifically, numerical scores are used to rank the branching candidates. If, for a given variable, the learned approximation is … Read more

    The Vehicle Routing Problem with Occasional Drivers

  • Claudia Archetti
  • Martin Savelsbergh
  • M. Grazia Speranza
    • Categories (Mixed) Integer Linear Programming, Meta Heuristics, Transportation Tags , ,

    We consider a setting in which a company not only has a fleet of capacitated vehicles and drivers available to make deliveries, but may also use the services of occasional drivers who are willing to make a single delivery using their own vehicle in return for a small compensation if the delivery location is not … 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

    PIPS-SBB: A parallel distributed-memory branch-and-bound algorithm for stochastic mixed-integer programs

  • Lluís-Miquel Munguía
  • Deepak Rajan
  • Geoffrey Oxberry
    • Categories (Mixed) Integer Linear Programming, Parallel Algorithms, Stochastic Programming Tags , ,

    Stochastic mixed-integer programs (SMIPs) deal with optimization under uncertainty at many levels of the decision-making process. When solved as extensive formulation mixed- integer programs, problem instances can exceed available memory on a single workstation. To overcome this limitation, we present PIPS-SBB: a distributed-memory parallel stochastic MIP solver that takes advantage of parallelism at multiple levels … Read more

    Convex Hull Characterizations of Lexicographic Orderings

  • Warren Adams
  • Pietro Belotti
  • Ruobing Shen
    • Categories (Mixed) Integer Linear Programming, Polyhedra Tags , ,

    Given a p-dimensional nonnegative, integral vector α, this paper characterizes the convex hull of the set S of nonnegative, integral vectors x that is lexicographically less than or equal to α. To obtain a finite number of elements in S, the vectors x are restricted to be component-wise upper-bounded by an integral vector u. We … Read more