{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:41:14Z","timestamp":1760060474207,"version":"build-2065373602"},"reference-count":40,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2025,8,28]],"date-time":"2025-08-28T00:00:00Z","timestamp":1756339200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Natural Science Foundation of China","award":["72342014","72371176","KJQN202500657"],"award-info":[{"award-number":["72342014","72371176","KJQN202500657"]}]},{"name":"Science and Technology Research Program of Chongqing Municipal Education Commission","award":["72342014","72371176","KJQN202500657"],"award-info":[{"award-number":["72342014","72371176","KJQN202500657"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems"],"abstract":"<jats:p>The nurse rostering problem (NRP) has attracted significant research interest in recent decades due to both its practical relevance and computational complexity. While the branch-and-price algorithm has demonstrated effectiveness in solving NRPs, its column generation component frequently produces weak lower bounds for some problem instances, which consequently degrades overall computational performance. To strengthen the lower bound quality, we propose three classes of cutting planes derived from the column generation master problem formulation: SRCs, CG rank-1 cuts, and {0, \u00bd}-cuts. For each cut type, the separation approaches enhanced with acceleration strategies are described. These cuts are typically classified as non-robust, meaning each cut added to the master problem requires introducing a new resource in the pricing subproblem\u2019s labeling algorithm. We therefore developed problem-specific methods to update these resources and integrate them into the NRP dominance rules. Computational experiments were conducted on benchmark instances from two international nurse rostering competitions (INRC-I and INRC-II). The results indicate that SRCs are highly effective for two challenging INRC-I instances, including one where a tighter lower bound was identified. In contrast, the {0, \u00bd}-cuts yield the strongest performance for most selected INRC-II instances. These findings demonstrate that the cutting plane method can be used to improve lower bounds for NRPs, and that the effectiveness of different cut types in improving lower bounds is closely tied to the problem formulation.<\/jats:p>","DOI":"10.3390\/systems13090745","type":"journal-article","created":{"date-parts":[[2025,8,28]],"date-time":"2025-08-28T15:03:14Z","timestamp":1756393394000},"page":"745","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Chv\u00e1tal\u2013Gomory Cuts Applied to the Nurse Rostering Problem"],"prefix":"10.3390","volume":"13","author":[{"given":"Yuanyuan","family":"Fang","sequence":"first","affiliation":[{"name":"School of Economics and Management, Chongqing University of Posts and Telecommunications, Chongqing 400065, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wanzhe","family":"Hu","sequence":"additional","affiliation":[{"name":"School of Economics and Management, Chongqing University of Posts and Telecommunications, Chongqing 400065, China"},{"name":"Business School, Sichuan University, Chengdu 610064, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Li","family":"Luo","sequence":"additional","affiliation":[{"name":"Business School, Sichuan University, Chengdu 610064, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,8,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1007\/s10732-008-9099-6","article-title":"A shift sequence based approach for nurse scheduling and a new benchmark dataset","volume":"16","author":"Brucker","year":"2010","journal-title":"J. Heuristics"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1016\/j.ejor.2010.11.017","article-title":"Personnel scheduling: Models and complexity","volume":"210","author":"Brucker","year":"2011","journal-title":"Eur. J. Oper. Res."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.ejor.2015.08.025","article-title":"Polynomially solvable personnel rostering problems","volume":"249","author":"Smet","year":"2016","journal-title":"Eur. J. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1023\/B:JOSH.0000046076.75950.0b","article-title":"The state of the art of nurse rostering","volume":"7","author":"Burke","year":"2004","journal-title":"J. Sched."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1016\/S0377-2217(03)00021-3","article-title":"Nurse rostering problems\u2014A bibliographic survey","volume":"151","author":"Cheang","year":"2003","journal-title":"Eur. J. Oper. Res."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"56504","DOI":"10.1109\/ACCESS.2022.3177280","article-title":"A survey of the nurse rostering solution methodologies: The state-of-the-art and emerging trends","volume":"10","author":"Ngoo","year":"2022","journal-title":"IEEE Access"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/s10479-020-03527-6","article-title":"Solving the static INRC-II nurse rostering problem by simulated annealing based on large neighborhoods","volume":"288","author":"Ceschia","year":"2020","journal-title":"Ann. Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"101547","DOI":"10.1016\/j.swevo.2024.101547","article-title":"Multi-agent deep Q-network-based metaheuristic algorithm for Nurse Rostering Problem","volume":"87","author":"Zhang","year":"2024","journal-title":"Swarm Evol. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"741","DOI":"10.1007\/s10472-021-09727-5","article-title":"A survey on the applications of variable neighborhood search algorithm in healthcare management","volume":"89","author":"Lan","year":"2021","journal-title":"Ann. Math. Artif. Intell."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/s10479-012-1062-0","article-title":"The first international nurse rostering competition 2010","volume":"218","author":"Haspeslagh","year":"2014","journal-title":"Ann. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/s10479-018-2816-0","article-title":"The second international nurse rostering competition","volume":"274","author":"Ceschia","year":"2019","journal-title":"Ann. Oper. Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2011.07.037","article-title":"Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints","volume":"218","author":"Baldacci","year":"2012","journal-title":"Eur. J. Oper. Res."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1057\/jors.2012.70","article-title":"A branch-and-price algorithm for the two-stage guillotine cutting stock problem","volume":"64","author":"Mrad","year":"2013","journal-title":"J. Oper. Res. Soc."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0377-2217(97)00330-5","article-title":"A generalized linear programming model for nurse scheduling","volume":"107","author":"Jaumard","year":"1998","journal-title":"Eur. J. Oper. Res."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/j.ejor.2014.01.039","article-title":"New approaches to nurse rostering benchmark instances","volume":"237","author":"Burke","year":"2014","journal-title":"Eur. J. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1002\/nav.20201","article-title":"Cyclic preference scheduling for nurses using branch and price","volume":"54","author":"Purnomo","year":"2007","journal-title":"Nav. Res. Logist. (NRL)"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"105597","DOI":"10.1016\/j.cor.2021.105597","article-title":"A column generation-based algorithm for midterm nurse scheduling with specialized constraints, preference considerations, and overtime","volume":"138","author":"Guo","year":"2022","journal-title":"Comput. Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"3331","DOI":"10.1016\/j.cor.2012.04.018","article-title":"A constraint programming based column generation approach to nurse rostering problems","volume":"39","author":"He","year":"2012","journal-title":"Comput. Oper. Res."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1016\/j.ejor.2003.06.046","article-title":"Preference scheduling for nurses using column generation","volume":"164","author":"Bard","year":"2005","journal-title":"Eur. J. Oper. Res."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"104945","DOI":"10.1016\/j.cor.2020.104945","article-title":"First-order linear programming in a column generation-based heuristic approach to the nurse rostering problem","volume":"120","author":"Strandmark","year":"2020","journal-title":"Comput. Oper. Res."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1108","DOI":"10.1287\/ijoc.2023.0019","article-title":"A dedicated pricing algorithm to solve a large family of nurse scheduling problems with branch-and-price","volume":"36","author":"Legrain","year":"2024","journal-title":"INFORMS J. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"110629","DOI":"10.1016\/j.cie.2024.110629","article-title":"A branch-and-price approach for the nurse rostering problem with multiple units","volume":"198","author":"Hu","year":"2024","journal-title":"Comput. Ind. Eng."},{"key":"ref_23","unstructured":"de Aragao, M.P., and Uchoa, E. (2003, January 9\u201312). Integer program reformulation for robust branch-and-cut-and-price algorithms. Proceedings of the Mathematical Programming: Conference Honour Nelson Maculan, Buzios, Brazil."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1007\/s10107-005-0644-x","article-title":"Robust branch-and-cut-and-price for the capacitated vehicle routing problem","volume":"106","author":"Fukasawa","year":"2006","journal-title":"Math. Program."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1287\/opre.1070.0449","article-title":"Subset-row inequalities applied to the vehicle-routing problem with time windows","volume":"56","author":"Jepsen","year":"2008","journal-title":"Oper. Res."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1007\/s10107-020-01523-z","article-title":"A generic exact solver for vehicle routing and related problems","volume":"183","author":"Pessoa","year":"2020","journal-title":"Math. Program."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1002\/net.20471","article-title":"Cutting planes for branch-and-price algorithms","volume":"58","author":"Desaulniers","year":"2011","journal-title":"Networks"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/s10479-014-1594-6","article-title":"Integer programming techniques for the nurse rostering problem","volume":"239","author":"Santos","year":"2016","journal-title":"Ann. Oper. Res."},{"key":"ref_29","unstructured":"Petersen, B., Pisinger, D., and Spoorendonk, S. (2008). Chv\u00e1tal-Gomory rank-1 cuts used in a Dantzig-Wolfe decomposition of the vehicle routing problem with time windows. The Vehicle Routing Problem: Latest Advances and New Challenges, Springer."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/BF02592196","article-title":"{0, 1\/2}-Chv\u00e1tal-Gomory cuts","volume":"74","author":"Caprara","year":"1996","journal-title":"Math. Program."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1016\/j.orl.2017.02.006","article-title":"Limited memory rank-1 cuts for vehicle routing problems","volume":"45","author":"Pecin","year":"2017","journal-title":"Oper. Res. Lett."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"106869","DOI":"10.1016\/j.cor.2024.106869","article-title":"A branch-cut-and-price approach for the two-echelon vehicle routing problem with drones","volume":"173","author":"Lichau","year":"2025","journal-title":"Comput. Oper. Res."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0012-365X(73)90167-2","article-title":"Edmonds polytopes and a hierarchy of combinatorial problems","volume":"4","year":"1973","journal-title":"Discret. Math."},{"key":"ref_34","first-page":"291","article-title":"On cutting planes","volume":"79","author":"Schrijver","year":"1980","journal-title":"Combinatorics"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/s004930050057","article-title":"NOTE\u2013On the Membership Problem for the Elementary Closure of a Polyhedron","volume":"19","author":"Eisenbrand","year":"1999","journal-title":"Combinatorica"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"913","DOI":"10.1137\/04061831X","article-title":"Mod-2 cuts generation yields the convex hull of bounded integer feasible sets","volume":"20","author":"Gentile","year":"2006","journal-title":"SIAM J. Discret. Math."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1287\/ijoc.1050.0162","article-title":"Embedding {0, 1\/2}-Cuts in a Branch-and-Cut Framework: A Computational Study","volume":"19","author":"Andreello","year":"2007","journal-title":"INFORMS J. Comput."},{"key":"ref_38","unstructured":"Deza, A., Khalil, E.B., Fan, Z., Zhou, Z., and Zhang, Y. (March, January 25). Learn2Aggregate: Supervised generation of Chvatal-Gomory cuts using graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, Philadelphia, PA, USA."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0167-6377(96)00007-7","article-title":"Gomory cuts revisited","volume":"19","author":"Balas","year":"1996","journal-title":"Oper. Res. Lett."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Deza, A., and Khalil, E.B. (2023). Machine learning for cutting planes in integer programming: A survey. arXiv.","DOI":"10.24963\/ijcai.2023\/739"}],"container-title":["Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-8954\/13\/9\/745\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T18:34:32Z","timestamp":1760034872000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-8954\/13\/9\/745"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,28]]},"references-count":40,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2025,9]]}},"alternative-id":["systems13090745"],"URL":"https:\/\/doi.org\/10.3390\/systems13090745","relation":{},"ISSN":["2079-8954"],"issn-type":[{"type":"electronic","value":"2079-8954"}],"subject":[],"published":{"date-parts":[[2025,8,28]]}}}