## 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**

**Abstract:**

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

**Abstract:**

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**

**Abstract:**

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 *Σ*^{p}_{2} 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.