Submitter | Variables | Constraints | Density | Status | Group | Objective | MPS File |
---|---|---|---|---|---|---|---|

Domenico Salvagnin | 48736 | 31424 | 1.02844e-04 | open | shiftreg | 522.1155479894853* | shiftreg5-1.mps.gz |

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

Detailed explanation of the following tables can be found here.

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 |

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 |

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

Decomposed structure of original problem (dec-file)

Decomposed structure after trivial presolving (dec-file)

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 |

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

3 | 4 | 522.1155 | 522.5230 | 0e+00 | 4e-07 | 0 | Edward Rothberg | 2020-11-25 | Found with Gurobi 9.1 NoRel heuristics |

1 | 3 | 522.4711 | 9e-07 | 9e-07 | 0 | Edward Rothberg | 2019-12-13 | Obtained with Gurobi 9.0 | |

4 | 2 | 522.5793 | 0e+00 | 0e+00 | 0 | Robert Ashford and Alkis Vazacopoulus | 2019-12-18 | Found using ODH|CPlex | |

2 | 1 | 524.1003 | 524.1003 | 0e+00 | 0e+00 | 0 | - | 2018-10-13 | Solution found during MIPLIB2017 problem selection. |

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 | 68750.0* | 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 |

```
@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 Mai 20, 2021 by Philipp Wellner

generated with R Markdown

© 2020 by Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)

Imprint