Refine
Document Type
- Article (3)
Language
- English (3)
Has Fulltext
- yes (3)
Keywords
- Software (2)
- Theoretical Computer Science (2)
MIPLIB 2010
(2011)
This paper reports on the fifth version of theMixed Integer Programming Library. The miplib 2010 is the first miplib release that has been assembled by a large group from academia and from industry, all of whom work in integer programming. There was mutual consent that the concept of the library had to be expanded in order to fulfill the needs of the community. The new version comprises 361 instances sorted into several groups. This includes the main benchmark test set of 87 instances, which are all solvable by today’s codes, and also the challenge test set with 164 instances, many of which are currently unsolved. For the first time, we include scripts to run automated tests in a predefined way. Further, there is a solution checker to test the accuracy of provided solutions using exact arithmetic.
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 found integer feasible solution. It uses global structures available within MIP solvers to iteratively fix integer variables and propagate these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. If sufficiently many variables can be fixed that way, the resulting problem is solved first as an LP, and then as an auxiliary MIP if the rounded LP solution does not provide a feasible solution already. We present three primal heuristics that use this scheme based on different global structures. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about 60% of the instances and by this, help to improve several performance measures for MIP solvers, including the primal integral and the average solving time.
The analysis of infeasible subproblems plays an important role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems: conflict graph analysis and dual proof analysis. While conflict graph analysis detects sets of contradicting variable bounds in an implication graph, dual proof analysis derives valid linear constraints from the proof of the dual LP’s unboundedness. The main contribution of this paper is twofold. Firstly, we present three enhancements of dual proof analysis: presolving via variable cancellation, strengthening by applying mixed integer rounding functions, and a filtering mechanism. Further, we provide a comprehensive computational study evaluating the impact of every presented component regarding dual proof analysis. Secondly, this paper presents the first combined approach that uses both conflict graph and dual proof analysis simultaneously within a single MIP solution process. All experiments are carried out on general MIP instances from the standard public test set Miplib 2017; the presented algorithms have been implemented within the non-commercial MIP solver and the commercial MIP solver .
