shiftreg5-1

numerics aggregations set_partitioning cardinality equation_knapsack binpacking knapsack mixed_binary

Submitter Variables Constraints Density Status Group Objective MPS File
Domenico Salvagnin 48736 31424 1.02844e-04 open shiftreg 522.1155479894852* shiftreg5-1.mps.gz

Multi-activity shift scheduling problem with 5 activities and 24 employees, using an implicit model based on a regular language.

Instance Statistics

Detailed explanation of the following tables can be found here.

Size Related Properties
Original Presolved
Variables 48736 46048
Constraints 31424 31424
Binaries 10608 7920
Integers 0 0
Continuous 38128 38128
Implicit Integers 0 0
Fixed Variables 2688 0
Nonzero Density 0.000102844 0.000105132
Nonzeroes 157504 152128
Constraint Classification Properties
Original Presolved
Total 31424 31424
Empty 0 0
Free 0 0
Singleton 0 0
Aggregations 11280 12432
Precedence 0 0
Variable Bound 0 0
Set Partitioning 2304 1152
Set Packing 0 0
Set Covering 0 0
Cardinality 24 24
Invariant Knapsack 0 0
Equation Knapsack 24 24
Bin Packing 24 24
Knapsack 24 72
Integer Knapsack 0 0
Mixed Binary 17744 17696
General Linear 0 0
Indicator 0 0

Structure

Available nonzero structure and decomposition information. Further information can be found here.

value min median mean max
Components 3.618362
Constraint % 0.00318 0.0105218 0.00636 0.700102
Variable % 0.00434 0.0116240 0.00651 0.873002
Score 0.435379

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
4 522.1155 522.5230 0e+00 4e-07 0 Edward Rothberg 2020-11-25 Found with Gurobi 9.1 NoRel heuristics
3 522.4711 9e-07 9e-07 0 Edward Rothberg 2019-12-13 Obtained with Gurobi 9.0
2 522.5793 0e+00 0e+00 0 Robert Ashford and Alkis Vazacopoulus 2019-12-18 Found using ODH|CPlex
1 524.1003 524.1003 0e+00 0e+00 0 - 2018-10-13 Solution found during MIPLIB2017 problem selection.

Similar instances in collection

The following instances are most similar to shiftreg5-1 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
shiftreg2-7 hard 11404 4152 0 7252 8540 34900 Domenico Salvagnin shiftreg 230.326187744737 decomposition numerics aggregations set_partitioning cardinality equation_knapsack binpacking knapsack mixed_binary
shiftreg1-4 easy 10008 3912 0 6096 8136 29976 Domenico Salvagnin shiftreg 132.66969396 decomposition numerics aggregations set_partitioning cardinality equation_knapsack binpacking knapsack mixed_binary
ns2122698 open 155103 16447 0 138656 139280 424272 Timo Berthold neos-pseudoapplication-93 68749.99988531263* decomposition aggregations set_partitioning set_packing cardinality mixed_binary general_linear
ns2124243 open 156083 16447 0 139636 139280 429032 Timo Berthold neos-pseudoapplication-93 77460* decomposition aggregations variable_bound set_partitioning cardinality mixed_binary general_linear
binkar10_1 easy 2298 170 0 2128 1026 4496 H. Mittelmann 6742.1998835 benchmark benchmark_suitable aggregations mixed_binary

Reference

@article{CGR11,
    Author = {Marie-Claude C{\^o}t{\'e} and Bernard Gendron and Louis-Martin Rousseau},
    Journal = {Management Science},
    Number = {1},
    Pages = {151--163},
    Title = {Grammar-Based Integer Programming Models for Multiactivity Shift Scheduling},
    Volume = {57},
    Year = {2011}}

@article{CGQR11,
    Author = {Marie-Claude C{\^o}t{\'e} and Bernard Gendron and Claude-Guy Quimper and Louis-Martin Rousseau},
    Journal = {Constraints},
    Number = {1},
    Pages = {54--76},
    Title = {Formal languages for integer programming modeling of shift scheduling problems},
    Volume = {16},
    Year = {2011}}

@article{QuimperRousseau10,
    Author = {Quimper, Claude-Guy and Rousseau, Louis-Martin},
    Journal = {Journal of Heuristics},
    Pages = {373--392},
    Title = {A large neighbourhood search approach to the multi-activity shift scheduling problem},
    Volume = {16},
    Year = {2010}}

@inproceedings{SalvagninWalsh12,
    Author = {Domenico Salvagnin and Toby Walsh},
    Booktitle = {CP},
    Pages = {633--646},
    Title = {A hybrid MIP/CP approach for multi-activity shift scheduling},
    Year = {2012}}

Last Update Mar 04, 2024 by Julian Manns
generated with R Markdown
© 2023 by Zuse Institute Berlin (ZIB)
Imprint