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


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


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 dkl, between facilities k and l, and flows.
The Minimum Linear Arrangement (MinLA) is a special case of (QAP) where dkl = |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,%.

  1. Liu, W., A. Vannelli. 1995. Generating lower bounds for the linear arrangement problem. Discrete Applied Mathematics 59, p. 137-151.
  2. 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.



  Payday Loans In Texas. If you have already decided to take Generic Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.