ivu06-big

binary set_partitioning

Submitter	Variables	Constraints	Density	Status	Group	Objective	MPS File
S. Weider	2277736	1177	8.62614e-03	open	ivu	140.74*	ivu06-big.mps.gz

Set partitioning instance resulting from a column generation algorithm used for duty scheduling in public transportation Imported from MIPLIB2010.

Location of instance in collection

Instance Statistics

Detailed explanation of the following tables can be found here.

Size Related Properties
	Original	Presolved
Variables	2277736	2277736
Constraints	1177	1177
Binaries	2277736	2277736
Integers	0	0
Continuous	0	0
Implicit Integers	0	0
Fixed Variables	0	0
Nonzero Density	0.00862614	0.00862614
Nonzeroes	23125800	23125800

Constraint Classification Properties
	Original	Presolved
Total	1177	1177
Empty	0	0
Free	0	0
Singleton	0	0
Aggregations	0	0
Precedence	0	0
Variable Bound	0	0
Set Partitioning	1177	1177
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	Submitter	Date	Description
3	140.7437	140.7437	Edward Rothberg	2020-07-30	Obtained with Gurobi 9.0 using the solution improvement heuristic.
2	146.7010		Ed Klotz	2019-08-16
1	168.6410	168.6410	-	2018-10-10	Solution found during MIPLIB2017 problem selection.

Similar instances in collection

The following instances are most similar to ivu06-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
ds-big	open	174997	174997	1042	4623442	Steffen Weider	–	195.43982994*	binary set_partitioning
nw04	easy	87482	87482	36	636666	MIPLIB submission pool	–	16862	benchmark binary benchmark_suitable set_partitioning
eilA101-2	easy	65832	65832	100	959373	J. Linderoth	eil	880.9201079999999	benchmark binary benchmark_suitable set_partitioning
eilC76-2	easy	28599	28599	75	314837	J. Linderoth	eil	762.514781999996	binary benchmark_suitable set_partitioning

Reference

@inproceedings{BorndoerferLoebelWeider2008,
 author = {Ralf Bornd{\"o}rfer and Andreas L{\"o}bel and Steffen
Weider},
 booktitle = {Computer-aided Systems in Public Transport},
 editor = {Mark Hickman and Pitu Mirchandani and Stefan Voß},
 pages = {3--24},
 series = {Lecture Notes in Economics and Mathematical Systems},
 title = {A Bundle Method for Integrated Multi-Depot Vehicle and
Duty Scheduling in Public Transit},
 volume = {600},
 year = {2008}
}

@phdthesis{Weider2007,
 author = {Steffen Weider},
 school = {Technische Universit{\"a}t Berlin},
 title = {Integration of Vehicle and Duty Scheduling in Public
Transport},
 year = {2007}
}