NDLI: Consistency techniques for polytime linear global cost functions in weighted constraint satisfaction

Please wait, while we are loading the content...

Consistency techniques for polytime linear global cost functions in weighted constraint satisfaction

Content Provider	Springer Nature Link
Author	Lee, J. H. M. Leung, K. L. Shum, Y. W.
Copyright Year	2014
Abstract	Lee and Leung make practical the consistency enforcement of global cost functions in Weighted Constraint Satisfaction Problems (WCSPs). The main idea of their approach lies in the derivation of polynomial time algorithms for the computation of the minimum cost of global cost functions. In this paper, we investigate how soft arc consistency can also be applied on global cost functions with no known efficient minimum cost computation algorithms. We propose polytime linear projection-safe (PLPS) cost functions, which have a polynomial size integer linear formulation and can maintain this good property across projection/extension operations. We observe that the minimum of the linear relaxation gives a good approximation to the minimum of the integer formulation. This is used as the basis for the enforcement of relaxed forms of existing soft arc consistencies. By using the linear formulations, we can easily enforce conjunctions of overlapping PLPS, which give stronger pruning power. We further propose polytime integral linear projection-safe (PILPS) cost functions, which are PLPS cost functions with guaranteed integral solutions to the linear relaxation. We prove theorems to compare the consistency strengths among PLPS, PILPS and their conjunctions. Extensive experimentations are conducted to compare our proposed algorithms against state of the art global cost functions consistency enforcement algorithms and integer programming. Empirical results agree with our theoretical predictions, and confirm orders of magnitude improvement in terms of pruning and runtime by our proposals.
Starting Page	270
Ending Page	308
Page Count	39
File Format	PDF
ISSN	13837133
Journal	Constraints
Volume Number	19
Issue Number	3
e-ISSN	15729354
Language	English
Publisher	Springer US
Publisher Date	2014-03-20
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Constraint optimization Global constraints Linear programming Artificial Intelligence (incl. Robotics) Optimization Computing Methodologies Operations Research/Decision Theory
Content Type	Text
Resource Type	Article
Subject	Discrete Mathematics and Combinatorics Artificial Intelligence Computational Theory and Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Minimization of Locally Defined Submodular Functions by Optimal Soft Arc Consistency

Models for Global Constraint Applications

High-Order Consistency in Valued Constraint Satisfaction

Ultra-weak solutions and consistency enforcement in minimax weighted constraint satisfaction

Improved filtering for weighted circuit constraints

Redundant modeling in permutation weighted constraint satisfaction problems

Grammar constraints

Multiconsistency and Robustness with Global Constraints

The Complexity of Reasoning with Global Constraints

Consistency techniques for polytime linear global cost functions in weighted constraint satisfaction

Similar Documents

Minimization of Locally Defined Submodular Functions by Optimal Soft Arc Consistency

Models for Global Constraint Applications

High-Order Consistency in Valued Constraint Satisfaction

Ultra-weak solutions and consistency enforcement in minimax weighted constraint satisfaction

Improved filtering for weighted circuit constraints

Redundant modeling in permutation weighted constraint satisfaction problems

Grammar constraints

Multiconsistency and Robustness with Global Constraints

The Complexity of Reasoning with Global Constraints

Consistency techniques for polytime linear global cost functions in weighted constraint satisfaction