Integer Programming

Facial reduction heuristics and the motivational example of mixed-integer conic optimization

  • Henrik A. Friberg
    • Categories Integer Programming, Linear, Cone and Semidefinite Programming Tags , ,

    Facial reduction heuristics are developed in the interest of added performance and reliability in methods for mixed-integer conic optimization. Specifically, the process of branch-and-bound is shown to spawn subproblems for which the conic relaxations are difficult to solve, and the objective bounds of linear relaxations are arbitrarily weak. While facial reduction algorithms already exist to … Read more

    Min-max-min Robust Combinatorial Optimization Subject to Discrete Uncertainty

  • Christoph Buchheim
  • Jannis Kurtz
    • Categories 0-1 Programming, Combinatorial Optimization, Robust Optimization Tags , ,

    We consider combinatorial optimization problems with uncertain objective functions. In the min-max-min robust optimization approach, a fixed number k of feasible solutions is computed such that the respective best of them is optimal in the worst case. The idea is to calculate a set of candidate solutions in a potentially expensive preprocessing and then select … Read more

    Parallel Scenario Decomposition of Risk Averse 0-1 Stochastic Programs

  • Shabbir Ahmed
  • Yan Deng
  • Siqian Shen
    • Categories 0-1 Programming, Parallel Algorithms, Stochastic Programming

    In this paper, we extend a recently proposed scenario decomposition algorithm (Ahmed (2013)) for risk-neutral 0-1 stochastic programs to the risk-averse setting. Specifically, we consider risk-averse 0-1 stochastic programs with objective functions based on coherent risk measures. Using a dual representation of a coherent risk measure, we first derive an equivalent minimax reformulation of the … Read more

    Satisficing Models under Uncertainty

  • Patrick Jaillet
  • Sanjay Dominik Jena
  • Tsan Sheng Ng
  • Melvyn Sim
    • Categories Integer Programming, Robust Optimization, Stochastic Programming Tags , , ,

    Satisficing, as an approach to decision-making under uncertainty, aims at achieving solutions that satisfy the problem’s constraints as well as possible. Mathematical optimization problems that are related to this form of decision-making include the P-model of Charnes and Cooper (1963). In this paper, we propose a general framework of satisficing decision criteria, and show a … 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

    A branch-price-and-cut algorithm for the vehicle routing problem with time windows and multiple deliverymen

  • Reinaldo Morabito
  • Pedro Munari
    • Categories Combinatorial Optimization, Integer Programming, Transportation Tags , , , , , ,

    We address a variant of the vehicle routing problem with time windows (VRPTW) that includes the decision of how many deliverymen should be assigned to each vehicle. In this variant, the service time at each customer depends on the size of the respective demand and on the number of deliverymen assigned to visit this customer. … 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