logo
CanyamAI summaries for academic research
language
MobileMobile
  • Phone FeatureWeChat Mini Program
EnglishEnglish
noticeNotice
BlogBlog
delete
arrow
Return

A polynomial algorithm for continuous non-binary disjunctive CSPs: extended DLRs

delete2003-07-01
delete5
PRE
AI
M
Miguel Á. Salido *
F
Federico Barber
DOI：10.1016/S0950-7051(03)00029-7delete
deleteOriginal
deleteOriginal request for help
deleteShare
deleteSave
Abstract

Abstract

En 中文
Nowadays, many real problems can be modelled as Constraint Satisfaction Problems (CSPs). Some CSPs are considered non-binary disjunctive CSPs. Many researchers study the problems of deciding consistency for Disjunctive Linear Relations (DLRs). In this paper, we propose a new class of constraints called Extended DLRs consisting of disjunctions of linear inequalities, linear disequations and non-linear disequations. This new class of constraints extends the class of DLRs. We propose a heuristic algorithm called DPOLYSA that solves Extended DLRs. as a non-binary disjunctive CSP solver. This proposal works on a polyhedron whose vertices are also polyhedra that represent the nondisjunctive problems. We also present a statistical preprocessing step which translates the disjunctive problem into a nondisjunctive and ordered one in each step. (C) 2003 Elsevier Science B.V. All rights reserved.
Keywords:
disjunctive linear relations
constraint satisfaction problems
disjunctive polyhedron search algorithm
non-binary CSP
AI Summary

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.

Journal

K
Knowledge-Based Systems
IF:
7.6
Papers:
1.2W
Citations:
4.5W

Organization

No organization information available