Retour

Séance TB2 - Métaheuristiques / Metaheuristics

Jour mardi, le 8 mai 2007
Salle Van Houtte
Président Philippe Galinier

Présentations

13h30-
13h55
Ant Colony Optimization: Do Ants Explore a Small World?
  Paola Pellegrini, Università Ca' Foscari di Venezia, Dipartimento di Matematica Applicata, Dorsoduro 3825/E, Venezia, Italy, 30123
Andrea Ellero, Università Ca' Foscari di Venezia, Dipartimento di Matematica Applicata, Dorsoduro 3825/E, Venezia, Italy, 30123

Good metaheuristics explore the search space as much as possible, saving resources for analyzing the most promising regions. Our experimental analysis supports this intuition for fine tuned ACO applied to traveling salesman problem, by observing the pheromone distribution on edges in terms of small world-like properties.


13h55-
14h20
Using Meta-heuristics to Find Minimal Unsatisfiable Subformulas in Satisfiability Problems
  Christian Desrosiers, École Polytechnique de Montréal, Génie informatique, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7
Philippe Galinier, École Polytechnique de Montréal, Génie informatique, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7
Alain Hertz, GERAD et École Polytechnique de Montréal, Mathématiques et génie industriel, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7
Sandrine Paroz, École Polytechnique de Montréal, GERAD et Mathématiques et génie industriel, Montréal, Canada

We propose efficient algorithms to extract minimal unsatisfiable subsets of clauses or variables in unsatisfiable propositional formulas. Such subsets yield unsatisfiable propositional subformulas that become satisfiable when any of their clauses or variables is removed. The algorithms we propose are based on meta-heuristics, and thus, can be applied to large instances. Furthermore, we show that, in some cases, the minimality of the subformulas can be proven with these algorithms. We also present an original algorithm to find minimum cardinality unsatisfiable subformulas in smaller instances. Finally, we report computational experiments on unsatisfiable instances from various sources, that demonstrate the effectiveness of our algorithms.


14h20-
14h45
A Patient Assignment Algorithm for Home Care Services
  Alain Hertz, GERAD et École Polytechnique de Montréal, Mathématiques et génie industriel, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7
Nadia Lahrichi, École Polytechnique de Montréal, Mathématiques et génie industriel, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7

We consider the problem of assigning patients to nurses for home care services. The aim is to balance the workload of the nurses while avoiding long travels to visit the patients. We analyze the case of the CSSS Côte-des-Neiges, Métro and Parc Extension for which a previous analysis has shown that demand fluctuations may create work overload for the nursing staff. We propose a mixed integer programming model with some non linear constraints and a non linear objective which we solve using a Tabu Search algorithm. A simplification of the workload measure leads to a linear mixed integer program which we optimize using CPLEX.


14h45-
15h10
High Level Hybrid Method for the Wood Scheduling Problem
  José Eduardo Pecora Jr., Université Laval, Opérations et systèmes de décision & CENTOR, Pavillon Palasis-Prince, Bureau 2666, Québec, QC, Canada, G1K 7P4
Angel Ruiz, Université Laval, Opérations et systèmes de décision et CRT, Québec, Québec, Canada, G1K 7P4
Patrick Soriano, HEC Montréal, CRT, GERAD et Méthodes quantitatives de gestion, 3000, ch. de la Côte Ste-Catherine, Montréal, Québec, Canada, H3T 2A7

We propose an approach based on the synergy, complementarity and multi-directional exchange of information through the several solution methods in order to tackle a real world problem. The hybrid method has two distinct phases: in the first one two heuristic methods will interact in order to find good search to be explored by an exact method explore in the next phase. There are some characteristics which are highly desired in this final search space, like it should be small enough to the exact method perform a complete search and it must have a high probability of contain the optimal solution. The preliminary computational tests show the robustness and the efficiency of the method, providing very good solutions mostly for the greater test instances in very competitive computational time.


Retour