Volume 0, Number 2, July 2004

Constraint Programming News

volume 0, number 2, July 2004

Editors:
Jimmy Lee (events, career news)
Eric Monfroy (profiles, publications)
Toby Walsh (news, reports)

Contents

News

Welcome to the second number of CP News, an initiative of the CP organizing committee. We aim to provide a comprehensive summary of important news in the area of constraint programming. The newsletter will be published quarterly in January, April, July, and October. Please email the relevant editor with any news, event, report or profile you want published. To subscribe, please register here.

Each year, the CP community elects two new members to serve on the CP organizing committe. The committee consists of 10 members: 6 elected members, and 4 members drawn from the current and past local and program chairs. The committee decides the venue of the annual CP conference, program and conference chairs. It also supports activities like the doctoral programme, summer schools, this newsletter, etc. This year, the terms of Jean Francois Puget and Peter Stuckey end. The six candidates standing for these positions in alphabetical order are: Michela Milano, Patrick Prosser, Jean-Francois Puget, Barbara Smith, Peter Stuckey and Edward Tsang. If you have attended at least one CP conference, you are allowed to vote. Voting can be performed online between now and 1st Sept by visiting here.

One of the initiatives supported by the CP organizing committee is a new web portal, CP online. This is designed to be a single place for information about constraint programming. Please visit this site, and add your news, conferences announcements, online resources, etc.

After a successful series of five CP-AI-OR international workshops (Ferrara, Paderborn, Ashford, Le Croisic, and Montreal) devoted to integration of Constraint Programming, Artificial Intelligence, and Operations Research techniques. CP-AI-OR 2004 became a conference with the first meeting held in Nice (France) with more than 100 participants. In 2005, The Second CP-AI-OR Conference will be organized by Roman Bartak and Michela Milano in Prague (Czech Republic) in early June. Like in the previous years, CP-AI-OR 2005 will be co-located with a Master Class for PhD students, researchers, and practitioners on Meta-heuristics and CP organized by Gilles Pesant. More information about CP-AI-OR 2005 will be available here.

The French constraint programming community is happy to announce the formation of a unique association: the AFPC (Association Francaise pour la Programmation par Contraintes - French Association for Constraint Programming). With around 100 members, the new association, among other activities, will steer a new annual conference - JFPC (Journees Francophones de Programmation par Contraintes - French speaking Constraint Programming Days) - that unites the two JFPLC and JNPC conferences. A 17 member administration board has been elected for one year. The current secretariat of the association is constituted of: Narendra Jussien (president), Francois Fages (vice-president), Pierre Deransart (general secretary), Laurent Simon (secretary), and Michel Adam (treasurer).

Publications

PhD theses:

Olli Kamarainen, "Local Probing - A New Framework for Combining Local Search with Backtrack Search", IC-Parc, Imperial College London, 2004.

Neil Yorke-Smith, "Reliable Constraint Reasoning with Uncertain Data", IC-Parc, Imperial College London, 2004.

Recent books

New slides and errata for the book: "Essentials of Constraint Programming" are available here.

Combinatorial Optimization Polyhedra and Efficiency Series: Algorithms and Combinatorics, Vol. 24 Schrijver, Alexander 2003, Vol. A: XXXVIII, 648 S. Vol. B: XXXIV, 570 S. Vol. C: XXXIV, 664 S. (3 volume-set, not available separately)., Hardcover ISBN: 3-540-44389-4

Programming Constraint Services High-Level Programming of Standard and New Constraint Services LNAI Vol. 2302, Christian Schulte, 2002, XII, 176 pp., Softcover ISBN: 3-540-43371-6

Special issues:

SAT 2005. Special issue of the Journal of Automated Reasoning devoted to recent progress in propositional satisfiability. Guest Editors: Enrico Giunchiglia and Toby Walsh. Submission deadline, 1st Nov 2005.

Recent Advances in Constraints: forthcoming LNAI volume, based on the CSCLP '04 workshop held in Lausanne, June 23-25, 2004. The annual workshop on Constraint Solving and Constraint Logic Programming, jointly sponsored by ERCIM and Colognet, attracted 20 paper presentations. Many of the papers are of interest to a wider audience and the intention of this book is to make them more widely accessible. Authors of papers presented at the workshop are therefore invited to submit final versions that take into account the discussion at the workshop. In addition, we give an opportunity for other papers of good quality to appear in this volume, even when they have not been presented at the workshop. All submissions will be peer-reviewed. Submission of a paper implies implicit agreement to review several other submissions. Papers are due Sept 10th, 2004 and should be formatted in Sprinter LNCS style and not exceed 15 pages. Please submit papers in .pdf format by e-mail to: adrian.petcu@epfl.ch

