Submitter Variables Constraints Density Status Group Objective MPS File
Domenico Salvagnin 10008 8136 3.68142e-04 easy shiftreg 132.66969396 shiftreg1-4.mps.gz

Multi-activity shift scheduling problem with 1 activity and 12 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 10008 8376
Constraints 8136 8136
Binaries 3912 2280
Integers 0 0
Continuous 6096 6096
Implicit Integers 0 0
Fixed Variables 1632 0
Nonzero Density 0.000368142 0.000391975
Nonzeroes 29976 26712
Constraint Classification Properties
Original Presolved
Total 8136 8136
Empty 0 0
Free 0 0
Singleton 0 0
Aggregations 4248 4968
Precedence 0 0
Variable Bound 0 0
Set Partitioning 1152 432
Set Packing 0 0
Set Covering 0 0
Cardinality 12 12
Invariant Knapsack 0 0
Equation Knapsack 12 12
Bin Packing 12 12
Knapsack 12 36
Integer Knapsack 0 0
Mixed Binary 2688 2664
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 1.113943
Constraint % 8.27188 8.27188 8.27188 8.27188
Variable % 8.26170 8.26170 8.26170 8.26170
Score 0.910618

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 132.6697 132.6697 0 0 0 - 2018-10-12 Solution found during MIPLIB2017 problem selection.

Similar instances in collection

The following instances are most similar to shiftreg1-4 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
shiftreg5-1 48736 10608 0 38128 31424 157504 Domenico Salvagnin shiftreg open 524.100343*
ns2122698 155103 16447 0 138656 139280 424272 Timo Berthold neos-pseudoapplication-93 open 69250*
neos-1396125 1161 129 0 1032 1494 5511 NEOS Server Submission neos-pseudoapplication-96 easy 3000.0453373
ns2124243 156083 16447 0 139636 139280 429032 Timo Berthold neos-pseudoapplication-93 open 77460*

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