## Contributed Session Mon.2.H 2032

#### Monday, 13:15 - 14:45 h, Room: H 2032

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

### Integer programming algorithms II

**Chair: Serigne Gueye**

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

**Hilary Paul Williams**

The general solution of a mixed integer programme

**Coauthor: John N. Hooker**

**Abstract:**

We give general formulae for the optimal objective value and solution values of a Mixed Integer Programme (MIP) as a function of the coefficients (objective, matrix and RHS). In order to do this we project out all the variables giving an (attainable) bound on the optimal objective value. This results in the optimal objective value expressed as a finite disjunction of inequalities and linear congruences. While the method is not computationally viable for practical sized MIPs it reveals a lot about their mathematical structure. It also provides a finite method of proving optimality. Hopefully the resultant `dual' solution also provides useful economic interpretations.

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

**Serigne Gueye**

Using distance variables for the quadratic assignment problem

**Coauthor: Philippe Michelon**

**Abstract:**

The Quadratic Assignment Problem (QAP) is the problem of allocating facilities to locations such as to minimize the sum of a linear and quadratic cost depending on the distances *d*_{kl}, between facilities *k* and *l*, and flows.

The Minimum Linear Arrangement (MinLA) is a special case of (QAP) where *d*_{kl} = |k-l|. It has been proposed for MinLA a linear model using distance variables. The lower bound is poor, equal to 0, but can be improved with facets (see [1, 2]). We have independently observed that the distance variables can be used for (QAP), and that some facets are also applicable each time *d* defines a metric, as the grid graphs in QAPLIB instances. Adding valid inequalities linking *D* and *x*, we have tested this model. The result shows a competitive average relative gap of 10.7,% with a minimum of 3.4,%.

{\footnotesize

- Liu, W., A. Vannelli. 1995. Generating lower bounds for the linear arrangement problem. Discrete Applied Mathematics 59, p. 137-151.

- A. Caprara, A.N. Letchford, and J.J. Salazar-Gonzalez. 2011. Decorous lower

bounds for minimum linear arrangement. INFORM Journal of Computing, 23(1), p. 26-40.

}