Estrategias de Enumeración para Resolver Problemas de Satisfacción de Restricciones: Evaluación de desempeño

Ricardo Soto; Broderick Crawford; Rodrigo Olivares; Rodrigo Herrera; Franklin Johnson; Fernando Paredes

doi:10.1109/CISTI.2015.7170511

Estrategias de Enumeración para Resolver Problemas de Satisfacción de Restricciones: Evaluación de desempeño

Translated title of the contribution: Enumeration strategies to solve constraint satisfaction problems: Performance evaluation

Ricardo Soto, Broderick Crawford, Rodrigo Olivares, Rodrigo Herrera, Franklin Johnson, Fernando Paredes

SCHOOL OF COMPUTER ENGINEERING

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

Abstract

In constraint programming, efficiency in the resolution process can be affected by the order in which the variables of the problem and the domain values are selected. This activity is known as enumeration. At the beginning, it is difficult to determine the best choice variable-value pair that can generate potential solutions for constraint satisfaction problems. In this paper, we present an evaluation of different enumeration strategies, based on performance exhibited in a set indicators. These strategies solve different instances of constraint problems satisfactions. The results show that it is feasible to solve constraint satisfaction with at least one strategy enumeration.

Translated title of the contribution	Enumeration strategies to solve constraint satisfaction problems: Performance evaluation
Original language	Spanish
Title of host publication	2015 10th Iberian Conference on Information Systems and Technologies, CISTI 2015
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)	9789899843455
DOIs	https://doi.org/10.1109/CISTI.2015.7170511
State	Published - 28 Jul 2015
Event	10th Iberian Conference on Information Systems and Technologies, CISTI 2015 - Aveiro, Portugal Duration: 17 Jun 2015 → 20 Jun 2015

Publication series

Name	2015 10th Iberian Conference on Information Systems and Technologies, CISTI 2015

Conference

Conference	10th Iberian Conference on Information Systems and Technologies, CISTI 2015
Country/Territory	Portugal
City	Aveiro
Period	17/06/15 → 20/06/15

Access to Document

10.1109/CISTI.2015.7170511

Cite this

Soto, R., Crawford, B., Olivares, R., Herrera, R., Johnson, F., & Paredes, F. (2015). Estrategias de Enumeración para Resolver Problemas de Satisfacción de Restricciones: Evaluación de desempeño. In 2015 10th Iberian Conference on Information Systems and Technologies, CISTI 2015 Article 7170511 (2015 10th Iberian Conference on Information Systems and Technologies, CISTI 2015). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CISTI.2015.7170511

Soto, Ricardo ; Crawford, Broderick ; Olivares, Rodrigo et al. / Estrategias de Enumeración para Resolver Problemas de Satisfacción de Restricciones : Evaluación de desempeño. 2015 10th Iberian Conference on Information Systems and Technologies, CISTI 2015. Institute of Electrical and Electronics Engineers Inc., 2015. (2015 10th Iberian Conference on Information Systems and Technologies, CISTI 2015).

@inproceedings{1e410fec614e46e5a70fdb342236dae6,

title = "Estrategias de Enumeraci{\'o}n para Resolver Problemas de Satisfacci{\'o}n de Restricciones: Evaluaci{\'o}n de desempe{\~n}o",

abstract = "In constraint programming, efficiency in the resolution process can be affected by the order in which the variables of the problem and the domain values are selected. This activity is known as enumeration. At the beginning, it is difficult to determine the best choice variable-value pair that can generate potential solutions for constraint satisfaction problems. In this paper, we present an evaluation of different enumeration strategies, based on performance exhibited in a set indicators. These strategies solve different instances of constraint problems satisfactions. The results show that it is feasible to solve constraint satisfaction with at least one strategy enumeration.",

keywords = "constraint programming, constraint satisfaction problems, enumeration strategies, heuristic",

author = "Ricardo Soto and Broderick Crawford and Rodrigo Olivares and Rodrigo Herrera and Franklin Johnson and Fernando Paredes",

note = "Publisher Copyright: {\textcopyright} 2015 AISTI.; 10th Iberian Conference on Information Systems and Technologies, CISTI 2015 ; Conference date: 17-06-2015 Through 20-06-2015",

year = "2015",

month = jul,

day = "28",

doi = "10.1109/CISTI.2015.7170511",

language = "Spanish",

series = "2015 10th Iberian Conference on Information Systems and Technologies, CISTI 2015",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

booktitle = "2015 10th Iberian Conference on Information Systems and Technologies, CISTI 2015",

}

