15h30 - 15h55
Modeling a Scenario-Based Network Design Problem in an Open Distribution Web Context
This research studies network deployment strategies in a Physical Internet enabled open distribution web where companies can exploit a widely dispersed set of open storage facilities. Under uncertainty, a scenario-based approach is proposed to model this strategic design problem and an approximate solution approach is under development to solve it.
15h55 - 16h20
Slope-Scaling Heuristic for a Service Network Design with Resource Constraints
In this paper, we present the first slope-scaling algorithm heuristic column generation approach with cycle-based formulation for a service network design with resource constraints. The heuristic includes column generation idea plus a fast heuristic as its core components. The experiment shows that the result is able to identify feasible and high quality solutions for the studied hard problem.
16h20 - 16h45
Capacitated Network Design with Facility Location
We consider the Capacitated Connected Facility Location Problem which arises in the design of last mile telecommunication networks. It combines the capacitated network design problem (CNDP) with the single-source capacitated facility location problem (SSCFLP). We develop a basic integer
programming model based on multi-commodity flows. Based on valid inequalities for the subproblems, CNDP and SSCFLP, we derive several (new) classes of valid inequalities for the CapConFL. We use them in a branch-and-cut framework and show the efficiency of our approach on a set of benchmark instances.
16h45 - 17h10
Relaxations for the RWA Problem
This work deals with solving the Routing and Wavelength Assignment problem where the number
of accepted connections is to be maximized. Lagrangean decomposition as well as Lagrangean
relaxation are studied for both node-arc formulations and arc-path formulation. It is shown that
relaxing the demand constraints yields an edge-disjoint path problem with profits that is NP-hard,
while the Lagrangean problem obtained when the clash constraints are relaxed becomes a shortest
path problem or a 0-1 linear knapsack problem, depending on the formulation used. Moreover, it
is shown that the Lagrangean decomposition is not stronger than the Lagrangean relaxation of the
demand constraints. We also propose a subgradient algorithm to solve the Lagrangean dual obtained
by relaxing the clash constraints. Numerical results demonstrate a high quality of Lagrangean dual
bounds with fast computation time.