ds-big

binary set_partitioning

Submitter	Variables	Constraints	Density	Status	Group	Objective	MPS File
Steffen Weider	174997	1042	2.53552e-02	open	–	195.498997075249*	ds-big.mps.gz

Bus driver duty scheduling problem Imported from MIPLIB2010. Solution was computed with 12 Threads in 12 hours, using the approach of giving highest priority to the variables with the most edges in the conflic graph

Location of instance in collection

Instance Statistics

Detailed explanation of the following tables can be found here.

Size Related Properties
	Original	Presolved
Variables	174997	174997
Constraints	1042	1042
Binaries	174997	174997
Integers	0	0
Continuous	0	0
Implicit Integers	0	0
Fixed Variables	0	0
Nonzero Density	0.0253552	0.0253552
Nonzeroes	4623440	4623440

Constraint Classification Properties
	Original	Presolved
Total	1042	1042
Empty	0	0
Free	0	0
Singleton	0	0
Aggregations	0	0
Precedence	0	0
Variable Bound	0	0
Set Partitioning	1042	1042
Set Packing	0	0
Set Covering	0	0
Cardinality	0	0
Invariant Knapsack	0	0
Equation Knapsack	0	0
Bin Packing	0	0
Knapsack	0	0
Integer Knapsack	0	0
Mixed Binary	0	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	0.30103
Constraint %		100	100	100	100
Variable %		100	100	100	100
Score	0.00000

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	Int. Viol	Cons. Viol	Submitter	Date	Description
4	195.4990		1.1e-06	1e-06	Edward Rothberg	2019-12-13	Obtained with Gurobi 9.0
3	228.1898		0.0e+00	0e+00	Robert Ashford and Alkis Vazacopoulus	2019-12-18	Found using ODH\|CPlex
2	247.9167		0.0e+00	0e+00	Ed Klotz	2019-08-21	Computed with 12 Threads in 12 hours, using the approach of giving highest priority to the variables with the most edges in the conflic graph.
1	325.0937	325.0937	0.0e+00	0e+00	-	2018-10-12	Solution found during MIPLIB2017 problem selection.

Similar instances in collection

The following instances are most similar to ds-big 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	Constraints	Nonz.	Submitter	Group	Objective	Tags
ivu06	open	787239	787239	1177	8032303	S. Weider	ivu	142.86*	binary set_partitioning
nw04	easy	87482	87482	36	636666	MIPLIB submission pool	–	16862	benchmark binary benchmark_suitable set_partitioning
ivu06-big	open	2277736	2277736	1177	23125770	S. Weider	ivu	140.74*	binary set_partitioning
ds	hard	67732	67732	656	1024059	MIPLIB submission pool	–	93.52	binary set_partitioning
eilC76-2	easy	28599	28599	75	314837	J. Linderoth	eil	762.514781999996	binary benchmark_suitable set_partitioning

Reference

@incollection{GroetschelBorndoerferLoebel2003,
 author = {Martin Gr{\"o}tschel and Ralf Bornd{\"o}rfer and Andreas L{\"o}bel},
 booktitle = {{MATHEMATICS} -- {K}ey {T}echnology for the {F}uture},
 editor = {Willi J{\"a}ger and Hans-Joachim Krebs},
 language = {English},
 pages = {653--674},
 publisher = {Springer-Verlag},
 title = {Duty Scheduling in Public Transit},
 year = {2003}
}