{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,10]],"date-time":"2024-04-10T09:09:19Z","timestamp":1712740159821},"reference-count":40,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["INFORMS Journal on Computing"],"published-print":{"date-parts":[[2016,2]]},"abstract":" Branch-and-price algorithms combine a branch-and-bound search with an exponentially sized LP formulation that must be solved via column generation. Unfortunately, the standard branching rules used in branch and bound for integer programming interfere with the structure of the column generation routine; therefore, most such algorithms employ alternate branching rules to circumvent this difficulty. This paper shows how a zero-suppressed binary decision diagram can be used to solve the pricing problem in a branch-and-price algorithm for the graph coloring problem, even in the presence of constraints imposed by branching decisions. This approach facilitates a much more direct solution method and can improve convergence of the column generation subroutine. <\/jats:p>","DOI":"10.1287\/ijoc.2015.0667","type":"journal-article","created":{"date-parts":[[2016,1,26]],"date-time":"2016-01-26T14:52:08Z","timestamp":1453819928000},"page":"67-82","source":"Crossref","is-referenced-by-count":20,"title":["Solving the Pricing Problem in a Branch-and-Price Algorithm for Graph Coloring Using Zero-Suppressed Binary Decision Diagrams"],"prefix":"10.1287","volume":"28","author":[{"given":"David R.","family":"Morrison","sequence":"first","affiliation":[{"name":"Inverse Limit, The Woodlands, Texas 77381"}]},{"given":"Edward C.","family":"Sewell","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, Southern Illinois University, Edwardsville, Illinois 62026"}]},{"given":"Sheldon H.","family":"Jacobson","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois, Urbana\u2013Champaign, Urbana, Illinois 61801"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1978.1675141"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1287\/opre.48.2.318.12378"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1287\/opre.46.3.316"},{"key":"B5","unstructured":"Behle M (2007) Binary decision diagrams and integer programming. Ph.D. thesis, Universist\u00e4t des Saarlands, Saarbrucken, Germany."},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972870.15"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29828-8_3"},{"key":"B9","volume-title":"Introduction to Linear Optimization","author":"Bertsimas D","year":"1997"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1109\/12.537122"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1986.1676819"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1145\/136035.136043"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1287\/opre.8.1.101"},{"key":"B15","first-page":"56","volume-title":"Math. Program Rio: A Conf. Honour Nelson Maculan","author":"de Arag\u00e3o MP","year":"2003"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0644-x"},{"key":"B17","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey MR","year":"1979"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1100.0436"},{"key":"B20","first-page":"607","volume-title":"Proc. 14th Internat. Joint Conf. Artificial Intelligence","volume":"1","author":"Harvey WD","year":"1995"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-012-0042-3"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/026"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-008-0087-3"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(85)90084-0"},{"key":"B26","first-page":"286","volume-title":"Association for the Advancement of Artificial Intelligence\/Innovative Applications of Artificial Intelligence","volume":"1","author":"Korf RE","year":"1996"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1959.tb01585.x"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-009-0108-x"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1070.0245"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.07.005"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.8.4.344"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.05.022"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1145\/157485.164890"},{"key":"B34","unstructured":"Morrison DR (2014) New methods for branch-and-bound algorithms. Ph.D. thesis, University of Illinois, Urbana\u2013Champaign."},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2013.11.033"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-014-9722-4"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2014.0593"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-77778-8_14"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1060.0181"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1287\/opre.45.6.831"},{"key":"B41","volume-title":"Algorithms","author":"Sedgewick R","year":"2011"},{"key":"B42","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-011-9793-z"},{"key":"B44","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0043-y"},{"key":"B45","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018346107246"},{"key":"B46","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0334-1"}],"container-title":["INFORMS Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/ijoc.2015.0667","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T13:53:45Z","timestamp":1680443625000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/ijoc.2015.0667"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,2]]}},"alternative-id":["10.1287\/ijoc.2015.0667"],"URL":"https:\/\/doi.org\/10.1287\/ijoc.2015.0667","relation":{},"ISSN":["1091-9856","1526-5528"],"issn-type":[{"value":"1091-9856","type":"print"},{"value":"1526-5528","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2]]}}}