A. Malapert

Modélisation Avancée PPC/PL

We introduce some combinatorial problems, algorithms and general methods such as linear and constraint programming.

S3 3 ECTS 24h OPT A. Malapert

Lectures

We work on the cryptator project using the choco solver.

  1. Getting started with the project.
    • Introduction to constraint programming ;
    • Research project management
      • Scientific context and objectives.
      • Tasks, milestones, deadlines, etc.

Schedule

Archive 2021-2022

Lectures

We learn basics of constraint programming using the choco solver.

  1. Introduction to constraint programming
  2. Modeling puzzle: the famous n-queens problem
  3. Modeling puzzle: cryptarithm
  4. Designing custom constraints and search for the n-queens problem
  5. Modeling a project scheduling problem
  6. Final Exam
  7. Modeling a university timetabling problem (project)

Resources

  • The shared github repository.
  • Lectures 1-4: Choco tutorials; my old CP course (sorry in French).
  • Lectures 5: chapter 10 entitled Project Management with PERT/CPM from the book Introduction to operations Research written by Hillier and Lieberman ; see also archive 2019-2020.
  • Lectures 6: the problem specification and state-of-the-art are part of the project.

Grading

  • Labs (20%): publishing corrections for two labs; github; pair work.
  • Project (40%): github; team work.
  • Final Exam (40%): modeling two simple problems on your computer within 3 hours; email; individual work.

Archive 2020-2021

Lesson 1: Project Management

We start with a a quick reminder from the [graph theory course] from pages 193 to 212 that will present the main algorithm used in project management : shortest path in a directed acyclic graph. Then, we will follow the chapter 10 entitled Project Management with PERT/CPM from the book Introduction to operations Research written by Hillier and Lieberman. The lab will be conducted using IBM Ilog Optimization Studio instead of an Excel worksheet.

Some additional resources are listed below :

Guidelines and addtional questions for the PERT/CPM Lab

I suggest to use the data model given below.

// Table 10.1 (without estimated durations)
tuple Activity {
  key string code;
  string description;
  {string} predecessors;
}
{Activity} Activities = ...;

// Figure 10.11
tuple TimeCostTradeoff {
  int normalTime;
  int crashTime;
  int normalCost;
  int crashCost;
}
// Table 10.7
TimeCostTradeoff tradeoffs[Activities] = ...;
CPM Models
  1. The most simple approach is to define two optimization models to apply the critical path method. The first model computes the Earliest Start Schedule while the second model computes the Latest Start Schedule for a given deadline/makespan.
  2. But, you will remark that these two models are very similar. In fact, it is possible to write a single model for which parameters, given as external data, define the schedule to compute (ES or LS).
  3. However, you still have to manually execute two run configurations to apply the CPM model. You can automate these two steps by using the IBM OPL Script language.
Approximating the Probability of Meeting the Deadline (p. 491) :
  1. What is the probability of finishing the project within of 44 weeks ?
  2. What is the probability of meeting the deadline of 47 weeks ?
  3. What is the probability to get the bonus by finishing the project within 40 weeks ?
Crashing
  1. You should start by writing a new model for crashing activities for a given makespan. If needed, the model is described in the chapter.
  2. Then, you can try to factorize some code with the CPM model(s) by using the include command.
  3. Last, you must compute the total crash cost for every possible makespan. Again, it can be automated with the IBM OPL Script language.
Unary Resource

A unary or disjunctive resource models a set of non-interruptible activities which must not overlap in the schedule: two tasks cannot be executed simulatenously.

  1. All activities use the the unary resource.
  2. Only crashed activities use the unary resource.

Textbooks

Archive 2019-2020

We will study and solve a real-life nurse rostering problem occurring at the university hospital centre Pasteur II.

Nurse rostering is a complex scheduling problem that affects hospital personnel on a daily basis all over the world 1. You will be provided the following information :

  • A decision-maker who is grappling with nurse rostering problem that needs solving.
  • A description of the problem context.
  • A formal problem specification.
  • Supporting data and past timetables.
  • Light software specifications.

You will apply theoretical concepts and software development process in a real world situation. Hopefully, the problem specification remains accessible and the problem instances remain small so that it is solvable with respect to time constraints of the course.

You will be developing more skills in:

  • Problem solving
  • literature review
  • Using analytical tools, both quantitative and qualitative
  • Decision making in complex situations
  • Coping with ambiguities
  • Learning how to apply optimization methods in similar situations

More precisely, you will discover new techniques or strengthen your knowledge in:

  • Nurse rostering problems
  • Integer programming and constraint programming
  • Local search and metaheuristics
  • Multicriteria decision-making Note that there is no prerequisite and that we will choose methods and techniques according to your will and skills. We will study several articles cited in the survey 1.

The teacher and all students will act as a team. We will define several work packages that will be assigned to groups of students. Your grades will depend on the realization of the work packages.

  1. The State of the Art of Nurse Rostering, Burke, E.K., De Causmaecker, P., Berghe, G.V. et al. Journal of Scheduling (2004) 7: 441. https://doi.org/10.1023/B:JOSH.0000046076.75950.0b ↩ ↩2