|
|
|
Séance TA3 - Programmation en nombres entiers / Integer Programming
Jour |
mardi, le 10 mai 2005 |
Salle |
Dutailier International |
Président |
Daniel T. Wojtaszek |
Présentations
10h30 |
Location Models: A Reformulation by Discretization |
|
Luis Gouveia, Universidade de Lisboa, DEIO-CIO Faculdade de Ciências, Cidade Universitaria Bloco C6 Piso 4, Campo Grande, Lisboa, Portugal, 1749-016
Francisco Saldanha da Gama, Universidade de Lisboa, DEIO-CIO Faculdade de Ciências, DEIO-FCUL, BLOCO C6, Piso 4, Lisbon, PORTUGAL, 1749-016
The usual location models contain a set of binary variables Yi indicating whether or not, a facility is built at location i. In this talk we discuss models using binary variables Ziq indicating whether a facility is built at location i AND is serving q clients. We relate formulations involving the new set of variables with previous known formulations. We also present and discuss a set of inequalities using the new set of variables and generated by the Chvatal-Gomory rounding method. We also discuss variations of the problem with nonlinear costs at the facilities (as these are easily modelled by the new variables). Computational results taken from instances with up to 100 client nodes and 20 facility nodes are presented for several variations of the location problem.
|
10h55 |
Faster MIP Solutions by Early Estimates of the Optimum Objective Function Value |
|
Daniel T. Wojtaszek, Carleton University, Systems and Computer Engineering, 1125 Colonel By Drive, Carleton University, Ottawa, Ontario, Canada, K1S 5B6
John W. Chinneck, Carleton University, Systems and Computer Engineering, 1125 Colonel By Drive, Carleton University, Ottawa, Ontario, Canada, K1S 5B6
The size of the branch and bound tree for a mixed-integer solution can be signficantly reduced if a reasonably accurate estimate of the optimum objective function value is available early in the search process. We develop algorithms for providing such early estimates and show preliminary empirical evidence in support of the effectiveness of the method.
|
11h20 |
Flow Formulations for Minimum-Energy Problems in Wireless Ad Hoc Networks |
|
Joanna Bauer, University of Bergen, Informatics, PB. 7800, Bergen, Norway, N-5020
Dag Haugland, University of Bergen, Informatics, PO Box 7800, 5020 Bergen, Norway
Di Yuan, Linkoping University, Science and Technology, Campus Norrkoping, Norrkoping, Sweden, SE-60174
We first give a flow formulation for the problem of minimizing energy in multicast sessions in wireless ad hoc networks. This formulation is strengthened, and some alternative flow formulations of equal strength are constructed. Finally, computational results comparing the performance of these are given.
|
11h45 |
Steiner Tree Formulations for Minimum-Energy Problems in Wireless Ad Hoc Networks |
|
Dag Haugland, University of Bergen, Informatics, PO Box 7800, 5020 Bergen, Norway
Joanna Bauer, University of Bergen, Informatics, PB. 7800, Bergen, Norway, N-5020
Di Yuan, Linkoping University, Science and Technology, Campus Norrkoping, Norrkoping, Sweden, SE-60174
By various network extensions, we demonstrate how the minimum-energy problem introduced in the previous talk (Bauer) can be formulated as a minimum Steiner tree problem. We analyze the strength of the formulations hence obtained, and we show that the Steiner and flow models are equally strong.
|
|