Soto, R , Crawford, B, Olivares, R, Herrera, R, Johnson, F & Paredes, F 2015, Estrategias de Enumeración para Resolver Problemas de Satisfacción de Restricciones: Evaluación de desempeño. in 2015 10th Iberian Conference on Information Systems and Technologies, CISTI 2015., 7170511, 2015 10th Iberian Conference on Information Systems and Technologies, CISTI 2015, Institute of Electrical and Electronics Engineers Inc., 10th Iberian Conference on Information Systems and Technologies, CISTI 2015, Aveiro, Portugal, 17/06/15. https://doi.org/10.1109/CISTI.2015.7170511

Estrategias de Enumeración para Resolver Problemas de Satisfacción de Restricciones: Evaluación de desempeño. / Soto, Ricardo ; Crawford, Broderick; Olivares, Rodrigo et al.
2015 10th Iberian Conference on Information Systems and Technologies, CISTI 2015. Institute of Electrical and Electronics Engineers Inc., 2015. 7170511 (2015 10th Iberian Conference on Information Systems and Technologies, CISTI 2015).

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

TY - GEN

T1 - Estrategias de Enumeración para Resolver Problemas de Satisfacción de Restricciones

T2 - 10th Iberian Conference on Information Systems and Technologies, CISTI 2015

AU - Soto, Ricardo

AU - Crawford, Broderick

AU - Olivares, Rodrigo

AU - Herrera, Rodrigo

AU - Johnson, Franklin

AU - Paredes, Fernando

PY - 2015/7/28

Y1 - 2015/7/28

N2 - In constraint programming, efficiency in the resolution process can be affected by the order in which the variables of the problem and the domain values are selected. This activity is known as enumeration. At the beginning, it is difficult to determine the best choice variable-value pair that can generate potential solutions for constraint satisfaction problems. In this paper, we present an evaluation of different enumeration strategies, based on performance exhibited in a set indicators. These strategies solve different instances of constraint problems satisfactions. The results show that it is feasible to solve constraint satisfaction with at least one strategy enumeration.

AB - In constraint programming, efficiency in the resolution process can be affected by the order in which the variables of the problem and the domain values are selected. This activity is known as enumeration. At the beginning, it is difficult to determine the best choice variable-value pair that can generate potential solutions for constraint satisfaction problems. In this paper, we present an evaluation of different enumeration strategies, based on performance exhibited in a set indicators. These strategies solve different instances of constraint problems satisfactions. The results show that it is feasible to solve constraint satisfaction with at least one strategy enumeration.

KW - constraint programming

KW - constraint satisfaction problems

KW - enumeration strategies

KW - heuristic

UR - http://www.scopus.com/inward/record.url?scp=84943329002&partnerID=8YFLogxK

U2 - 10.1109/CISTI.2015.7170511

DO - 10.1109/CISTI.2015.7170511

M3 - Conference contribution

AN - SCOPUS:84943329002

T3 - 2015 10th Iberian Conference on Information Systems and Technologies, CISTI 2015

BT - 2015 10th Iberian Conference on Information Systems and Technologies, CISTI 2015

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 17 June 2015 through 20 June 2015

ER -

Soto R , Crawford B, Olivares R, Herrera R, Johnson F, Paredes F. Estrategias de Enumeración para Resolver Problemas de Satisfacción de Restricciones: Evaluación de desempeño. In 2015 10th Iberian Conference on Information Systems and Technologies, CISTI 2015. Institute of Electrical and Electronics Engineers Inc. 2015. 7170511. (2015 10th Iberian Conference on Information Systems and Technologies, CISTI 2015). doi: 10.1109/CISTI.2015.7170511

Estrategias de Enumeración para Resolver Problemas de Satisfacción de Restricciones: Evaluación de desempeño

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this