Invited Session Fri.3.H 3005

Friday, 15:15 - 16:45 h, Room: H 3005

Cluster 2: Combinatorial optimization [...]

Nonlinear combinatorial optimization problems II


Chair: Christoph Buchheim



Friday, 15:15 - 15:40 h, Room: H 3005, Talk 1

Franklin Djeumou Fomeni
A dynamic programming heuristic for the quadratic knapsack problem

Coauthor: Adam N. Letchford


It is well known that the standard (linear) knapsack problem can be solved exactly by dynamic programming in pseudo-polynomial time. The quadratic knapsack problem, by contrast, is NP-hard in the strong sense, which makes it unlikely that it can be solved in pseudo-polynomial time. It is possible, however, to convert the dynamic programming approach to the linear knapsack problem into a heuristic for the quadratic version. We explain how this can be done, and present some extremely promising computational results.



Friday, 15:45 - 16:10 h, Room: H 3005, Talk 2

Ruth Hübner
Ellipsoid bounds for convex quadratic integer programming

Coauthors: Christoph Buchheim, Anita Schöbel


Solving unrestricted convex quadratic integer programs by a branch&bound approach requires lower bounds on the objective value. We are going to follow the approach by Buchheim, Caprara and Lodi (2011) and approximate the quadratic function by an "easier'' quadratic function which underestimates the original one. Geometrically, we approximate the level set of the objective by an auxiliary ellipsoid for which we require that the corresponding quadratic integer problem can be solved by rounding its continuous optimal solution. In a first approach we are going to restrict the choice of the auxiliary ellipsoid to axis-parallel ellipsoids (corresponding to the level sets of separable convex quadratic functions). Which one is the "best'' auxiliary axis-parallel ellipsoid depends not only on the given objective function but also on the respective continuous optimal solution which changes in every node of the branching tree. As it is expensive to find a good auxiliary ellipsoid we want to decide on a single ellipsoid and use it for the whole algorithm. This raises the question on how to compare different ellipsoids. To this end, worst-case and average-case arguments are discussed.



Friday, 16:15 - 16:40 h, Room: H 3005, Talk 3

Sourour Elloumi
A unified view of linear and quadratic convex reformulation for binary quadratic programming


We consider binary quadratic programs (QP) having a quadratic objective
function, linear constraints, and binary variables. Many classical solution methods of
these problems are based on exact reformulation of QP into an
equivalent mixed integer linear program. Several linearization methods were
studied in the literature. More recent solution methods also
build an exact reformulation but into a problem which objective function is
quadratic and convex. A common point of the two approaches is that the
continuous relaxation of the reformulated problem is a convex optimization
problem that can be solved in polynomial time. This makes it possible to use a general branch-and-bound framework to solve the reformulated problem and even to rely on the strongness of standard solvers.
In this paper, we show that several quadratic convex reformulation methods, as well as classical linearization, can be viewed within a unified framework. This shows the non-surprising result that linearization is a particular quadratic convex reformulation on the one hand. On the other hand, it allows to compare these methods from a theoretical point of view.


  There are three major facts that should be watched out for in all payday loans in the United States. If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.