Invited Session Thu.3.H 2033

Thursday, 15:15 - 16:45 h, Room: H 2033

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

Mixed-integer linear and semidefinite programs


Chair: Marc E. Pfetsch



Thursday, 15:15 - 15:40 h, Room: H 2033, Talk 1

Sonja Mars
Approaches to solve mixed integer semidefinite programs

Coauthors: Jakob Schelbert, Lars Schewe


We present a hybrid approach for solving mixed integer SDPs, which alternates between solving SDP- and LP-relaxations. We implemented this approach in SCIP and provide an interface to SDP-solvers. Therefore we added new features concerning presolving, heuristics and separation. Additionally to solving the SDPs directly, we approximate the SDP cone using linear inequalities and solve LP-relaxations.
Our framework can be used as a pure branch-and-cut-algorithm with solving SDP-relaxations. Furthermore it is possible to just use the linear approximations for solving. Our main focus lies on the comparison of the interaction of the two relaxations. For this we present numerical results.
Our studies are motivated by one main application. We consider problems from mechanical engineering in the context of truss topology design. The standard formulation of a truss problem is extended to discrete bar areas and actuators. These components are modeled via binary variables. Additionally we show results for other classes of MISDPs.



Thursday, 15:45 - 16:10 h, Room: H 2033, Talk 2

Nam Dung Hoang
Steiner tree packing revisited

Coauthor: Thorsten Koch


The Steiner tree packing problem (STPP) in graphs is a long
studied problem in combinatorial optimization. In contrast
to many other problems, where there have been tremendous
advances in practical problem solving, STPP remains very
difficult. Most heuristics schemes are ineffective and even
finding feasible solutions is already NP-hard. What makes this problem special is that in order to reach the overall optimal solution non-optimal solutions to the underlying NP-hard Steiner tree problems must be used. Any non-global approach to the STPP is likely to fail. Integer programming is currently the best approach for computing optimal solutions. In this talk we review some classical STPP instances which model the underlying real world application only in a reduced form. Through improved modelling, including some new cutting planes, and by emplyoing recent advances in solver technology we are for the first time able to solve those instances in the original 3D grid graphs to optimimality.



Thursday, 16:15 - 16:40 h, Room: H 2033, Talk 3

Matthias Miltenberger
Advances in linear programming


The efficient and reliable solution of today's optimization problems remains an interesting and challenging task, especially when dealing with large-scale instances. A lot of these are formulated as mixed integer programs that rely on branch-and-cut to compute an optimal solution. In this process usually many linear relaxations (LPs) have to be solved and the simplex method has proven successful in this task. We shed light on the impact of LP solving within the MIP context and present recent progress in the area, in particular with respect to the academic solvers SCIP and SoPlex.


  Florida Loans Online can help you in trying times, but be sure to know the laws necessary for your loan application. Thanks to that, they have a great variety of drugs that can help in these cases. Female Viagra is not an exception.