Contributed Session Tue.3.H 3003A

Tuesday, 15:15 - 16:45 h, Room: H 3003A

Cluster 5: Constraint programming [...]

Constraint programming methodology


Chair: Burak Gokgur



Tuesday, 15:15 - 15:40 h, Room: H 3003A, Talk 1

Toby Walsh
Breaking variable and value symmetry in constraint satisfaction and optimisation problems


Factoring out the symmetry in a model is important for solving many constraint satisfaction and optimisation problems. Symmetries can act on the variables, or on the values, or on both the variables and the values in a model.
A simple but nevertheless effective method to deal with symmetry is to post static constraints which eliminate symmetric assignments. If a model has value symmetry in addition to variable symmetry, we might simply post the relevant value symmetry breaking constraints in addition to the variable symmetry breaking constraints.
We consider three issues with this approach.

  • Soundness: Is it safe to post together the variable and value symmetry breaking constraints?

  • Completeness: Does this combination of symmetry breaking constraints eliminate all symmetry from the problem? If not, how can we eliminate all symmetry?

  • Complexity: What is the complexity of breaking all variable and value symmetry? And of propagating the combination of the variable and value symmetry breaking constraints together?



    Tuesday, 15:45 - 16:10 h, Room: H 3003A, Talk 2

    Alexander Schnell
    The impact of the predefined search space on recent exact algorithms for the RCPSP

    Coauthor: Richard F. Hartl


    The problem of assigning starting times to a number of jobs subject to resource and precedence constraints is called the resource-constrained project scheduling problem (RCPSP). This presentation deals with exact algorithms for the standard version of the RCPSP assuming a single mode, non-preemption and renewable resources. Recent exact algorithms for this problem combine a branch and bound-based optimization search with principles from constraint programming, boolean satisfiability solving and mixed-integer programming for the branching and the fathoming of the search space. In our presentation, we analyze and enhance two recent exact algorithms by a parallel solving procedure. The latter consists of running the exact algorithm in parallel on an instance with different variable domains which are determined through a preprocessing step based on activity lists. Our results on instances with 60, 90 and 120 jobs show that the efficiency of the exact algorithms strongly varies depending on the predefined search space. Moreover, when employing the best found search space (which is not the smallest), we can improve two recent exact algorithms from the literature.



    Tuesday, 16:15 - 16:40 h, Room: H 3003A, Talk 3

    Burak Gokgur
    Mathematical modelling and constraint programming approaches for operation assignment and tool loading problems in flexible manufacturing systems

    Coauthors: Brahim Hnich, Selin Ozpeynirci


    This study presents mathematical programming and constraint programming models that aim to solve scheduling and tool assignment problems in flexible manufacturing systems. In our problem, there are a number of jobs to be processed on parallel computer numerically controlled machines. Each job requires a set of tools and the number of tools available in the system is limited due to economic restrictions. The problem is to assign the jobs and the required tools to machines and determine the schedule so that the makespan is minimized. A mathematical model and three constraint programming models for this problem are developed and the results of the experimental study are reported. Our empirical study reveals that the constraint programming approach leads to more efficient models when compared to mathematical programming model in terms of solution quality and computation time. This work is supported by The Scientific and Technological Research Council of Turkey (TÜBITAK).


  •   personal loans. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.