Invited Session Tue.2.H 2032

Tuesday, 13:15 - 14:45 h, Room: H 2032

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

Trends in mixed integer programming III


Chair: Robert Weismantel and Andrea Lodi



Tuesday, 13:15 - 13:40 h, Room: H 2032, Talk 1

Qie He
Minimum concave cost network flow over a grid network

Coauthors: Shabbir Ahmed, George L. Nemhauser


The minimum concave cost network flow problem (MCCNFP) is NP-hard, but efficient polynomial-time algorithms exist for some special cases, such as the uncapacitated multi-echelon lot-sizing problem. We consider the computational complexity of MCCNFP as a function of the underlying network topology and the representation of the concave function by studying MCCNFP over a grid network with a general nonnegative separable concave function. We show that this problem is polynomial solvable when all source nodes are at the first echelon and all sink nodes are at the last echelon. The polynomiality argument relies on a combination of a particular dynamic programming formulation and a careful investigation of the extreme points of the underlying flow polyhedron. We derive an analytical formula for the inflow of any node under all extreme points, which generalizes Zangwill's result for the
multi-echelon lot-sizing problem.



Tuesday, 13:45 - 14:10 h, Room: H 2032, Talk 2

Tamás Kis
Strengthening the MIP formulation of a bilevel lot-sizing problem


In the talk, I will introduce the bilevel lot-sizing problem,
and show how to formulate it as a MIP. In addition, I will present problem specific bounds and cuts, as well as mixed integer disjunctive cuts derived from two rows of the simplex tableau,
one corresponding to an integer variable, the other to a continuous variable.
I will also discuss the computational merits of the various strengthening methods.



Tuesday, 14:15 - 14:40 h, Room: H 2032, Talk 3

Fabio Furini
Heuristic and exact algorithms for the interval min-max regret knapsack problem

Coauthors: Manuel Iori, Silvano Martello, Mutsunori Yagiura


We consider a generalization of the 0-1 knapsack problem in which the profit of each item can take any value in a
range characterized by a minimum and a maximum possible profit. A set of specific profits is called a scenario.
The interval min-max regret knapsack problem (MRKP) is then to find a
feasible solution such that the maximum regret over all scenarios is minimized. The problem is extremely challenging both from a theoretical and a
practical point of view. Its recognition version is complete for the complexity class Σp2 hence it is most probably not in NP.
In addition, even computing the regret of a solution with respect to a scenario requires the solution of an NP-hard problem.
We examine the behavior of classical combinatorial optimization approaches when adapted to the solution of the MRKP.
We introduce an iterated local search approach and a Lagrangian-based branch-and-cut algorithm, and evaluate their performance
through extensive computational experiments.


  personal loans. What can cause long-term use of Canadian Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.