English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Many combinatorial problems deal with preferences and violations, the goal ofwhich is to find solutions with the minimum cost. Weighted constraintsatisfaction is a framework for modeling such problems, which consists of a setof cost functions to measure the degree of violation or preferences ofdifferent combinations of variable assignments. Typical solution methods forweighted constraint satisfaction problems (WCSPs) are based on branch-and-boundsearch, which are made practical through the use of powerful consistencytechniques such as AC*, FDAC*, EDAC* to deduce hidden cost information andvalue pruning during search. These techniques, however, are designed to beefficient only on binary and ternary cost functions which are represented intable form. In tackling many real-life problems, high arity (or global) costfunctions are required. We investigate efficient representation scheme andalgorithms to bring the benefits of the consistency techniques to also higharity cost functions, which are often derived from hard global constraints fromclassical constraint satisfaction. The literature suggests some global costfunctions can be represented as flow networks, and the minimum cost flowalgorithm can be used to compute the minimum costs of such networks inpolynomial time. We show that naive adoption of this flow-based algorithmicmethod for global cost functions can result in a stronger form of null-inverseconsistency. We further show how the method can be modified to handle costprojections and extensions to maintain generalized versions of AC* and FDAC*for cost functions with more than two variables. Similar generalization for thestronger EDAC* is less straightforward. We reveal the oscillation problem whenenforcing EDAC* on cost functions sharing more than one variable. To avoidoscillation, we propose a weak version of EDAC* and generalize it to weakEDGAC* for non-binary cost functions. Using various benchmarks involving thesoft variants of hard global constraints ALLDIFFERENT, GCC, SAME, and REGULAR,empirical results demonstrate that our proposal gives improvements of up to anorder of magnitude when compared with the traditional constraint optimizationapproach, both in terms of time and pruning.

Consistency Techniques for Flow-Based Projection-Safe Global Cost Functions in Weighted Constraint Satisfaction