Invited Session Mon.2.MA 042

Monday, 13:15 - 14:45 h, Room: MA 042

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

Computational integer programming

 

Chair: Ricardo Fukasawa

 

 

Monday, 13:15 - 13:40 h, Room: MA 042, Talk 1

Daniel Steffy
Improving the accuracy of linear programming solvers with iterative refinement

Coauthors: Ambros M. Gleixner, Kati Wolter

 

Abstract:
We describe an iterative refinement procedure for computing extended precision or exact solutions to linear programming problems (LPs). Arbitrarily precise solutions can be computed by solving a sequence of closely related LPs with limited precision arithmetic. The LPs solved at iterations of this algorithm share the same constraint matrix as the original problem instance and are transformed only by modification of the objective function, right-hand side, and variable bounds. Exact computation is used to compute and store the exact representation of the transformed problems, while numeric computation is used for computing approximate LP solutions and applying iterations of the simplex algorithm. We demonstrate that this algorithm is effective in practice for computing extended precision solutions and directly benefits methods for solving LPs exactly over the rational numbers. A proof-of-concept implementation is done within the SoPlex LP solver.

 

 

Monday, 13:45 - 14:10 h, Room: MA 042, Talk 2

Franz Wesselmann
Computational experiments with general-purpose cutting planes

Coauthor: Uwe H. Suhl

 

Abstract:
General-purpose cutting planes are known to play a crucial role in solving mixed-integer linear programs. We report on computational experiments with families of split cuts which can be generated efficiently such as Gomory mixed-integer cuts, reduce-and-split cuts, lift-and-project cuts and pivot-and-reduce cuts. We also consider several variants of these basic algorithms, e.g., lift-and-project cuts generated from split disjunctions obtained with the reduce-and-split algorithms or reduce-and-split cuts generated using tableau rows produced by the lift-and-project method. Moreover, we present computational results obtained with different variants of multi-row cut separators.

 

 

Monday, 14:15 - 14:40 h, Room: MA 042, Talk 3

Daniel G. Espinoza
Cutting and separation for semi-continuous variables

Coauthor: Angulo A. Alejandro

 

Abstract:
Semi-continuous variables appear naturally when modeling general functions with mixed integer linear programs (MILP), and are widely used in many applications.
In this talk we present several classes of inequalities for semi-continuous variables linked together by a knapsack inequality.
We present necessary and sufficient conditions for these classes of inequalities to be facet-defining; and also, we describe an approximate lifting scheme, and conditions under which the approximated lifting is exact.
Although the separation problem is NP-complete, we present some separation heuristics, as well as extensive testing on instances coming from unit commitment problems.
Our results show that, in our test instances, we close in average between 50 and 90 percent of the root LP gap.

 

  Payday Loans California. In this section we give only a brief summary recommendation for admission of Levitra Sale. Full information can be found in the instructions for receiving medications with vardenafil.