previous day
next day
all days

View: session overviewtalk overview

09:00-10:00 Session 15

Invited Talk 3: Great Hall (#1022) (Chair: Peter Stuckey)

  • Jimmy Lee (Chinese University of Hong Kong), A Tale of Two Cities: Teaching CP with Story-Telling
10:00-10:30Coffee Break

Great Hall Lower Gallery (#1022K)

10:30-11:00 Session 16

ACP Research Excellence Award, Great Hall (#1022) (Chair: David Bergman)

11:00-12:30 Session 17A

DEI EventEast Common Room (#1034)

11:00-12:00 Session 17B

Constraints 2, Great Hall (#1022) (Chair: Pierre Schaus)

The p-dispersion problem with distance constraints

ABSTRACT. In the (maxmin) p-dispersion problem we seek to locate a set of facilities in an area so that the minimum distance between any pair of facilities is maximized. We study a variant of this problem where there exist constraints specifying the minimum allowed distances between the facilities. This type of problem, which we call PDDP, has not received much attention within the literature on location and dispersion problems, despite its relevance to real scenarios. We propose both ILP and CP methods to solve the PDDP. Regarding ILP, we give two formulations derived from a classic and a state-of-the-art model for p-dispersion, respectively. Regarding CP, we first give a generic model that can be implemented within any standard CP solver, and we then propose a specialized heuristic Branch&Bound method. Experiments demonstrate that the ILP formulations are more efficient than the CP model, as the latter is unable to prove optimality, except for small problems, and is usually slower in finding solutions of the same quality as the ILP models. However, although the ILP approach displays good performance on small to medium size problems, it cannot efficiently handle larger ones. The heuristic CP-based method can be very efficient on larger problems and is able to quickly discover solutions to problems that are very hard for an ILP solver.

MDD archive for boosting the Pareto constraint

ABSTRACT. Multi-objective problems are frequent in the real world. In general they involve several incomparable objectives and the goal is to find a set of Pareto optimal solutions, i.e. solutions that are incomparable two by two. In order to better deal with these problems in CP the global constraint Pareto was developed by Schaus and Hartert to handle the relations between the objective variables and the current set of pareto optimal solutions, called the archive. This constraint handles three operations: adding a new solution to the archive, removing solutions from the archive that are dominated by a new solution, and reducing the bounds of the objective variables. The complexity of these operations depends on the size of the archive. In this paper, we propose to use a Multi-valued Decision Diagram (MDD) to represent the archive of pareto optimal solutions. MDDs are a compressed representation of solution sets, which allows us to obtain a compressed and therefore smaller archive. We introduce several algorithms to implement the above operations on compressed archives with a complexity depending on the size of the archive. We show experimentally on bin packing and multi-criteria knapsack problems the validity of our approach.

12:00-12:30 Session 18

Competition Results:  Great Hall (#1022)

12:30-14:00Lunch Break

Great Hall Lower Gallery (#1022K)

14:00-14:30 Session 19

ACP Early Career Researcher Award, Great Hall (#1022) (Chair: David Bergman)

14:30-15:00 Session 20

ACP Doctoral Research Award, Great Hall (#1022) (Chair: David Bergman)

15:00-15:30Coffee Break

Great Hall Lower Gallery (#1022K)

15:30-16:30 Session 21

ACP General Assembly, Great Hall (#1022)

16:30-16:50 Session 22

Presentation of CP 2024 & CPAIOR 2024 conferences, Great Hall (#1022)


CP 2023 Conference Banquet (open to both student and full registrations)

Faculty Club, 41 Willcocks Street