Abstract
In this paper, we propose a general extension of constraint propagation for constraint optimization based on cooperative computation. It is similar both in principle and operations to constraint propagation. In principle, it eliminates variable values by checking the feasibility that they can be in any global optimum. In operations, it is based on parallel, local iterative computations. The proposed algorithm returns both a solution and a global lower bound at each iteration. As an approximation algorithm for optimization, it significantly outperform classical optimization methods, such as simulated annealing and local search with multi-restarts in practice.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Freuder, E.C., Mackworth, A.K.: Constraint-based Reasoning. MIT/Elsevier (1994)
Schiex, T., Fargier, H., Verfaillie, G.: Valued constraint satisfaction problems: Hard and easy problems. In: Proc. of the 14th IJCAI, Montreal, Canada, pp. 631–637 (1995)
Modi, P.J.: Distributed Constraint Optimization for Multiagent Systems. PhD thesis, University of Southern California, Los Angles, U.S.A. (2003)
Rudová, H., Matyska, L.: Uniform framework for solving over-constrained and optimization problems. In: CP 1999 Post-Conference Workshop on Modelling and Solving Soft Constraints (1999)
Huang, X.: A general framework for constructing cooperative global optimization algorithms. In: 4th International Conference on Frontiers in Global Optimization (2003)
Schiex, T.: Arc consistency for soft constraints. In: Dechter, R. (ed.) CP 2000. LNCS, vol. 1894, p. 411. Springer, Heidelberg (2000)
Affane, M.S., Bennaceur, H.: Exploiting integer programming tools to solve maxcsp. In: Proc. of the Workshop on Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimisation Problem (1999)
Wallace, R.J.: Enhancements of branch and bound methods for the maximal constraint satisfaction problem. In: Proc. of AAAI, pp. 188–195 (1996)
Huang, X.: Cooperative optimization for solving large scale combinatorial problems. In: Grundel, D., Murphey, R., Pardalos, P. (eds.) 4th International Conference on Cooperative Control and Optimization, Destin, Florida, U.S.A. (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Huang, X. (2004). A General Extension of Constraint Propagation for Constraint Optimization. In: Wallace, M. (eds) Principles and Practice of Constraint Programming – CP 2004. CP 2004. Lecture Notes in Computer Science, vol 3258. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30201-8_57
Download citation
DOI: https://doi.org/10.1007/978-3-540-30201-8_57
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23241-4
Online ISBN: 978-3-540-30201-8
eBook Packages: Springer Book Archive