unitime / cpsolver

Local-search based solver of Constraint Satisfaction and Optimization Problems

UniTime

Comprehensive University Timetabling System https://www.unitime.org

UniTime is a comprehensive educational scheduling system that supports developing course and exam timetables, managing changes to these timetables, sharing rooms with other events, and scheduling students to individual classes. It is a distributed system that allows multiple university and departmental schedule managers to coordinate efforts to build and modify a schedule that meets their diverse organizational needs while allowing for minimization of student course conflicts. It can be used alone to create and maintain a school's schedule of classes and/or exams, or interfaced with an existing student information system.

The system was originally developed as a collaborative effort by faculty, students, and staff at universities in North America and Europe. The software is distributed free under an open source license in hopes that other colleges and universities can benefit their students through better scheduling or wish to contribute to ongoing research in this area. The UniTime project has become a sponsored project of the Apereo Foundation in March 2015.

Components

• Course Timetabling & Management
• Examination Timetabling
• Event Management
• Student Scheduling

Tutorials

• Installation Instructions
• Building UniTime
• Setting up UniTime in Eclipse
• Customization
• Localization

Links

• UniTime 4.6 documentation
• Online Documentation
• Online Demo
• Downloads
• Nightly Builds
• XML Interfaces
• Publications

cpsolver's Issues

Online class restriction

@tomas-muller,
I had some query regarding the solver report.
In the Instructor solver, I see that there is a perturbation percentage report.
What does the perturbation percentage indicate? How does it affect the solver result?

Continuation of this question :
UniTime/unitime#48 (comment)
I have added a hard constraint of the online classes, but the perturbation percentage went up from 0.34% to 70%.

Additional exam criteria

I would like to open a discussion about an additional exam timetabling/scheduling criterion.

I'm using UniTime for exam scheduling. At our faculty the total examination period is 24 days.
In order to reduce the examination stress for the students the examinations should be more ore less distributed evenly over these 24 days.
Sometimes the solver places the exams in a row. For example if a student is enrolled in 5 exams all the exams take place in one week at 5 consecutive days.

In my opinion it would be helpful to have an exam cirterion like for example "students not more than 3 exams in 5 days".
I started to implement such a criterion and there is a first (not yet tested) draft (what would be the best way to share it?).

Maybe such a criterion is interesting for other UniTime/cpsolver users.

Best regards
Alexander

Constants are hardcoded

Some constants for course timetabling seem to be hardcoded like the start and end slot. I am currently implementing course timetabling on top of cpsolver, but those fixed slot times are forcing me to use my own patched version of cpsolver. Can the fields for the starting and end times be made accessible?

Less constrained timelocations

I'd like to deploy a cpsolver based timetabling at my university. However, timetables are not as constrained as required by cpsolver at my university. In cpsolver if a lecture meets several times a week on different days, the start time is always the same. That's not the case at my university, e.g. a lecture might meet Mondays at 10:00 - 12:00 and Thursdays at 16:00 - 18:00. Is there a way to have this kind of timelocations with cpsolver?

Information about course timetabling

I have a question related to this issue #7 .
Have there been any updates since the closure of this issue or has the logic remained the same?

If I divide a class into several subparts, can I use the same class id several times to use a unique id for the constraints?
Also, if I define a child class to a parent class and use the id of the parent class in the constraints, will the child class be affected by the same constraints?

Thank you in advance.

Deadlock in SearchIntensification

For some reason Searchintensification seems to produce dead locks. It seems all threads get stuck at Solution.restoreBest()

The last output I see in my console is

2018-01-26 11:59:21.701 [Solver-1] DEBUG o.c.i.e.SearchIntensification - Going back to the best known solution...
2018-01-26 11:59:21.873 [Solver-3] DEBUG o.c.i.e.SearchIntensification - Going back to the best known solution...

So it might be several threads trying to restore the solution at a time. I'll try to debug this and provide more information.

Understanding of solver score calculation

