search

UniTime / cpsolver

Local-search based solver of Constraint Satisfaction and Optimization Problems
http://www.cpsolver.org
GNU Lesser General Public License v3.0
60 stars 35 forks source link

Failed to select a neighbour: ArrayIndexOutOfBoundsException #3

Closed SeriousBug closed 8 years ago

SeriousBug commented 8 years ago

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?

tomas-muller commented 8 years ago

Yes, the first time in the class goes over the midnight and the end of a week: <time breaktime="10" days="0000001" length="60" pref="1" start="229"/> The solver does not expect that and such a situation should be avoided.

Please note that the UniTime user interface does not allow a time placement to go over the midnight as it could create all sorts of issues.

SeriousBug commented 8 years ago

Thanks!