primal heuristics

A Multi-Reference Relaxation Enforced Neighborhood Search Heuristic in SCIP

  • Suresh Bolusani
  • Gioni Mexi
  • Mathieu Besançon
  • Mark Turner
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Optimization Software and Modeling Systems Tags , , ,

    This paper proposes and evaluates a Multi-Reference Relaxation Enforced Neighborhood Search (MRENS) heuristic within the SCIP solver. This study marks the first integration and evaluation of MRENS in a full-fledged MILP solver, specifically coupled with the recently-introduced Lagromory separator for generating multiple reference solutions. Computational experiments on the MIPLIB 2017 benchmark set show that MRENS, … Read more

    Using Multiple Reference Vectors and Objective Scaling in the Feasibility Pump

  • Timo Berthold
  • Gioni Mexi
  • Domenico Salvagnin
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming Tags ,

    The Feasibility Pump (FP) is one of the best-known primal heuristics for mixed-integer programming (MIP): more than 15 papers suggested various modifications of all of its steps. So far, no variant considered information across multiple iterations, but all instead maintained the principle to optimize towards a single reference integer point. In this paper, we evaluate … Read more

    Structure-driven fix-and-propagate heuristics for mixed integer programming

  • Timo Berthold
  • Gerald Gamrath
  • Stefan Heinz
  • Michael Winkler
    • Categories (Mixed) Integer Linear Programming Tags , , , ,

    Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They often provide good feasible solutions early and help to reduce the time needed to prove optimality. In this paper, we present a scheme for start heuristics that can be executed without previous knowledge of an LP solution or a previously … Read more

    Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms

  • Gregor Hendel
  • Matthias Miltenberger
  • Jakob Witzig
    • Categories (Mixed) Integer Linear Programming Tags , ,

    State-of-the-art solvers for mixed integer programs (MIP) govern a variety of algorithmic components. Ideally, the solver adaptively learns to concentrate its computational budget on those components that perform well on a particular problem, especially if they are time consuming. We focus on three such algorithms, namely the classes of large neighborhood search and diving heuristics … Read more

    A Center-Cut Algorithm for Quickly Obtaining Feasible Solutions and Solving Convex MINLP Problems

  • David E. Bernal Neira
  • Andreas Lundell
  • Tapio Westerlund
  • Jan Kronqvist
    • Categories (Mixed) Integer Nonlinear Programming Tags , , , ,

    Here we present a center-cut algorithm for convex mixed-integer nonlinear programming (MINLP) that can either be used as a primal heuristic or as a deterministic solution technique. Like many other algorithms for convex MINLP, the center-cut algorithm constructs a linear approximation of the original problem. The main idea of the algorithm is to use the … Read more

    Conflict Driven Diving for Mixed Integer Programming

  • Jakob Witzig
    • Categories (Mixed) Integer Linear Programming Tags , ,

    The analysis of infeasibility plays an important role in solving satisfiability problems (SAT) and mixed integer programs (MIPs). In mixed integer programming, this procedure is called conflict analysis. So far, modern MIP solvers use conflict analysis only for propagation and improving the dual bound, i.e., fathoming nodes that cannot contain feasible solutions. In this short … Read more

    Tackling Industrial-Scale Supply Chain Problems by Mixed-Integer Programming

  • Gerald Gamrath
  • Ambros Gleixner
  • Thorsten Koch
  • Matthias Miltenberger
  • Dieter Weninger
  • Dimitri Kniasew
  • Alexander Martin
  • Dominik Schlögel
    • Categories (Mixed) Integer Linear Programming, Supply Chain Management Tags , , , , ,

    SAP’s decision support systems for optimized supply network planning rely on mixed-integer programming as the core engine to compute optimal or near-optimal solutions. The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of a robust and future-proof decision support system for a large and diverse customer base. In this … Read more

    Alternating Criteria Search: A Parallel Large Neighborhood Search Algorithm for Mixed Integer Programs

  • Shabbir Ahmed
  • Lluís-Miquel Munguía
  • George L. Nemhauser
  • David A. Bader
  • Yufen Shao
    • Categories (Mixed) Integer Linear Programming, Parallel Algorithms Tags , , ,

    We present a parallel large neighborhood search framework for finding high quality primal solutions for generic Mixed Integer Programs (MIPs). The approach simultaneously solves a large number of sub-MIPs with the dual objective of reducing infeasibility and optimizing with respect to the original objective. Both goals are achieved by solving restricted versions of two auxiliary … Read more

    Using the analytic center in the feasibility pump

  • Daniel Baena
  • Jordi Castro
    • Categories (Mixed) Integer Linear Programming Tags , , , ,

    The feasibility pump (FP) [5,7] has proved to be a successful heuristic for finding feasible solutions of mixed integer linear problems (MILPs). FP was improved in [1] for finding better quality solutions. Briefly, FP alternates between two sequences of points: one of feasible so- lutions for the relaxed problem (but not integer), and another of … Read more