@tomas-muller, we are finding difficulty in understanding the logic behind the calculation of the scores involved while assigning a subject to an instructor based on various parameters set in the applications.

Screenshot 1: Solver score of Prof.Eric Kostelish

Screenshot2: Solver score of Prof.Tim Ferguson

With reference to the screenshots above, Prof."Eric Kostelich" has been assigned with this course when he has not set any kind of preferences( Time preference = Neutral, No course preference). Where as prof."Tim Ferguson" has set the MAT-342 as his preferred course and the time preference matches with the time of the class. Yet he's not assigned with this class.
Under the objectives column we are not able to interpret how the values are calculated for entries such as Attribute preferences, same course, teaching preferences and time preferences. Specifically, we want to understand how Prof.Eric Kostelich's attribute preference is -2 and Prof.Tim Ferguson has +2.

Please find the preferences info for both the professors :

Prof.Eric Kostelishs attribute preferences

Prof.Tim Ferguson's attribute preferences

Round Robin prevents from terminating if no neighbour is selected

Hey there,

I have just spend some time to detect why my custom solver didn't terminate. It's probably a good idea to return null, if all registered neighbourSelections fail to find a neighbour or check for terminationCondition. Adding a random selection helps preventing this issue.

Maybe there are other ways to avoid this problem? Probably the most selections will at some point return a valid neighbour.

This is the relating code of RoundRobinNeighbourSelection

public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) {
        while (true) {
            int selectionIndex = getSelectionIndex();
            NeighbourSelection<V, T> selection = iSelections.get(selectionIndex % iSelections.size());
            Neighbour<V, T> neighbour = selection.selectNeighbour(solution);
            if (neighbour != null)
                return neighbour;
            changeSelection(selectionIndex);
        }
    }

Update to Java 8

Java 8 is widely adapted now and should be the default on most machines. Java 8 brings useful features like lambda expressions allowing more precise and shorter code in some situations.

Is there any reason to stay at a language level of 1.6?

University Course Timetabling coursett-1.3.jar execution

Hi,

I was looking for run the solver without using the unitime web application using this page as example https://www.unitime.org/cpsolver_examples.php.

I am interested in University Course Timetabling but I have some questions.

1. Where I can find the coursett-1.3.jar? If I use the cp-solver.1.3.jar the execution returns this error:

Errore: impossibile inizializzare la classe principale org.cpsolver.coursett.Test
Causato da: java.lang.NoClassDefFoundError: org/apache/log4j/Layout

2. Is it possible to use the same jar to solve a CurriculaRequestsCourseDemands or CurriculaLastLikeCourseDemands problems? How can I do that?

Thank you for your attention.

Is there any constraint about week.

hi there!
I wonder if there is a class and it has a course from the first week to the third week and it also has other course from the five week to the nine week.Can CPsolver can solver this problem and how to solve.

Solver MPP mode

Hi everyone,

I would like to know if there is the possibility (using some particular configuration in the cfg file) to build a solution starting from an initial partial solution WITHOUT changing the assignments already done in the input xml.

Thank you

Failed to select a neighbour: ArrayIndexOutOfBoundsException

The following input file causes the error "Failed to select a neighbour: ArrayIndexOutOfBoundsException". The solver still produces a solution, but constantly throws this error while trying to improve the solution.

<?xml version='1.0' encoding='UTF-8'?>

<timetable created="2016-07-11" initiative="173500" nrDays="7" slotsPerDay="288" term="2016foo" version="2.4">
  <rooms>
    <room capacity="55" constraint="true" id="1" location="39.9048053575,32.820756607">
      <sharing>
        <department id="1234" value="F"/>
        <pattern unit="6">000000000000000000000000FFFF001111111111111100000000000000000000000000111111111111110000000000000000000000000000000000000000000011110000000000000000000000000000000000FFFFFFFFFF00FFFFFFFF000000000000000000000000000000000000000000111100000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111110000</pattern>
        <freeForAll value="1"/>
        <notAvailable value="0"/>
      </sharing>
    </room>
  </rooms>
  <classes>
    <class classLimit="49" config="10" dates="1111111111111111111111111111" id="100" offering="1000" scheduler="1234" subpart="111">
      <room id="1" pref="0"/>
      <time breaktime="10" days="0000001" length="60" pref="1" start="229"/>
      <time breaktime="10" days="1000000" length="60" pref="2" start="186"/>
    </class>
  </classes>
  <groupConstraints/>
  <students/>
