Optimization Online


Two-row and two-column mixed-integer presolve using hash-based pairing methods

Weikun Chen (chenw***at***zib.de)
Patrick Gemander (patrick.gemander***at***fau.de)
Ambros Gleixner (gleixner***at***zib.de)
Leona Gottwald (gottwald***at***zib.de)
Alexander Martin (alexander.martin***at***fau.de)
Dieter Weninger (dieter.weninger***at***fau.de)

Abstract: In state-of-the-art mixed-integer programming solvers, a large array of reduction techniques are applied to simplify the problem and strengthen the model formulation before starting the actual branch-and-cut phase. Despite their mathematical simplicity, these methods can have significant impact on the solvability of a given problem. However, a crucial property for employing presolving techniques successfully is their speed. Hence, most methods inspect constraints or variables individually in order to guarantee linear complexity. In this paper, we present new hashing-based pairing mechanisms that help to overcome known performance limitations of more powerful presolving techniques that consider pairs of rows or columns. Additionally, we develop an enhancement to one of these presolving techniques by exploiting the presence of set-packing structures on binary variables in order to strengthen the resulting reductions without increasing runtime. We analyze the impact of these methods on the MIPLIB 2017 benchmark set based on an implementation in the MIP solver SCIP.

Keywords: Linear programming, mixed-integer linear programming, optimization solver, presolve

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Optimization Software and Modeling Systems (Optimization Software Benchmark )

Category 3: Combinatorial Optimization (Polyhedra )


Download: [PDF]

Entry Submitted: 09/03/2019
Entry Accepted: 09/03/2019
Entry Last Modified: 07/08/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society