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	1715.0*	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] https://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

Location of instance in collection

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.

Nonzero entries of original problem

Nonzero entries after trivial presolving

Decomposed structure of original problem (dec-file)

Decomposed structure after trivial presolving (dec-file)

	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.

## Warning in lapply(df["exactobjval"], as.numeric): NAs introduced by coercion

ID	Objective	Exact	Submitter	Date	Description
3	1715	1715	Edward Rothberg	2020-07-17	Obtained with the Gurobi 9.0 solution improvement heuristic
2	2120		Ed Klotz	2019-02-27	Found using CPLEX with customized parameters
1	4280		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	easy	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	easy	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"
}