Conflict resolution

Konstantin Korovin; Nestan Tsiskaridze; Andrei Voronkov

doi:10.1007/978-3-642-04244-7_41

Conflict resolution

Konstantin Korovin, Nestan Tsiskaridze, Andrei Voronkov

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

Abstract

We introduce a new method for solving systems of linear inequalities over the rationals-the conflict resolution method. The method successively refines an initial assignment with the help of newly derived constraints until either the assignment becomes a solution of the system or a trivially unsatisfiable constraint is derived. We show that this method is correct and terminating. Our experimental results show that conflict resolution outperforms the Fourier-Motzkin method and the Chernikov algorithm, in some cases by orders of magnitude. © 2009 Springer Berlin Heidelberg.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)\|Lect. Notes Comput. Sci.
Publisher	Springer Nature
Pages	509-523
Number of pages	14
Volume	5732
ISBN (Print)	3642042430, 9783642042430
DOIs	https://doi.org/10.1007/978-3-642-04244-7_41
Publication status	Published - 2009
Event	15th International Conference on Principles and Practice of Constraint Programming, CP 2009 - Lisbon Duration: 1 Jul 2009 → … http://dblp.uni-trier.de/db/conf/cp/cp2009.html#KorovinTV09http://dblp.uni-trier.de/rec/bibtex/conf/cp/KorovinTV09.xmlhttp://dblp.uni-trier.de/rec/bibtex/conf/cp/KorovinTV09

Conference

Conference	15th International Conference on Principles and Practice of Constraint Programming, CP 2009
City	Lisbon
Period	1/07/09 → …
Internet address	http://dblp.uni-trier.de/db/conf/cp/cp2009.html#KorovinTV09http://dblp.uni-trier.de/rec/bibtex/conf/cp/KorovinTV09.xmlhttp://dblp.uni-trier.de/rec/bibtex/conf/cp/KorovinTV09

Access to Document

10.1007/978-3-642-04244-7_41

Cite this

@inproceedings{6d934f02ddf947c980e4f78ab514dfa8,

title = "Conflict resolution",

abstract = "We introduce a new method for solving systems of linear inequalities over the rationals-the conflict resolution method. The method successively refines an initial assignment with the help of newly derived constraints until either the assignment becomes a solution of the system or a trivially unsatisfiable constraint is derived. We show that this method is correct and terminating. Our experimental results show that conflict resolution outperforms the Fourier-Motzkin method and the Chernikov algorithm, in some cases by orders of magnitude. {\textcopyright} 2009 Springer Berlin Heidelberg.",

author = "Konstantin Korovin and Nestan Tsiskaridze and Andrei Voronkov",

year = "2009",

doi = "10.1007/978-3-642-04244-7\_41",

language = "English",

isbn = "3642042430",

volume = "5732",

pages = "509--523",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci.",

publisher = "Springer Nature",

address = "United States",

note = "15th International Conference on Principles and Practice of Constraint Programming, CP 2009 ; Conference date: 01-07-2009",

url = "http://dblp.uni-trier.de/db/conf/cp/cp2009.html\#KorovinTV09http://dblp.uni-trier.de/rec/bibtex/conf/cp/KorovinTV09.xmlhttp://dblp.uni-trier.de/rec/bibtex/conf/cp/KorovinTV09",

}

Korovin, K, Tsiskaridze, N & Voronkov, A 2009, Conflict resolution. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci.. vol. 5732, Springer Nature, pp. 509-523, 15th International Conference on Principles and Practice of Constraint Programming, CP 2009, Lisbon, 1/07/09. https://doi.org/10.1007/978-3-642-04244-7_41

Conflict resolution. / Korovin, Konstantin; Tsiskaridze, Nestan; Voronkov, Andrei.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci.. Vol. 5732 Springer Nature, 2009. p. 509-523.

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Conflict resolution

AU - Korovin, Konstantin

AU - Tsiskaridze, Nestan

AU - Voronkov, Andrei

PY - 2009

Y1 - 2009

N2 - We introduce a new method for solving systems of linear inequalities over the rationals-the conflict resolution method. The method successively refines an initial assignment with the help of newly derived constraints until either the assignment becomes a solution of the system or a trivially unsatisfiable constraint is derived. We show that this method is correct and terminating. Our experimental results show that conflict resolution outperforms the Fourier-Motzkin method and the Chernikov algorithm, in some cases by orders of magnitude. © 2009 Springer Berlin Heidelberg.

AB - We introduce a new method for solving systems of linear inequalities over the rationals-the conflict resolution method. The method successively refines an initial assignment with the help of newly derived constraints until either the assignment becomes a solution of the system or a trivially unsatisfiable constraint is derived. We show that this method is correct and terminating. Our experimental results show that conflict resolution outperforms the Fourier-Motzkin method and the Chernikov algorithm, in some cases by orders of magnitude. © 2009 Springer Berlin Heidelberg.

UR - https://www.scopus.com/pages/publications/70350406488

U2 - 10.1007/978-3-642-04244-7_41

DO - 10.1007/978-3-642-04244-7_41

M3 - Conference contribution

SN - 3642042430

SN - 9783642042430

VL - 5732

SP - 509

EP - 523

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci.

PB - Springer Nature

T2 - 15th International Conference on Principles and Practice of Constraint Programming, CP 2009

Y2 - 1 July 2009

ER -

Conflict resolution

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this