Record number :
1314101
Title of article :
Combining VNS with constraint programming for solving anytime optimization problems
Author/Authors :
Samir Loudni، نويسنده , , Patrice Boizumault، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2008
Pages :
31
From page :
705
To page :
735
Abstract :
This paper presents an hybrid search method for solving on-line optimization problems that are modelled using the vcspValued Constraint Satisfaction Problems framework. To each constraint is associated a valuation representing the “cost to pay” when this constraint will be violated by a solution. Our method (VNS/LDS+CP) uses principles of VNS (Variable Neighborhood Search) and combines a partial tree search (Limited Discrepancy Search) with Constraint Propagation in order to compute local optima. Experiments on the CELAR benchmarks demonstrate significant improvements on other competing methods: LNS/CP/GR [Lobjois, L., Lemaitre, M., Verfaillie, G., 2000. Large neighbourhood search using constraint propagation and greedy reconstruction for valued csp resolution. In: Proceedings of the ECAI2000 Workshop on Modelling and Solving Problems with Constraints], another hybrid method using vcsps, and two standard versions of Simulated-Annealing [Li, Y.H., 1997. Directed annealing search in constraint satisfaction and optimization. Ph.D. thesis, Imperial College of Science, Department of Computing]: Quick and Medium. Moreover, VNS/LDS+CP clearly satisfies the key properties of anytime algorithms. Finally, VNS/LDS+CP has been successfully applied to a real-life on-line resource allocation problem in computer networks.
Keywords :
On-line optimization , Valued CSP , Anytime algorithms , VNDS , LDS , Constraint propagation , VNS
Journal title :
European Journal of Operational Research
Link To Document :