It involves finding values to variables satisfying some constraints. If all constraints cannot be satisfied simultaneously, a solution is the assignment that best respects the constraints. While this problem is computationally intractable, many real problems can be modelled as constraint satisfaction.

  • Algorithms for Max-CSP and non-binary constraints.
  • Generic and symmetry-based heuristics.
  • Interleaved depth-first search.
  • Distributed constraint satisfaction.

Enhanced data management techniques for real time logistics planning and scheduling

Initial/final date: 
01 June 2018 to 31 May 2021
Main researcher: 
Project type: 
International
Funding Entity: 
European Commission
Description: 

The main objective of the project is to allow effective planning and optimizing of transport operations in the supply chain by taking advantage of horizontal and vertical collaboration, relaying on the increasingly real time available data gathered from the interconnected environment. For this, a real-time decision making tool and a real-time
visualization tool of freight transport will be developed, with the purpose of delivering information and services to the various agents involved in the supply chain, i.e. freight transport operators, their clients, industries and other stakeholders such as warehouse or infrastructure managers.

The operative objectives will be:

  • To analyse stakeholders’ needs incorporating them in the specification of the logistic services delivered.
  • To identify logistic open data sources and harmonizing this data together with the other closed sources (i.e. data retrieved from IoT devices) to be used as real-time information
  • To deploy and enhance artificial intelligence techniques to deliver prediction services and to learn the preferences of logistic chain participants, which will serve as an input for accurate planning of logistic operations.
  • To leverage optimization techniques to transshipment planning and scheduling in hubs as well as freight transport network planning and scheduling to make the best use of the available resources.
  • To apply machine learning techniques to identify and remedy potential incidents or events which could disrupt the supply chain, to take the relevant actions and needed reconfigurations ensuring a continuous, seamless flow of the operations.
  • To make use of distributed constraint satisfaction techniques to allow the negotiation among different agents involved in the supply chain taking into account several constraints that arise in real-time.
  • To develop specific services leveraging the aforementioned processing techniques and delivering 2 main results:
    • Control and decision making tool for logistics operations capable of monitoring of goods through the whole logistics chain, allowing an integrated planning of resources a providing dynamic routing relying on synchromodality.
    • Real time information on sea, rail and road freight transport will be delivered by means of a website positioning sea/rail and road cargo and communicating their arrival time.
  • To elaborate a full exploitation plan for the results and define the disseminations actions for promotion.

 

Project Status: 
Ongoing
Funding Amount (€): 
429906.25
Research line: 
Constraint Satisfaction
Acronym: 
LOGISTAR
External researchers: 
Fundación Deusto, Spain
University College Cork (UCC), National University of Ireland, Ireland
Drustvo Za Konsalting (DUNAVNET) , Serbia
Semantic Web Company (SWC), Austria
Preston Solutions, UK
MDS Transmodal Limited, UK
Software AG (SAG), Germany
DBH Logistics IT AG (DBH), Germany
GESP SRL, Italy
Ahlers, Belgium
ZAILOG, Italy
NESTLE York Ltd, UK
United Biscuits (PLADIS), UK
Codognotto Italia SPA, Italy
Geographical scope: 
European
Grant type: 
Competitive
Transferència: 

Lógica y algoritmos

Initial/final date: 
01 December 2014 to 30 November 2017
Main researcher: 
Project type: 
Intramural
Funding Entity: 
CSIC (Intramural 201450E045)
Research line: 
Constraint Satisfaction
Acronym: 
Logal

Una aproximación declarativa para modelizar, analizar y resolver problemas

