Submitter Variables Constraints Density Status Group Objective MPS File
Domenico Salvagnin 48736 31424 1.02844e-04 open shiftreg 524.100343 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.

ID Objective Exact Int. Viol Cons. Viol Obj. Viol Submitter Date Description
1 524.1003 524.1003 0 0 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 Variables Binaries Integers Continuous Constraints Nonz. Submitter Group Status Objective
shiftreg2-7 11404 4152 0 7252 8540 34900 Domenico Salvagnin shiftreg hard 230.326187744737
shiftreg1-4 10008 3912 0 6096 8136 29976 Domenico Salvagnin shiftreg easy 132.66969396
ns2122698 155103 16447 0 138656 139280 424272 Timo Berthold neos-pseudoapplication-93 open 69250*
ns2124243 156083 16447 0 139636 139280 429032 Timo Berthold neos-pseudoapplication-93 open 77460*
binkar10_1 2298 170 0 2128 1026 4496 H. Mittelmann easy 6742.1998835

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 Nov 17, 2018 by Gregor Hendel
generated with R Markdown
© 2018 by Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)
Imprint