Combining VNS with constraint programming for solving anytime optimization problemsSamir Loudni and Patrice Boizumault European Journal of Operational Research, 2008, vol. 191, issue 3, pages 705-735 Abstract: This paper presents an hybrid search method for solving on-line optimization problems that are modelled using the vcsp Valued 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. Downloads: (external link) Related works: Access Statistics for this article European Journal of Operational Research is edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
Econpapers is hosted by the
Swedish Business School at Örebro University.