ivu52

binary set_partitioning invariant_knapsack knapsack mixed_binary

Submitter	Variables	Constraints	Density	Status	Group	Objective	MPS File
S. Weider	157591	2116	6.53589e-03	hard	ivu	481.0068	ivu52.mps.gz

Set partitioning instance resulting from a column generation algorithm used for duty scheduling in public transportation. Solved in June 2014 using CPLEX 12.6 with 48 threads in about 25 days. 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	157591	157591
Constraints	2116	2116
Binaries	157591	157591
Integers	0	0
Continuous	0	0
Implicit Integers	0	0
Fixed Variables	0	0
Nonzero Density	0.00653589	0.00653589
Nonzeroes	2179480	2179480

Constraint Classification Properties
	Original	Presolved
Total	2116	2116
Empty	0	0
Free	0	0
Singleton	0	0
Aggregations	0	0
Precedence	0	0
Variable Bound	0	0
Set Partitioning	2110	2110
Set Packing	0	0
Set Covering	0	0
Cardinality	0	0
Invariant Knapsack	1	1
Equation Knapsack	0	0
Bin Packing	0	0
Knapsack	1	3
Integer Knapsack	0	0
Mixed Binary	4	2
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.301030
Constraint %		0.047259	0.047259	0.047259	0.047259
Variable %		0.324257	0.324257	0.324257	0.324257
Score	0.000471

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	Obj. Viol	Submitter	Date	Description
1	481.3141		2e-07	2e-07	0	-	2018-10-12	Solution found during MIPLIB2017 problem selection.

Similar instances in collection

The following instances are most similar to ivu52 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
square37	easy	49320	49284	36	0	33150	9475672	Sascha Kurz	square	14.9999997973	benchmark_suitable set_partitioning general_linear
square31	easy	28860	28830	30	0	19435	3937200	Sascha Kurz	square	15	benchmark_suitable set_partitioning general_linear
square41	easy	62234	62197	37	0	40160	13566426	Sascha Kurz	square	15	benchmark benchmark_suitable set_partitioning general_linear
rvb-sub	hard	33765	33763	0	2	225	984143	S. Weider	–	16.08499802	binary set_partitioning knapsack
square23	easy	11660	11638	22	0	7887	898813	Sascha Kurz	square	13	benchmark_suitable set_partitioning general_linear

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}
}