Journées de l'optimisation 2007 Optimizations days

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.

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.

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.

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.