Final CFP: CP98 workshop on constraint problem reformulation

Subject: Final CFP: CP98 workshop on constraint problem reformulation
From: Stefano Bistarelli (
Date: Thu Jul 30 1998 - 16:14:54 MET DST

Apologies if you receive this more than once!

                          CALL FOR PAPERS
                           CP98 Workshop
                 Constraint Problem Reformulation

                           Pisa, Italy
                         30 October 1998
(in conjunction with the fourth International Conference on Principles
and Practice of Constraint Programming (CP98))

This workshop will focus on reformulating Constraints Problems to
take advantage of efficient techniques in particular constraints
problem domains. In particular, the workshop will focus on
reformulating NP-Complete problems and related optimization problems
to translate them to domains which have good problem solver performance

A fundamental issue is planning and search is the choice of an
appropriate problem representation. While the importance of
problem representation has been widely recognized within AI,
starting from the work of Saul Amarel on represenations of
the Missionaries and Cannibals, there have not been a great many
success stories. Much research focuses on exploiting the
domain-specific details of a particular problem domain in order
to come up with the best algorithm. However, there is considerable
value to exploring alternate representations for which good algorithms
already exist. For eaxmple, SATPLAN exploits the excellent performance
of algorithms (both deterministic and non-deterministic) to solve
SAT problem instances. SATPLAN's success is hard-won, however,
in that automatic procedures for translating planning problems to
SAT representation are not as effective as hand-designed representations.
Other efforts at reformulation, such as encoding Hamiltonian Cycle
problems as SAT problems and using local search to solve them,
have not been successful.


Issues which workshop submissions will focus on include:

  What are the issues in reformulation?
        Speed of translation procedure.
        Exposing/hiding of information by the translation procedure.
        Translation by hand vs. automated translation.
        Translation of problem classes vs. translation of problem instances.
  How should reformulation be used?
        Reformulation to solve problems directly.
        Reformulation to motivate improvements in the original space.
  Explaining success/failure of reformulation.

A more detailed explanation of the workhshop themes can be found
in the extended workshop announcement, which is available on the
workshop web page.

                        Paper Submission and Important Dates

Prospective authors are asked to submit papers of 6 pages or less
in length. The papers should be original, written in English, and
formatted on either 8.5 by 11 inches or A4 paper. Papers may be
sent electronically, with appropriate instructions, or by mail.
Submissions should be submitted to both Jeremy Frank and Mihaela Sabin;
contact information is provided at the end of the call.
Workshop attendees are asked to send a 1 page statement of interest;
all of these statements will be published with the workshop proceedings.

  August 28, 1998: Submission of workshop papers.
  September 11, 1998: Announcement of workshop speakers and
                         posting of workshop schedule.
  September 25, 1998: Submission of statement of interest by
                         workshop attendees.
  September 25, 1998: Final copy of the accepted papers due.
  October 30, 1998: Workshop occurs in conjunction with
                         CP 98 in Pisa, Italy.


With the authors permission, we will publish all of the accepted papers
on the workshop web site. We will also publish the papers and
statements of interest, along with the introductory components of the
workshop call for papers, in a booklet which will be made available
at the workshop.

                                Workshop Format

The morning session will be reserved for presentations:
each presentation will be limited to 20 minutes.
A 3.5 hour morning session leaves time for roughly 10 presentations
of 20 minutes each. The afternoon session would then be reserved
for free-form discussion on the topics presented in the morning,
with about a half-hour wrap up. The accompanying workshop proceedings
will include a 6 page paper for each speaker, plus 1 page statements
of interest from any other participants.

                                Contact Information

    Jeremy Frank
    Caelum Research Corp.
    Mail Stop 269-1
    NASA Ames Research Center
    Moffett Field, CA 94040

    Mihaela Sabin
    Computer Science Department
    University of New Hampshire
    Durham, NH 03824

Constraint Programming 1998 page:
Constraint Problem Reformulation Workshop page:

This archive was generated by hypermail 2b25 : Fri Mar 03 2000 - 16:17:16 MET