Initial/final date: 
01 January 2014 to 31 December 2015
Main researcher: 
Project type: 
Plan Nacional
Funding Entity: 
Ministerio de Economía y Competitividad (TIN2013-45732-C4-4-P)
Description: 
Hard decision and optimization problems are present in many applications of computational tools. Some challenging questions are: how do we schedule a professional sports league, whether a cryptographic protocol is safe, whether there is some input data that will cause a program to hang or produce wrong output, which is the most convenient time slot for a video conference, how can a flexible admission control for safe overbooking be defined for cloud computing, or how a flexible text cataloging and information retrieval can be defined for the (semantic) web. A declarative approach to solve such problems consists in modelling the problem in some logical framework and then applying powerful logic-based techniques to analyse and/or solve the resulting model. In this setting, problems can often be formulated using mathematical formulas or other logic based languages. Once the problem is expressed in the corresponding language we can use existing general techniques or develop novel ones to solve it. When this approach is applied to our specific problems, we might need to use some of their particularities in order to improve its performance. However, thanks to the initial abstraction from particular problems to general problems expressed in a given language, this "declarative approach" makes the development of tools to solve hard real problems significantly easier and faster. As logical frameworks we will mainly use (extensions of) propositional and first-order logic. In particular, we will consider: SAT (satisfaction of propositional formulas), SAT modulo theories (SMT, where propositions are replaced by atoms in the given theory), Constraint Programming (CP, where clauses are replaced by predicates over a pre-defined language), Fuzzy Logic (FL, where clauses have some uncertainty), Rewrite Logic (RWL, with modelling and programming advanced capabilities), Logic Programming (LP), and Fuzzy Logic Programming (FLP). In this project we will focus on the combination and extension of these successful formal languages to get the necessary expressiveness for our practical applications. Guided by applications for scheduling and planning, for security, for agents, for machine learning, for concurrent and sequential program analysis, for bio-informatics or for XML manipulation, we will develop efficient algorithms and tools to solve problems described in the previous logical frameworks. As precise applications we consider: (a) sports scheduling as done with Hypercube and KNVB, the Netherlands, (b) program analysis in collaboration with Microsoft Research at Cambridge, (c) evaluation of transcript sequences in collaboration with the Centre for Genomic Regulation (CRG) in Barcelona, (d) security in collaboration with the University of Illinois at Urbana-Champaign and the Naval Research Laboratory at Washington, (e) new features in the Maude language with the University of Illinois at Urbana-Champaign and SRI International in California, (f) knowledge discovering and flexible manipulation of data retrieved from the web in collaboration with the University of Almeria, and (g) fuzzy scheduling for resource usage within cloud data centers with the Umea University. This is therefore a project that covers all the way in the development and application of computer technologies from the basic theory and techniques to industrial and social impact problems.
Research line: 
Constraint Satisfaction
Acronym: 
DAMAS
External researchers: 
Jimmy Lee,

Weigted Soft Constraints: Centralized and Distributed Cases

Initial/final date: 
01 January 2010 to 31 December 2012
Main researcher: 
Project type: 
Plan Nacional
Funding Entity: 
TIN2009-13951-C02-02
Description: 
Within soft constraint reasoning, weighted CSP (WCSP) provide a very convenient framework for modeling and solving many real-world optimization problems. Motivated for the relevance of WCSP model, this project aims at developing efficient solving algorithms for this model. We diferentiate between the centralized approach, where a WCSP instance is kept in a single computer, and the more recent distributed approach, where the instance is distributed among different computers (but none of them contains the whole instance). We also give special attention to the boolean case (namely, when variables only have two values to chose from) because it extends the famous boolean satisfiability problem (SAT) that is ubiquous in Computer Science. SAT solvers have improved their performance dramatically in the last 15 years, and some of the techniques responsible of this sucess can also be incorporated to boolean WCSP (being Max-SAT the most popular problem of this class). In the centralized case, we intend to achieve the overall goal by enhancing existing search algorithms with sophisticated techniques such as backjumping, learning and adaptive inference, and by improving current implementations with tailored linear programming solvers and more advanced data structures. In the distributed case, we intend to achieve the goal by combining existing search algorithms with local consistency enforcement and inference. In the distributed context, we also want to collect and/or build sets of benchmarks in order to compare the different alternatives. This project combines two research groups with complementary expertise.
Research line: 
Constraint Satisfaction
Acronym: 
RECEDIT
In collaboration with: 
Javier Larrosa, Dep LSI, UPC

Constraint reasoning and its application to planning

Initial/final date: 
01 October 2006 to 30 September 2009
Main researcher: 
Project type: 
-
Funding Entity: 
TIN2006-15387-C03-01
Description: 
Constraint reasoning techniques, developed in the context of AI research, have successfully solved many real problems. Although it is a mature field, there are many important active lines of research such as open CSPs, distributed CSPs, quantified CSPs and soft constraint problems. Another well-known AI topic is Planning. It has recently gained new strenth in the research community due to its reformulation in terms of graphs, search and constraint satisfaction. In this project we want to make progress in the open lines of research of both fields. We also want to exploit the close relation between constraint processing and planning. Our objectives are: Constraint reasoning. Our goal is to contribute to the efficient resolution of the new paradigms (open, distributed and quantified CSPs) as well as continue our work on soft constraints, where we have already made relevant contributions, extending the results to closely related models such as clausal formulas or bayesian networks. Since the problem is in general untractable, we also want to identify tractable classes (soluble in polynomial time). Planning Our goal is to refine the methods based on heuristic search for planning. We also want to study and develop the combination of search and inference. We want to exploit the existence of symmetries to decrease the solving effort, which is a well-known topic in the constraint community. We present this project as a continuation of REPLI (TIC2002-04470-C03) motivated by the good results and experience that was achieved. We have now a larger and more experienced team of researchers. The benefits of the project will be the accomplishment of the previous goals as well as the integration of different research groups with complementary expertise.
Funding Amount (€): 
0.00
Research line: 
Constraint Satisfaction
Acronym: 
REPLI-II-2006