Web resources:

The Constraint Handling Rules (CHR) programming language web pages have been redesigned, updated and extended. There is also a link to the minutes and proceedings of the First Workshop on Constraint Handling Rules that took place in May.

Events

AAAI 2004, The Nineteenth National Conference on Artificial Intelligence. July 25 - 29, 2004, San Jose, California, USA.
PATAT 2004, The 5th international conference on the Practice And Theory of Automated Timetabling. 18th August - 20th August 2004, Pittsburgh, USA.
ECAI 2004 workshop on "Modelling and Solving Problems with Constraints", 22 August 2004, Valencia, Spain.
ECAI 2004 workshop on "Constraint Satisfaction Techniques for Planning and Scheduling Problems", 23 August 2004, Valencia, Spain.
ECAI 2004 workshop on "Configuration", 23-24 August 2004, Valencia, Spain.
ECAI 2004 tutorial on "Constraint Processing", Pedro Meseguer, Thomas Schiex 24 August 2004, Valencia, Spain.
ECAI 2004, 16th European Conference on Artificial Intelligence (2004). 22-27 August, 2004, Valencia, Spain. http://www.dsic.upv.es/ecai2004/
CSLP 2004, International Workshop on Constraint Solving and Language Processing. 1-3 September 2004, Copenhagen Business School, Copenhagen, Denmark. Contributions submission deadline: 9 July, 2004.
CICLOPS'04, Colloquium on Implementation of Constraint and LOgic Programming Systems (held in conjunction with ICLP'04). 6-10 September, 2004, Saint-Malo, France.
COLOPS'04, 2nd International Workshop on COnstraint & LOgic Programming in Security (held in conjunction with ICLP'04). 6-10 September, 2004, Saint-Malo, France.
MultiCPL 2004, 3rd International Workshop on Multiparadigm Constraint Programming Languages (held in conjunction with ICLP'04). 6-10 September, 2004, Saint-Malo, France.
ICLP'04, Twentieth International Conference on Logic Programming. 6-10 September, 2004, Saint-Malo, France.
KI2004, 27th GERMAN CONFERENCE ON ARTIFICIAL INTELLIGENCE. September 20-24, Ulm, Germany.
AISC 2004, 7th International Conference on ARTIFICIAL INTELLIGENCE AND SYMBOLIC COMPUTATION. September 22-24, 2004, RISC (Research Institute for Symbolic Computation), Castle of Hagenberg, Austria.
CP 2004, Tenth International Conference on Principles and Practice of Constraint Programming, 27 September - 1 October 2004, Toronto, Canada. (Call for Demos, dealine: July 11, 2004)
Third International Workshop On Modelling and Reformulating Constraint Satisfaction Problems (held in conjunction with CP 2004). 27 September 2004, Toronto, Canada. Paper submission deadline: July 9, 2004.
Soft 2003, 6th International Workshop on Soft Constraints and Preferences (held in conjunction with CP 2004). 27 September 2004, Toronto, Canada. Paper submission deadline: July 9, 2004.
SymCon'04, 4th International Workshop on Symmetry and Constraint Satisfaction Problems (held in conjunction with CP 2004). 27 September 2004, Toronto, Canada.
First International Workshop on Constraint Propagation and Implementation (held in conjunction with CP 2004). 27 September 2004, Toronto, Canada.
COSOLV'2004, Fourth Workshop on Cooperative Solvers in Constraint Programming (held in conjunction with CP 2004). 27 September 2004, Toronto, Canada. Paper submission deadline: July 5, 2004.
LSCS'04, 1st International Workshop on Local Search Techniques in Constraint Satisfaction (held in conjunction with CP 2004). 27 September 2004, Toronto, Canada. Paper submission deadline: July 21, 2004.
Workshop on CSP Techniques with Immediate Application, (held in conjunction with CP 2004). 27 September 2004, Toronto, Canada. Paper submission deadline: July 26, 2004.
CLIMA V, Fifth International Workshop on Computational Logic in Multi-Agent Systems (co-located with JELIA'04). September 29 and 30, 2004, Lisbon, Portugal.
MOZ 2004, Second International Mozart/Oz Conference (MOZ 2004). 7-8 Oct, 2004, Charleroi, Belgium. Paper submission deadline: 16 July.
Fourth EU/ME Workshop Design and Evaluation of Advanced Hybrid Meta-heuristics. 3-4 November 2004, Nottingham, UK. Paper submission deadline: 27 August 2004. Send submissions (3-5 pages extended abstracts) to Nysret Musliu at musliu@dbai.tuwien.ac.at.
CSP 2005: Track on Constraint Solving and Programming part of the 20th Annual ACM Symposium on Applied Computing SAC'2005 Santa Fe, New Mexico, March 13 -17, 2005. Deadline: August 31, 2004
ICAPS 2005, International Conference on Automated Planning & Scheduling, June 5 - 10, 2005, Monterey, California, USA. Papers dues on 15 November, 2004. Workshop proposals due on 1 October, 2004 Tutorial proposals due on 15 December, 2004 Software demos due on 21 March, 2005. (Competition in Engineering for Planning)
CP 2005, 11th International Conference on Principles and Practice of Constraint Programming, October 1-5 2005, Sitges, Spain. Co-located with ICLP and an annular eclipse. Program chair: Peter van Beek. Conference chairs: Pedro Meseguer and Javier Larrosa.
CP 2006, 12th International Conference on Principles and Practice of Constraint Programming, Fall 2006, Nantes, France. Program chair: Frederic Benhamou. Conference chairs: Eric Monfroy and Frederic Benhamou.

Career news

PhD position in Grobner Bases Theory

I intend to write a book on Grobner bases theory using the Theorema System currently developed in my Theorema Working Group. I would also like to organize a special semester on Grobner bases in the frame of the newly created Radon Institute for Computational and Applied Mathematics (RICAM, Linz, Austria) and to build up a Grobner bases web site with a papers repository etc. I invite students who want to do their PhD work on Grobner bases under my personal advice and who also would like to help me with the preparation of the book and the web site. Prerequisites: good background in mathematics and software, practice in formal proving.

The PhD study will be in the frame of the RISC PhD study. The research assistantship will be approx. 1000 Euro net per month, which is well sufficient to cover living expenses in Austria.

Applications should be sent by e-mail to the address below.

Bruno Buchberger, Professor of Computer Mathematics, Research Institute for Symbolic Computation, Johannes Kepler University, A4232 Castle of Hagenberg, Austria. Phone office: ++43 732 2468 9921. Mobile Phone: ++43 664 4211646. Fax: ++43 732 2468 9930. E-mail: Buchberger@RISC.Uni-Linz.ac.at. WWW: http://www.risc.uni-linz.ac.at/people/buchberg/

Reports

FLAIRS 2004 by Rich Wallace.

FLAIRS had both a constraints track and a distributed CSP track this year. There were some good papers presented in both of these sessions.

In the constraints track:

In a talk about visualization and explanation, Ghoniem, Jussien and Fekete presented a new visualization tool, VISEXP. They use these explanation/ visualization facilities to explore "solver dynamics", which distinguishes this approach from those concerned only with explanations in terms of the original problem and its constraints. The representation is based on adjacency matricies (instead of node-arc diagrams, which become cluttered when problems are large) and use clustering techniques, apparently to zero in on dynamic linkages between variables based on propagation effects. The authors compare VISEXP with other visualization tools; they make the point that in VISEXP visualization is not as dependent on the order in which decisions were made.

Bartak and Erben described a new algorithm for singleton arc consistency. This algorithm uses AC-4 style support structures to improve its efficiency. The paper includes a discussion of how these structures are implemented. There is also the obligatory comparison with Brand X, in this case "SAC-1".

Legtchenko, Lallouet and Ed-Dbali discussed the "automatic construction of [consistency] operators", building on the work of Apt & Monfroy and Fruehwirth. The authors define a basic reduction function and then some simple consistency operators that are weaker than arc-consistency. They implement their ideas using an "indexical language" and test the resulting system on "word constraints" and "crossword CSPs".

Lever described a local search/constraint propagation hybrid that was used to solve minimum weight shortest path problems (i.e. routing problems where routing is constrained by demands and capacities on the links). This approach reverses earlier approaches that used local search for optimization and constraint propagation for the hard constraints. Although incomplete, it performs well against complete algorithms such as the probe-search of El-Sakkout.

Mitra and Kim presented another hybrid algorithm composed on min-conflicts backtracking and forward checking. The basic idea is to use MC to get a good partial solution, which is completed by FC. Results were given of tests on random graph coloring problems where the new algorithm was compared with pure MC and FC.

Ringwelski and Wallace described an multiagent system composed of "reactive agents" that can be used for dynamic distributed constraint solving. Some basic properties of the system were described, and it was compared with other approaches to distributed constraint solving involving either a few 'smart' agents or many more-or-less 'reactive' agents.

Hickey and Wittenberg described a hybrid system, CLP(F) that is designed to handle problems involving ordinary differential eqns. A major theme of the talk was the problem of rounding with floating point numbers, which is apparently a serious problem in modeling ODEs. The system uses interval arithmetic to avoid this problem. It seems to me that this work might be relevant to explanations-people (if they take a 'longer' view), since one purpose is to determine answers to questions about the analog-digital systems that can be represented in CLP(F). In the distributed constraint reasoning track:

Mertens and Holvoet described a distributed ant colony algorithm for CSPs and PCSPs. The authors discuss the usefulness of this approach, but the difficulties in designing such algorithms for a distributed setting. Experimental tests compared the ant colony algorithm with the distributed breakout algorithm.

Wallace and Silaghi described a technique for monitoring privacy loss in multi-agent problem solving, that could be used to select proposals in the course of the solving process that would limit the information revealed about an agent's own subproblem.

Zivan and Meisels described a new algorithm for DisCSPs that conducts multiple searches concurrently. The full problem can be partitioned dynamically through domain splitting. Search is coordinated by circulating a current partial solution among agents. The resulting concurrent backtracking algorithm is compared experimentally with ABT.

Profiles

The DEIS groups in Bologna involved in Constraint Programming and Operations Research collaborate closely. These groups include the following members: Alberto Caprara, Andrea Lodi, Zeynep Kiziltan, Silvano Martello, Michela Milano, Paola Mello, Michele Monaci, Paolo Torroni, Paolo Toth, Daniele Vigo and 8 PhD students.

The groups of Constraint Programming and Operations Research are actively involved in the following research activities:

  • Integration of OR techniques in Constraint Programming: Constraint Programming has shown its effectiveness as general paradigm to solve Combinatorial Optimization problems by addressing those problems from a rather different viewpoint with respect to Operations Research. On the other hand, OR techniques provide a wide arsenal of algorithms whose integration within the Constraint Programming framework has attracted both communities in the last few years by producing highly effective hybrids techniques. The group in Bologna has a wide experience in this field and has developed effective techniques for the integration. Cost-based filtering has been defined as a way of integrating pruning based on feasibility reasoning with pruning based on optimality reasoning.
  • Hybrid search strategies: This research field is covered in two aspects: The first concerns the integration of local search techniques within MIP solvers aimed at enhance the capability of the solvers to provide good solutions quickly. In this setting, the local branching scheme has been developed and tested. The second concerns the definition of search strategies and heuristics based on results coming from relaxations. On one hand discrepancy based search has been studied with heuristics based on reduced costs. On the other hand additive bounding techniques have been studied for improving the proof of optimality.
  • Extensions of Constraint Programming Languages: the group has worked on the use of constraint programming in applications where the domain values are not available, and have to be acquired or computed, before the constraint satisfaction process starts. This is true in applications on the Internet, in visual systems, in planning systems working in complex domains, in configuration problems. The Bologna group has devised an Interactive Constraint Satisfaction (ICSP) framework and the corresponding Constraint Programming language implemented with Constraint Handling Rules.
  • Combinatorial Optimization methods for genome comparison: The research has two main objectives. The first objective is to consider the most used model to compare two genomes, namely the computation of the minimum number of inversions (reversals) of gene subsequences that leads from one genome to the other. The second objective is the study of models to compare three or more genomes, recently proposed by computational biologists. The purpose of these models is to define a median genome, corresponding to a possible ancestor, at minimum overall distance from the given genomes. For the combinatorial optimization problems arising from the above models, the research is aimed at defining exact algorithms as well as analyzing the worst-case performance of approximation algorithms.
  • Symmetry breaking: The presence of symmetries in constraint satisfaction problems has been identified as a source of inefficiency since much computational time is spent in visiting equivalent states. We have developed two approaches: one imposing constraints during search representing nogoods. The second is based on the imposition of symmetry breaking constraints in matrix models.
  • Compliance verification of interaction protocols: a constraint-based language Within the SOCS EU project, the group in Bologna is currently studying an abductive proof-procedure able to check the compliance of agents to protocols, and to provide a set of expectations to possibly guide the further behavior of the agents. The proof-procedure is able to abduce literals with existentially and universally quantified variables and possibly constrained through CLP(FD) constraints. The abductive proof-procedure implements abducible literals as CHR constraints (thus, abduction itself is considered as a constraint solver on the Herbrand universe). A further solver, necessary for dealing with CLP(FD) constraints with explicit quantification of variables, has been theoretically formalised and implemented. The two solvers interact smoothly as a two-sorted CLP language.
  • Separation: Important theoretical questions concerning the separation of both general and special purpose inequalities are of central relevance for one of the most effective methods for solving Mixed Integer Problems, i.e., the branch-and-cut technique. This research is aimed at improving the practical capability of branch-and-cut to solve both classical Combinatorial Optimization problems, e.g., the Traveling Salesman and the Maximum Cut problems, and real-world applications which can be modeled as general Mixed Integer Programs.
  • Real-world applications concerning Crew Planning, Train Timetabling, Locomotive Scheduling, Electric Power Dispatching, Cutting and Packing in one and more dimensions, Combinatorial Auctions and Vehicle Routing are also considered, often being related to research contracts with Italian and European institutions. Several national and international collaborations with individual researchers and scientific institutions are active.

M. Fischetti, A. Lodi, S. Martello, P. Toth, "A Polyhedral Approach to Simplified Crew Scheduling and Vehicle Scheduling Problems", Management Science 47, 2001.
A.N. Letchford, A. Lodi, "Polynomial-time Separation of Simple Comb Inequalities", in W.J. Cook, A.S. Schulz, Eds., Integer Programming and Combinatorial Optimization - IPCO 2002.
F. Focacci, A. Lodi, M. Milano, "A Hybrid Exact Algorithm for the TSPTW", INFORMS Journal on Computing 14, 403-417, 2002.
F. Focacci, A. Lodi, M. Milano, "Cost Based Filtering", CP99, 1999. F.Focacci, M.Milano, "Global Cut Framework for removing symmetries", CP2001.
A. Guerri, M.Milano Learning Techniques for Automatic Algorithm Portfolio Selection, ECAI2004.
M.Milano (ed.) Constraint and Integer Programming ? Toward a Unified Methodology, Kluwer Academic Publisher, 2003.
A. Lodi, M.Milano, L.M. Rousseau Discrepancy-Based additive bounding, CP2003.
M. Gavanelli, E. Lamma, P. Mello, M. Milano Dealing with incomplete knowledge in CLP(FD) variable domains. ACM Transaction on Programming Languages and Systems, to appear.
M. Alberti, D. Daolio, P. Torroni, M. Gavanelli, E. Lamma, P. Mello Specification and verification of agent interaction protocols in a logic-based system, SAC 2004.
Z. Kiziltan. Symmetry Breaking Ordering Constraints. PhD Thesis, Department of Information Science, Uppsala University, Sweden, 2004
P. Toth, D. Vigo (eds.). The Vehicle Routing Problem. Monographs on Discrete Mathematics and Applications. S.I.A.M., 2002.
M. Fischetti, A. Lodi, "Local Branching", Mathematical Programming 98, 23-47, 2003.
A. Caprara, A.N. Letchford, ``On the Separation of Split Cuts and Related Inequalities'', Mathematical Programming 94 (2003) 279-294.
A. Caprara, M. Monaci, P. Toth, ``Models and Algorithms for a Staff Scheduling Problem'', Mathematical Programming 98 (2003) 445-476.
A. Caprara, R. Carr, S. Istrail, G. Lancia, B. Walenz, ``1001 Optimal PDB Structure Alignments: Integer Programming Methods for Finding the Maximum Contact Map Overlap'', Journal of Computational Biology 11 (2004). Marcas de calçado, bolsas e vestuário na Spartoo