- -

Robustness and stability in dynamic constraint satisfaction problems

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

Robustness and stability in dynamic constraint satisfaction problems

Show simple item record

Files in this item

dc.contributor.advisor Barber Sanchís, Federico es_ES
dc.contributor.advisor Salido Gregorio, Miguel Angel es_ES
dc.contributor.author Climent Aunés, Laura Isabel es_ES
dc.date.accessioned 2014-01-07T07:47:22Z
dc.date.available 2014-01-07T07:47:22Z
dc.date.created 2013-12-17T11:00:54Z es_ES
dc.date.issued 2014-01-07T07:47:19Z es_ES
dc.identifier.uri http://hdl.handle.net/10251/34785
dc.description.abstract Constraint programming is a paradigm wherein relations between variables are stated in the form of constraints. It is well-known that many real life problems can be modeled as Constraint Satisfaction Problems (CSPs). Much effort has been spent to increase the efficiency of algorithms for solving CSPs. However, many of these techniques assume that the set of variables, domains and constraints involved in the CSP are known and fixed when the problem is modeled. This is a strong limitation because many problems come from uncertain and dynamic environments, where both the original problem may evolve because of the environment, the user or other agents. In such situations, a solution that holds for the original problem can become invalid after changes. There are two main approaches for dealing with these situations: reactive and proactive approaches. Using reactive approaches entails re-solving the CSP after each solution loss, which is a time consuming. That is a clear disadvantage, especially when we deal with short-term changes, where solution loss is frequent. In addition, in many applications, such as on-line planning and scheduling, the delivery time of a new solution may be too long for actions to be taken on time, so a solution loss can produce several negative effects in the modeled problem. For a task assignment production system with several machines, it could cause the shutdown of the production system, the breakage of machines, the loss of the material/object in production, etc. In a transport timetabling problem, the solution loss, due to some disruption at a point, may produce a delay that propagates through the entire schedule. In addition, all the negative effects stated above will probably entail an economic loss. In this thesis we develop several proactive approaches. Proactive approaches use knowledge about possible future changes in order to avoid or minimize their effects. These approaches are applied before the changes occur. Thus, our approaches search for robust solutions, which have a high probability to remain valid after changes. Furthermore, some of our approaches also consider that the solutions can be easily adapted when they did not resist the changes in the original problem. Thus, these approaches search for stable solutions, which have an alternative solution that is similar to the previous one and therefore can be used in case of a value breakage. In this context, sometimes there exists knowledge about the uncertain and dynamic environment. However in many cases, this information is unknown or hard to obtain. For this reason, for the majority of our approaches (specifically 3 of the 4 developed approaches), the only assumptions made about changes are those inherent in the structure of problems with ordered domains. Given this framework and therefore the existence of a significant order over domain values, it is reasonable to assume that the original bounds of the solution space may undergo restrictive or relaxed modifications. Note that the possibility of solution loss only exists when changes over the original bounds of the solution space are restrictive. Therefore, the main objective for searching robust solutions in this framework is to find solutions located as far away as possible from the bounds of the solution space. In order to meet this criterion, we propose several approaches that can be divided in enumeration-based techniques and a search algorithm. es_ES
dc.language Inglés es_ES
dc.rights Reserva de todos los derechos es_ES
dc.source Riunet es_ES
dc.subject Robustness es_ES
dc.subject Stability es_ES
dc.subject Uncertainty es_ES
dc.subject Dynamism es_ES
dc.subject Constraint Satisfaction Problems es_ES
dc.subject CSPs es_ES
dc.subject Dynamic Constraint Satisfaction Problems es_ES
dc.subject DynCSP es_ES
dc.subject.classification LENGUAJES Y SISTEMAS INFORMATICOS es_ES
dc.title Robustness and stability in dynamic constraint satisfaction problems
dc.type Tesis doctoral es_ES
dc.identifier.doi 10.4995/Thesis/10251/34785 es_ES
dc.rights.accessRights Abierto es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació es_ES
dc.description.bibliographicCitation Climent Aunés, LI. (2013). Robustness and stability in dynamic constraint satisfaction problems [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/34785 es_ES
dc.description.accrualMethod Alfresco es_ES
dc.type.version info:eu-repo/semantics/acceptedVersion es_ES
dc.relation.tesis 4289 es_ES


This item appears in the following Collection(s)

Show simple item record