</timetable>

The jar being ran is cpsolver-1.3.79.jar, it is run with the command java -Xmx1g -jar cpsolver-1.3.79.jar great-deluge.cfg 124150.xml OUTPUT.

The configuration file that is being used is the great deluge configuration.

The output:

Output folder: OUTPUT/160712_135209

Reading 124150.xml ...      : [main] [Restoring from backup ...]

Creating rooms ...          : ................................................
Creating variables ...      : ................................................
Creating constraints ...    : 
Loading students ...        : 
Initial sectioning ...      : 
Computing jenrl ...         : 
Purging invalid placements .: ................................................
Creating initial assignment : 
Done                        : ................................................[main] Model successfully loaded.
[SolverSync] [Solving problem ...]

Initializing solver         : [SolverSync] Using org.cpsolver.ifs.termination.MPPTerminationCondition
[SolverSync] Using org.cpsolver.coursett.heuristics.TimetableComparator
[SolverSync] Using org.cpsolver.ifs.algorithms.SimpleSearch
[SolverSync] Using org.cpsolver.coursett.heuristics.PlacementSelection
[SolverSync] Using org.cpsolver.coursett.heuristics.LectureSelection
[SolverSync] Using org.cpsolver.coursett.heuristics.PlacementSelection
[SolverSync] Using org.cpsolver.coursett.heuristics.LectureSelection
[SolverSync] Using org.cpsolver.coursett.heuristics.UniversalPerturbationsCounter
[SolverSync] Using org.cpsolver.ifs.extension.ConflictStatistics

Searching for initial soluti: [SolverSync] Initial solution:[
      Assigned variables: 0.00% (0/1)
      Distribution preferences: 100.00% (0.00)
      Iteration: 0
      Memory usage: 8.83M
      Overall solution value: 0.00
      Room preferences: 100.00% (0)
      Same subpart balancing penalty: 0.00
      Student conflicts: 0 [committed:0, distance:0, hard:0]
      Time: 0.00 min
      Time preferences: 100.00% (0.00)
      Too big rooms: 0.00% (0)
      Useless half-hours: 0.00% (0 + 0)
    ]
[SolverSync] **BEST[0]** V:0/1, T:0.00
[Solver-1] Using wall time.
[Solver-1] [Solver-1] Construction...
[Solver-2] [Solver-2] Construction...
[Solver-3] [Solver-3] Construction...
[Solver-4] [Solver-4] Construction...
[Solver-1] **BEST[1]** T:0.30, TP:0%
[Solver-1] [Solver-1] IFS...
[Solver-1] [Solver-1] Hill Climber...
[Solver-2] **BEST[1]** T:0.30, TP:0%
[Solver-2] [Solver-2] IFS...
[Solver-2] [Solver-2] Hill Climber...
[Solver-3] **BEST[1]** T:0.30, TP:0%
[Solver-3] [Solver-3] IFS...
[Solver-3] [Solver-3] Hill Climber...
[Solver-4] **BEST[1]** T:0.30, TP:0%
[Solver-4] [Solver-4] IFS...
[Solver-4] [Solver-4] Hill Climber...
[Solver-4] Failed to select a neighbour: 2016
[Solver-3] Failed to select a neighbour: 2016
< snipped... >
[Solver-1] Failed to select a neighbour: 2016
[Solver-4] Failed to select a neighbour: 2016
[Solver-1] Failed to select a neighbour: 2016
[Solver-3] Failed to select a neighbour: ArrayIndexOutOfBoundsException
[Solver-2] Failed to select a neighbour: ArrayIndexOutOfBoundsException
[Solver-4] Failed to select a neighbour: ArrayIndexOutOfBoundsException
< snipped... >
[Solver-1] Failed to select a neighbour: ArrayIndexOutOfBoundsException
[Solver-1] Failed to select a neighbour: ArrayIndexOutOfBoundsException
[Solver-2] Failed to select a neighbour: ArrayIndexOutOfBoundsException
[Solver-4] Failed to select a neighbour: ArrayIndexOutOfBoundsException

