2016 Optimization Days
HEC Montréal, Québec, Canada, 2 — 4 May 2016
TA3 Méthodes de décomposition en programmation en nombre entiers / Decomposition Methods for Integer Programming
May 3, 2016 10:30 AM – 12:10 PM
Location: EY
Chaired by Frédéric Quesnel
4 Presentations

10:30 AM  10:55 AM
Selective pricing in branchandprice algorithms for vehicle routing problems
When solving VRPs by column generation, usually the set of feasible routes is enlarged with infeasible cyclic routes. Nevertheless, a lower bound is reached when no feasible route has negative reduced cost regardless of the cyclic route reduced costs. We explore this knowledge to improve the labeling algorithm used for pricing.

10:55 AM  11:20 AM
I2SUD: An improved integral simplex using decomposition algorithm
We propose I2SUD, an improved version of the Integral Simplex Using Decomposition algorithm (ISUD). We develop dynamic selfadjusted decompositions to find likely orthogonal descent directions at each iteration. We solve related subproblems in parallel to get an improved integer solution until optimality. We also present some strategies to speedup I2SUD. Keywords: Integral Simplex Using Decomposition algorithm, dynamic selfadjusted decomposition, parallel computing, orthogonal descent directions.

11:20 AM  11:45 AM
An improved model for the integral simplex using decomposition algorithm
We introduce a new model that improves both quality and performance of the ISUD algorithm. The new model presents higher chances of finding the targeted integer solutions without branching. In our experimentation, optimal solutions are encountered, in less than a minute, for large instances with up to 570000 columns.

11:45 AM  12:10 PM
A general uncapacitated multiple allocation phub median problem
The uncapacitated multiple allocation phub median problem assumes that the triangle inequality applies on the edges of a complete graph. Hence the flow between any pair of nodes requires at most two hubs for the transfer process. Here we relax the triangle inequality restriction and present two new formulations that allow transfer through up to q hubs where q ≤ p is a given parameter. Some heuristic solution approaches are proposed and preliminary computational results given.