Constraint reasoning and its application to planning

Initial/final date: 
31 December 2005 to 30 June 2007
Main researcher: 
Project type: 
-
Funding Entity: 
TIN2005-09312-C03-01
Description: 
Constraint reasoning techniques, developed in the context of AI research, have successfully solved many real problems. Although it is a mature field, there are many important active lines of research such as open CSPs, distributed CSPs, quantified CSPs and soft constraint problems. Another well-known AI topic is Planning. It has recently gained new strenth in the research community due to its reformulation in terms of graphs, search and constraint satisfaction. In this project we want to make progress in the open lines of research of both fields. We also want to exploit the close relation between constraint processing and planning. Our objectives are: Constraint reasoning. Our goal is to contribute to the efficient resolution of the new paradigms (open, distributed and quantified CSPs) as well as continue our work on soft constraints, where we have already made relevant contributions, extending the results to closely related models such as clausal formulas or bayesian networks. Since the problem is in general untractable, we also want to identify tractable classes (soluble in polynomial time). Planning. Our goal is to refine the methods based on heuristic search for planning. We also want to study and develop the combination of search and inference. We want to exploit the existence of symmetries to decrease the solving effort, which is a well-known topic in the constraint community. We present this project as a continuation of REPLI (TIC2002-04470-C03) motivated by the good results and experience that was achieved. We have now a larger and more experienced team of researchers. The benefits of the project will be the accomplishment of the previous goals as well as the integration of different research groups with complementary expertise.
Funding Amount (€): 
0.00
Research line: 
Constraint Satisfaction
Acronym: 
REPLI-II

Exploiting non-standard CSP for Leveraging Application Intelligence

Initial/final date: 
01 January 2000 to 30 June 2002
Main researcher: 
Project type: 
-
Funding Entity: 
IST-1999-11969
Description: 
Constraint technology offers advantages over traditional Operations Research methods to solve optimisation tasks. However, the CSP model presents some limitations because all constraints are mandatory. In real problems, constraints are often preferences, but if included in the CSP model an over-constrasined problem is produced. Then, the only option is to relax / remove some of the preference constraints by hand, but it is difficult to assure teh solution quality and this is not commercially satisfactory. In the last years, several theoretical models as well as algorithms have been developed to represent and solve CSP with preferences. They have been produced in an academic context, but they are not fully available to industry. This project aims to bridge the gap between academic results and industrial needs. Specifically, the goal of ECSPLAIN is to develop methods, techniques and generic software, making it possible to address such problems in a systematic manner, thus insuring quality solutions to complex, constrained optimisation tasks. More specifically, the project focuses on the resolution of over-constrained problems and of problems involving multiple optimisation criteria and/or a wide variety of preference constraints.
Funding Amount (€): 
0.00
Research line: 
Constraint Satisfaction
Acronym: 
ECSPLAIN

Constraint-based reasoning and combinatorial optimization: Application to planning and uncertainty management

Initial/final date: 
01 November 2002 to 31 October 2005
Main researcher: 
Project type: 
-
Funding Entity: 
TIC2002-04470-C03-03
Description: 
The inclusion of soft constraints in the constraint-based reasoning model has connected this model with combinatorial optimization. This allows one to have a common view of both areas, exchanging methods between them. This project tries to use, integrate and extend ideas that have been shown successful for constraint reasoning in a double dimension: Soft constraints. Contribution to the issues caused by the inclusion of soft constraints in the constraint model, extending existing results for hard constraints. In particular, we will focus on soft constraint propagation and local consistency, resolution algorithms and their complexity, and the efficient formulation of real problems. Applications. To apply constraint techniques to two different fields: planning and uncertainty management. On planning, the idea of planning as heuristic search wll be extended to produce a temporal planner of high performance, combining a branch-and-bound scheme with prunning techniques based con constraint propagation. On uncertainty management, constraint-solving algorithms based on decomposition will be applied to bayesian networks and to the possibilistic model. Finally, other problems will be studied, in particular the optimization of circuit design. Project benefits include not only the above mentioned contributions and the resolution of the applications, but also the integration of research groups with complementary backgrounds.
Funding Amount (€): 
0.00
Research line: 
Constraint Satisfaction
Acronym: 
REPLI