HEURÍSTICAS DE SELECCIÓN DE VARIABLE PARA ALGORITMOS BASADOS EN INTERVALOS USANDO EL PRINCIPIO FAIL-FIRST

Abstract

Los algoritmos Branch&Bound basados en intervalos son utilizados para resolver problemas de satisfacción de restricciones con dominios continuos (NCSP) de una manera confiable, es decir, estos algoritmos encuentran todas las soluciones asociadas a una instancia con un error acotado. Una de las principales problemáticas que surgen en este tipo de algoritmos es determinar la siguiente variable a instanciar (o bisectar). En este trabajo son propuestas heurísticas de selección de variable para NCSP. Para esto, es utilizado el famoso principio fail-first. Desde su publicación, el principio ha tenido un impacto significativo en el diseo de heurísticas de selección de variable para problemas de satisfacción de restricciones con dominios discretos. Los resultados obtenidos muestran que es posible obtener información relevante a través de algoritmos basados en el principio fail-first, aumentando la eficiencia de búsqueda. Estas propuestas representan una mejora significativa a las heurísticas clásicas.