kottenpark09

aggregations precedence variable_bound set_partitioning set_packing set_covering cardinality invariant_knapsack mixed_binary general_linear

Submitter Variables Constraints Density Status Group Objective MPS File
George Fonseca 2893026 325547 1.38939e-05 open timetabling 2120* kottenpark09.mps.gz

Educational timetabling problems from several real schools/universities around the world. These instances were originally expressed in the xhstt file format [1] and formulated as Integer Programming models as described at [2].

[1] http://www.sciencedirect.com/science/article/pii/S0377221717302242 [2] https://link.springer.com/article/10.1007/s10479-011-1012-2

Ed Klotz reports the CPLEX Settings which he used to find the current best known solution: “With these settings, you get sufficiently fast node throughput that the tree search and node heuristics have some chance of success. After about 10 hours with 12 threads (and again 512 GB of RAM, although I don’t think that much was required), you start to get solutions with objectives in the 4000-5000 range, and letting it continue for 10 or more hours you eventually get solutions in the 2000-3000 range. I did not really experiment with alternate parameter settings to improve the tree search; that might help, as well as possibly using the attached solution as an advanced start and kicking off the run with the above settings with that solution immediately available.”

CPLEX Parameter File Version 12.9.0.0 - 12.9.0.0 | 2018-12-12 | a167f58ab5

     CPXPARAM_MIP_Strategy_StartAlgorithm             4
     CPXPARAM_MIP_Strategy_SubAlgorithm               4
     CPXPARAM_MIP_SubMIP_StartAlg                     4
     CPXPARAM_MIP_SubMIP_SubAlg                       4
     CPXPARAM_Barrier_Crossover                       -1
     2208                                             "submip.prm"

And the submip.prm file consists of:

     CPXPARAM_MIP_SubMIP_StartAlg                     4
     CPXPARAM_MIP_SubMIP_SubAlg                       4
     CPXPARAM_Barrier_Crossover                       -1

The undocumented parameter 2208 refers to

     CPLEX set mip submip _paramfile submip.prm
     New value for parameter file for sub-MIPs: submip.prm

Instance Statistics

Detailed explanation of the following tables can be found here.

Size Related Properties
Original Presolved
Variables 2893026 1410175
Constraints 325547 226913
Binaries 2892333 1409482
Integers 693 693
Continuous 0 0
Implicit Integers 0 639
Fixed Variables 0 0
Nonzero Density 1.38939e-05 2.25252e-05
Nonzeroes 13085500 7207770
Constraint Classification Properties
Original Presolved
Total 325547 226913
Empty 2170 0
Free 0 0
Singleton 3193 0
Aggregations 123838 86519
Precedence 13888 12462
Variable Bound 17522 16077
Set Partitioning 128709 87087
Set Packing 10030 8764
Set Covering 1283 1113
Cardinality 10694 5996
Invariant Knapsack 11562 7604
Equation Knapsack 362 0
Bin Packing 0 0
Knapsack 266 0
Integer Knapsack 0 0
Mixed Binary 71 18
General Linear 1959 1273
Indicator 0 0

Structure

Available nonzero structure and decomposition information. Further information can be found here.

value min median mean max
Components
Constraint %
Variable %
Score

Best Known Solution(s)

Find solutions below. Download the archive containing all solutions from the Download page.

ID Objective Exact Int. Viol Cons. Viol Obj. Viol Submitter Date Description
2 2120 0 0 0 Ed Klotz 2019-02-27 “Found using CPLEX with customized parameters”
1 4280 0 0 0 Ed Klotz 2019-01-28 “”

Similar instances in collection

The following instances are most similar to kottenpark09 in the collection. This similarity analysis is based on 100 scaled instance features describing properties of the variables, objective function, bounds, constraints, and right hand sides.

Instance Status Variables Binaries Integers Continuous Constraints Nonz. Submitter Group Objective Tags
satellites4-25 hard 95637 93747 0 1890 51712 821192 He Renjie satellites -25 benchmark_suitable aggregations precedence set_partitioning set_packing cardinality invariant_knapsack knapsack mixed_binary
satellites3-25 hard 81681 79961 0 1720 44804 698176 He Renjie satellites -25 benchmark_suitable aggregations precedence variable_bound set_partitioning set_packing cardinality invariant_knapsack knapsack mixed_binary
satellites2-40 easy 35378 34324 0 1054 20916 283668 He Renjie satellites -19 benchmark benchmark_suitable aggregations precedence variable_bound set_partitioning set_packing cardinality invariant_knapsack knapsack mixed_binary
satellites2-25 easy 35378 34324 0 1054 20916 283668 He Renjie satellites -19 benchmark_suitable aggregations precedence variable_bound set_partitioning set_packing cardinality invariant_knapsack knapsack mixed_binary
piperout-d27 easy 13104 12931 149 24 17470 224457 Gleb Belov piperout 8124 decomposition benchmark_suitable aggregations precedence variable_bound set_partitioning set_packing set_covering invariant_knapsack binpacking knapsack integer_knapsack mixed_binary general_linear

Reference

@article{FONSECA201728,
title = "Integer programming techniques for educational timetabling",
journal = "European Journal of Operational Research",
volume = "262",
number = "1",
pages = "28 - 39",
year = "2017",
note = "",
issn = "0377-2217",
doi = "http://dx.doi.org/10.1016/j.ejor.2017.03.020",
url = "http://www.sciencedirect.com/science/article/pii/S0377221717302242",
author = "George H.G. Fonseca and Haroldo G. Santos and Eduardo G. Carrano and Thomas J.R. Stidsen",
keywords = "Timetabling",
keywords = "Integer Programming",
keywords = "Formulation"
}

Last Update Apr 09, 2019 by Gregor Hendel
generated with R Markdown
© 2019 by Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)
Imprint