Invited Session Tue.3.H 2013

Tuesday, 15:15 - 16:45 h, Room: H 2013

Cluster 11: Integer & mixed-integer programming [...]

Advances in mixed integer programming

 

Chair: Alexander Martin

 

 

Tuesday, 15:15 - 15:40 h, Room: H 2013, Talk 1

Timo Berthold
Measuring the impact of primal heuristics

 

Abstract:
In modern MIP-solvers like the branch-cut-and-price-framework SCIP, primal heuristics play a major role in finding and improving feasible solutions at the early steps of the solution process.
However, classical performance measures for MIP such as time to optimality or number of branch-and-bound nodes reflect the impact of primal heuristics on the overall solving process rather badly. Reasons for this are that they typically depend on the convergence of the dual bound and that they only consider instances which can actually be solved within a given time limit.
In this talk, we discuss the question of how the quality of a primal heuristic should be evaluated and introduce a new performance measure, the "primal integral''. It depends on the quality of solutions found during the solving process as well as on the point in time when they are found. Thereby, it assesses the impact of primal heuristics on the ability to find feasible solutions of good quality, in particular early during search.
Finally, we discuss computational results for different classes of primal heuristics that are implemented in SCIP.

 

 

Tuesday, 15:45 - 16:10 h, Room: H 2013, Talk 2

Manfred W. Padberg
The rank of (mixed-) integer polyhedra

 

Abstract:
We define a purely geometrical notion of
the rank of (mixed-) integer rational polyhedra
that differs substantially from the existing
notions found in the literature. This talk will
outline the notion and present some related results.

 

 

Tuesday, 16:15 - 16:40 h, Room: H 2013, Talk 3

Felipe Serrano
Some computational experiments with multi-row cuts.

Coauthor: Daniel Espinoza

 

Abstract:
We consider a general mixed integer problem (MIP). The topic we address is to derive cuts by combining two or more rows of the optimal simplex tableau of the linear relaxation of the MIP.
A framework will be presented that allows to generate multi-row cuts using different relaxations over the main set possibly including bounds on the variables.
Specifically, in this talk we present a numerical approach that allows to look into more complex relaxations than those previously considered in the literature. We propose an approximation scheme that may prove useful for practical implementations of multi-row cuts. Also, we incorporate a simple way to take advantage of the integrality of non basic variables.

 

  There are three major facts that should be watched out for in all payday loans in the United States. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cheap Cialis was obtained in Europe, Australia, New Zealand.