Soft arc consistency revisited

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F10%3A00170731" target="_blank" >RIV/68407700:21230/10:00170731 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Soft arc consistency revisited

Popis výsledku v původním jazyce

The Valued Constraint Satisfaction Problem (VCSP) is a generic optimization problem defined by a network of local cost functions defined over discrete variables. The incremental lower bounds produced by local consistency filtering are used for pruning inside Branch and Bound search. We extend the notion of arc consistency by allowing fractional weights and by allowing several arc consistency operations to be applied simultaneously. To reach a more practical algorithm, we show that the existence of a sequence of arc consistency operations which increases the lower bound can be detected by establishing arc consistency in a classical Constraint Satisfaction Problem (CSP) derived from the original cost function network. These algorithms have been implemented and evaluated on a variety of problems, including two difficult frequency assignment problems which are solved to optimality for the first time.

Název v anglickém jazyce

Soft arc consistency revisited

Popis výsledku anglicky

The Valued Constraint Satisfaction Problem (VCSP) is a generic optimization problem defined by a network of local cost functions defined over discrete variables. The incremental lower bounds produced by local consistency filtering are used for pruning inside Branch and Bound search. We extend the notion of arc consistency by allowing fractional weights and by allowing several arc consistency operations to be applied simultaneously. To reach a more practical algorithm, we show that the existence of a sequence of arc consistency operations which increases the lower bound can be detected by establishing arc consistency in a classical Constraint Satisfaction Problem (CSP) derived from the original cost function network. These algorithms have been implemented and evaluated on a variety of problems, including two difficult frequency assignment problems which are solved to optimality for the first time.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

JD - Využití počítačů, robotika a její aplikace

OECD FORD obor

—

Projekt

<a href="/cs/project/7E08031" target="_blank" >7E08031: Dynamic Interactive Perception-action Learning in Cognitive Systems</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>R - Projekt Ramcoveho programu EK

Rok uplatnění

2010

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Artificial Intelligence

ISSN

0004-3702

e-ISSN

—

Svazek periodika

174

Číslo periodika v rámci svazku

7-8

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

30

Strana od-do

—

Kód UT WoS článku

000277328200001

EID výsledku v databázi Scopus

—