Integer Programming

Beating the SDP bound for the floor layout problem: A simple combinatorial idea

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

    For many Mixed-Integer Programming (MIP) problems, high-quality dual bounds can obtained either through advanced formulation techniques coupled with a state-of-the-art MIP solver, or through Semidefinite Programming (SDP) relaxation hierarchies. In this paper, we introduce an alternative bounding approach that exploits the “combinatorial implosion” effect by solving portions of the original problem and aggregating this information … 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

    Risk Averse Shortest Path Interdiction

  • Siqian Shen
  • Yongjia Song
    • Categories 0-1 Programming, Network Optimization, Stochastic Programming

    We consider a Stackelberg game in a network, where a leader minimizes the cost of interdicting arcs and a follower seeks the shortest distance between given origin and destination nodes under uncertain arc traveling cost. In particular, we consider a risk-averse leader, who aims to keep high probability that the follower’s traveling distance is longer … Read more

    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