Improving found solution ...: 
Done                        : ................................................[SolverSync] [Solver stopped.]
[ShutdownHook] Last solution: [
    Assigned variables: 0.00% (0/1)
    Best Iteration: 1
    Best Time: 0.00 min (2209.77 it/s)
    Distribution preferences: 100.00% (0.00)
    Iteration: 24219
    Memory usage: 15.64M
    Overall solution value: 0.00
    Room preferences: 100.00% (0)
    Same subpart balancing penalty: 0.00
    Speed: 33804.13 it/s
    Student conflicts: 0 [committed:0, distance:0, hard:0]
    Time: 0.01 min
    Time preferences: 100.00% (0.00)
    Too big rooms: 0.00% (0)
    Useless half-hours: 0.00% (0 + 0)
  ]
[ShutdownHook] Best solution (before restore): [
    Assigned variables: 100.00% (1/1)
    Distribution preferences: 100.00% (0.00)
    Iteration: 1
    Memory usage: 15.13M
    Overall solution value: 0.30
    Room preferences: 100.00% (0)
    Same subpart balancing penalty: 0.00
    Speed: 2209.77 it/s
    Student conflicts: 0 [committed:0, distance:0, hard:0]
    Time: 0.00 min
    Time preferences: 0.00% (1.00)
    Too big rooms: 0.00% (0)
    Useless half-hours: 0.00% (0 + 0)
  ]
[ShutdownHook] Best solution: [
    Assigned variables: 100.00% (1/1)
    Best Iteration: 1
    Best Time: 0.00 min (2209.77 it/s)
    Distribution preferences: 100.00% (0.00)
    Iteration: 24219
    Memory usage: 15.64M
    Overall solution value: 0.30
    Room preferences: 100.00% (0)
    Same subpart balancing penalty: 0.00
    Speed: 33804.13 it/s
    Student conflicts: 0 [committed:0, distance:0, hard:0]
    Time: 0.01 min
    Time preferences: 0.00% (1.00)
    Too big rooms: 0.00% (0)
    Useless half-hours: 0.00% (0 + 0)
  ]
[ShutdownHook] [Student Sectioning...]

moving students ...         : ................................................[ShutdownHook] Best solution: [
    Assigned variables: 100.00% (1/1)
    Best Iteration: 1
    Best Time: 0.00 min (2209.77 it/s)
    Distribution preferences: 100.00% (0.00)
    Iteration: 24219
    Memory usage: 15.64M
    Overall solution value: 0.30
    Room preferences: 100.00% (0)
    Same subpart balancing penalty: 0.00
    Speed: 33804.13 it/s
    Student conflicts: 0 [committed:0, distance:0, hard:0]
    Time: 0.01 min
    Time preferences: 0.00% (1.00)
    Too big rooms: 0.00% (0)
    Useless half-hours: 0.00% (0 + 0)
  ]
[ShutdownHook] Total number of done iteration steps:24219
[ShutdownHook] Achieved speed: 33804.135 iterations/second
Unassigned variables: 0

The problem seems to be caused by the line <time breaktime="10" days="0000001" length="60" pref="1" start="229"/>. Taking out this line, changing the day to anything other than '0000001' or setting the start to something lower than '229' solves the issue.

Are the errors caused by a problem in the input file?