Learning to Reduce State-Expanded Networks for Multi-activity Shift Scheduling

Römer M (2021)
In: Integration of Constraint Programming, Artificial Intelligence, and Operations Research. 18th International Conference, CPAIOR 2021, Vienna, Austria, July 5–8, 2021, Proceedings. Stuckey PJ (Ed); Lecture Notes in Computer Science, 12735. Cham: Springer International Publishing: 383-391.

Sammelwerksbeitrag | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Herausgeber*in
Stuckey, Peter J.
Abstract / Bemerkung
For personnel scheduling problems, mixed-integer linear programming formulations based on state-expanded networks in which nodes correspond to rule-related states often have very strong LP relaxations. A challenge of these formulations is that they typically give rise to large model instances. If one is willing to trade in optimality for computation time, a way to reduce the size of the model instances is to heuristically remove unpromising nodes and arcs from the state-expanded networks. In this paper, we propose to employ machine learning models for guiding the reduction of state-expanded networks for multi-activity shift scheduling problems. More specifically, we train a model that predicts the flow through a node from its state attributes, and based on this prediction, we decide whether to keep a node or not. In experiments with a well-known set of multi-activity shift scheduling instances, we show that our approach substantially reduces both the size of the model instances and their solution times while still obtaining optimal solutions for the vast majority of the instances. The results indicate that our approach is competitive with a state-of-the art Lagrangian-relaxation-based matheuristic for multi-activity shift scheduling problems.
Erscheinungsjahr
2021
Buchtitel
Integration of Constraint Programming, Artificial Intelligence, and Operations Research. 18th International Conference, CPAIOR 2021, Vienna, Austria, July 5–8, 2021, Proceedings
Serientitel
Lecture Notes in Computer Science
Band
12735
Seite(n)
383-391
ISBN
978-3-030-78229-0
eISBN
978-3-030-78230-6
ISSN
0302-9743
eISSN
1611-3349
Page URI
https://pub.uni-bielefeld.de/record/2958571

Zitieren

Römer M. Learning to Reduce State-Expanded Networks for Multi-activity Shift Scheduling. In: Stuckey PJ, ed. Integration of Constraint Programming, Artificial Intelligence, and Operations Research. 18th International Conference, CPAIOR 2021, Vienna, Austria, July 5–8, 2021, Proceedings. Lecture Notes in Computer Science. Vol 12735. Cham: Springer International Publishing; 2021: 383-391.
Römer, M. (2021). Learning to Reduce State-Expanded Networks for Multi-activity Shift Scheduling. In P. J. Stuckey (Ed.), Lecture Notes in Computer Science: Vol. 12735. Integration of Constraint Programming, Artificial Intelligence, and Operations Research. 18th International Conference, CPAIOR 2021, Vienna, Austria, July 5–8, 2021, Proceedings (pp. 383-391). Cham: Springer International Publishing. https://doi.org/10.1007/978-3-030-78230-6_24
Römer, M. (2021). “Learning to Reduce State-Expanded Networks for Multi-activity Shift Scheduling” in Integration of Constraint Programming, Artificial Intelligence, and Operations Research. 18th International Conference, CPAIOR 2021, Vienna, Austria, July 5–8, 2021, Proceedings, Stuckey, P. J. ed. Lecture Notes in Computer Science, vol. 12735, (Cham: Springer International Publishing), 383-391.
Römer, M., 2021. Learning to Reduce State-Expanded Networks for Multi-activity Shift Scheduling. In P. J. Stuckey, ed. Integration of Constraint Programming, Artificial Intelligence, and Operations Research. 18th International Conference, CPAIOR 2021, Vienna, Austria, July 5–8, 2021, Proceedings. Lecture Notes in Computer Science. no.12735 Cham: Springer International Publishing, pp. 383-391.
M. Römer, “Learning to Reduce State-Expanded Networks for Multi-activity Shift Scheduling”, Integration of Constraint Programming, Artificial Intelligence, and Operations Research. 18th International Conference, CPAIOR 2021, Vienna, Austria, July 5–8, 2021, Proceedings, P.J. Stuckey, ed., Lecture Notes in Computer Science, vol. 12735, Cham: Springer International Publishing, 2021, pp.383-391.
Römer, M.: Learning to Reduce State-Expanded Networks for Multi-activity Shift Scheduling. In: Stuckey, P.J. (ed.) Integration of Constraint Programming, Artificial Intelligence, and Operations Research. 18th International Conference, CPAIOR 2021, Vienna, Austria, July 5–8, 2021, Proceedings. Lecture Notes in Computer Science. 12735, p. 383-391. Springer International Publishing, Cham (2021).
Römer, Michael. “Learning to Reduce State-Expanded Networks for Multi-activity Shift Scheduling”. Integration of Constraint Programming, Artificial Intelligence, and Operations Research. 18th International Conference, CPAIOR 2021, Vienna, Austria, July 5–8, 2021, Proceedings. Ed. Peter J. Stuckey. Cham: Springer International Publishing, 2021.Vol. 12735. Lecture Notes in Computer Science. 383-391.

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Suchen in

Google Scholar
ISBN Suche