academictimetablebig

binary aggregations precedence variable_bound set_partitioning set_packing set_covering cardinality invariant_knapsack equation_knapsack binpacking knapsack

Submitter	Variables	Constraints	Density	Status	Group	Objective	MPS File
Joshua Friedman	168974	167661	5.45484e-05	hard	–	427	academictimetablebig.mps.gz

Academic timetabling integer program Reported solved after 1 1/2 days using Gurobi.

Location of instance in collection

Instance Statistics

Detailed explanation of the following tables can be found here.

Size Related Properties
	Original	Presolved
Variables	168974	158073
Constraints	167661	153402
Binaries	168974	158073
Integers	0	0
Continuous	0	0
Implicit Integers	0	0
Fixed Variables	0	0
Nonzero Density	5.45484e-05	6.07257e-05
Nonzeroes	1545380	1472520

Constraint Classification Properties
	Original	Presolved
Total	167661	153402
Empty	1762	0
Free	0	0
Singleton	820	0
Aggregations	185	122
Precedence	1601	1583
Variable Bound	48963	43724
Set Partitioning	682	5080
Set Packing	6462	10370
Set Covering	18226	39
Cardinality	5700	1060
Invariant Knapsack	22976	85136
Equation Knapsack	1800	1710
Bin Packing	2664	2565
Knapsack	2060	2013
Integer Knapsack	0	0
Mixed Binary	53760	0
General Linear	0	0
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.

ID	Objective	Exact	Int. Viol	Cons. Viol	Obj. Viol	Submitter	Date	Description
1	427	427	0	0	0	Joshua Friedman	2018-11-09	Found using Gurobi 8.1 on a very fast 16 Xeon core machine for 37 hours

Similar instances in collection

The following instances are most similar to academictimetablebig 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
academictimetablesmall	easy	28926	28926	0	0	23294	268350	Joshua Friedman	–	0	benchmark binary decomposition benchmark_suitable aggregations precedence variable_bound set_partitioning set_packing cardinality invariant_knapsack equation_knapsack binpacking knapsack
neos-5195221-niemur	easy	14546	9792	0	4754	42256	176586	Jeff Linderoth	neos-pseudoapplication-32	0.0038354326	benchmark benchmark_suitable aggregations precedence variable_bound set_partitioning cardinality invariant_knapsack knapsack mixed_binary
neos-5193246-nerang	easy	14546	9792	0	4754	42256	175794	Jeff Linderoth	neos-pseudoapplication-32	0.03821976217279999	benchmark_suitable aggregations precedence variable_bound set_partitioning cardinality invariant_knapsack knapsack mixed_binary
nursesched-medium-hint03	hard	34248	34170	78	0	14062	622800	Haroldo Gambini Santos	nursescheduling	115	benchmark decomposition benchmark_suitable set_partitioning set_packing cardinality invariant_knapsack general_linear
physiciansched3-3	easy	79555	72141	0	7414	266227	1062479	Pelin Damci-Kurt	physiciansched	2623271.326667	benchmark decomposition benchmark_suitable precedence variable_bound set_packing set_covering invariant_knapsack binpacking knapsack mixed_binary

Reference

@article{Friedman16,
  title={Automated timetabling for small colleges and high schools using huge integer programs},
  author={Friedman, Joshua S},
  journal={arXiv preprint arXiv:1612.08777},
  year={2016}
}