Total Coloring and Total Matching: Polyhedra and Facets
Author
Abstract
Suggested Citation
DOI: 10.1016/j.ejor.2022.02.025
Download full text from publisher
As the access to this document is restricted, you may want to search for a different version of it.
References listed on IDEAS
- San Segundo, Pablo & Coniglio, Stefano & Furini, Fabio & Ljubić, Ivana, 2019. "A new branch-and-bound algorithm for the maximum edge-weighted clique problem," European Journal of Operational Research, Elsevier, vol. 278(1), pages 76-90.
- Lü, Zhipeng & Hao, Jin-Kao, 2010. "A memetic algorithm for graph coloring," European Journal of Operational Research, Elsevier, vol. 203(1), pages 241-250, May.
- Stefano Gualandi & Federico Malucelli, 2012. "Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation," INFORMS Journal on Computing, INFORMS, vol. 24(1), pages 81-100, February.
- Januario, Tiago & Urrutia, Sebastián & Ribeiro, Celso C. & de Werra, Dominique, 2016. "Edge coloring: A natural model for sports scheduling," European Journal of Operational Research, Elsevier, vol. 254(1), pages 1-8.
- Demange, Marc & Ekim, Tınaz & Ries, Bernard & Tanasescu, Cerasela, 2015. "On some applications of the selective graph coloring problem," European Journal of Operational Research, Elsevier, vol. 240(2), pages 307-314.
- Steffen Rebennack & Marcus Oswald & Dirk Oliver Theis & Hanna Seitz & Gerhard Reinelt & Panos M. Pardalos, 2011. "A Branch and Cut solver for the maximum stable set problem," Journal of Combinatorial Optimization, Springer, vol. 21(4), pages 434-457, May.
- Stefano Gualandi & Federico Malucelli, 2013. "Constraint Programming-based Column Generation," Annals of Operations Research, Springer, vol. 204(1), pages 11-32, April.
- Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
- Anuj Mehrotra & Michael A. Trick, 1996. "A Column Generation Approach for Graph Coloring," INFORMS Journal on Computing, INFORMS, vol. 8(4), pages 344-354, November.
- Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
- Jon Lee & Janny Leung & Sven Vries, 2005. "Separating Type-I Odd-Cycle Inequalities for a Binary-Encoded Edge-Coloring Formulation," Journal of Combinatorial Optimization, Springer, vol. 9(1), pages 59-67, February.
Most related items
These are the items that most often cite the same works as this one and are cited by the same works as this one.- Timo Gschwind & Stefan Irnich, 2014. "Dual Inequalities for Stabilized Column Generation Revisited," Working Papers 1407, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz, revised 23 Jul 2014.
- Stefano Gualandi & Federico Malucelli, 2013. "Constraint Programming-based Column Generation," Annals of Operations Research, Springer, vol. 204(1), pages 11-32, April.
- Timo Gschwind & Stefan Irnich, 2016. "Dual Inequalities for Stabilized Column Generation Revisited," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 175-194, February.
- Shen, Yunzhuang & Sun, Yuan & Li, Xiaodong & Eberhard, Andrew & Ernst, Andreas, 2023. "Adaptive solution prediction for combinatorial optimization," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1392-1408.
- Jans, Raf, 2010. "Classification of Dantzig-Wolfe reformulations for binary mixed integer programming problems," European Journal of Operational Research, Elsevier, vol. 204(2), pages 251-254, July.
- David R. Morrison & Jason J. Sauppe & Edward C. Sewell & Sheldon H. Jacobson, 2014. "A Wide Branching Strategy for the Graph Coloring Problem," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 704-717, November.
- Túlio A. M. Toffolo & Jan Christiaens & Frits C. R. Spieksma & Greet Vanden Berghe, 2019. "The sport teams grouping problem," Annals of Operations Research, Springer, vol. 275(1), pages 223-243, April.
- David R. Morrison & Edward C. Sewell & Sheldon H. Jacobson, 2016. "Solving the Pricing Problem in a Branch-and-Price Algorithm for Graph Coloring Using Zero-Suppressed Binary Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 67-82, February.
- De Boeck, Liesje & Beliën, Jeroen & Creemers, Stefan, 2016. "A column generation approach for solving the examination-timetabling problemAuthor-Name: Woumans, Gert," European Journal of Operational Research, Elsevier, vol. 253(1), pages 178-194.
- Alex Gliesch & Marcus Ritt, 2022. "A new heuristic for finding verifiable k-vertex-critical subgraphs," Journal of Heuristics, Springer, vol. 28(1), pages 61-91, February.
- Raf Jans, 2009. "Solving Lot-Sizing Problems on Parallel Identical Machines Using Symmetry-Breaking Constraints," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 123-136, February.
- Isabel Martins & Filipe Alvelos & Miguel Constantino, 2012. "A branch-and-price approach for harvest scheduling subject to maximum area restrictions," Computational Optimization and Applications, Springer, vol. 51(1), pages 363-385, January.
- Rönnberg, Elina & Larsson, Torbjörn, 2014. "All-integer column generation for set partitioning: Basic principles and extensions," European Journal of Operational Research, Elsevier, vol. 233(3), pages 529-538.
- Eliashberg, Jehoshua & Hegie, Quintus & Ho, Jason & Huisman, Dennis & Miller, Steven J. & Swami, Sanjeev & Weinberg, Charles B. & Wierenga, Berend, 2009. "Demand-driven scheduling of movies in a multiplex," International Journal of Research in Marketing, Elsevier, vol. 26(2), pages 75-88.
- Markus Frey & Rainer Kolisch & Christian Artigues, 2017. "Column Generation for Outbound Baggage Handling at Airports," Transportation Science, INFORMS, vol. 51(4), pages 1226-1241, November.
- de Lima, Vinícius L. & Alves, Cláudio & Clautiaux, François & Iori, Manuel & Valério de Carvalho, José M., 2022. "Arc flow formulations based on dynamic programming: Theoretical foundations and applications," European Journal of Operational Research, Elsevier, vol. 296(1), pages 3-21.
- Stefano Gualandi & Federico Malucelli, 2012. "Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation," INFORMS Journal on Computing, INFORMS, vol. 24(1), pages 81-100, February.
- Omid Shahvari & Rasaratnam Logendran & Madjid Tavana, 2022. "An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems," Journal of Scheduling, Springer, vol. 25(5), pages 589-621, October.
- Melanie Erhard, 2021. "Flexible staffing of physicians with column generation," Flexible Services and Manufacturing Journal, Springer, vol. 33(1), pages 212-252, March.
- Hadi W. Purnomo & Jonathan F. Bard, 2007. "Cyclic preference scheduling for nurses using branch and price," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(2), pages 200-220, March.
More about this item
Keywords
Integer Programming; Combinatorial Optimization; Total Coloring; Total Matching;All these keywords.
Statistics
Access and download statisticsCorrections
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:303:y:2022:i:1:p:129-142. See general information about how to correct material in RePEc.
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .
Please note that corrections may take a couple of weeks to filter through the various RePEc services.