The minimum sum coloring problem (MSCP), a well-known NP-hard (nondeterministic polynomial time) problem with important practical applications, has been the subject of several papers in recent years. Because of the computational challenge posed by these problems, most solution methods employed are metaheuristics designed to find high-quality solutions with no guarantee of optimality. Exact methods (like Gurobi) and metaheuristic solvers have greatly improved in recent years, enabling high-quality and often optimal solutions to be found to a growing set of MSCPs. Alternative model forms can have a significant impact on the success of exact and heuristic methods in such settings, often providing enhanced performance compared with traditional model forms. In this paper, we introduce several alternative models for MSCP, including the quadratic unconstrained binary problem plus (QUBO-Plus) model for solving problems with constraints that are not folded into the objective function of the basic quadratic unconstrained binary problem (QUBO) model. We provide a computational study using a standard set of test problems from the literature that compares the general purpose exact solver from Gurobi with the leading QUBO metaheuristic solver NGQ and a special solver called Q-Card that belongs to the QUBO-Plus class. Our results highlight the effectiveness of the QUBO and QUBO-Plus models when solved with these metaheuristic solvers on this test bed, showing that the QUBO-Plus solver Q-Card provides the best performance for finding high-quality solutions to these important problems. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0334 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0334 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Abstract We propose a new algorithm for fixed‐charge network flow problems based on ghost image (GI) processes as proposed in Glover (1994) and adapted to fixed‐charge transportation problems in Glover et al. (2005). Our GI algorithm iteratively modifies an idealized representation of the problem embodied in a parametric GI, enabling all steps to be performed with a primal network flow algorithm operating on the parametric GI. Computational testing is carried out on well‐known problems from the literature plus a new set of large‐scale fixed‐charge transportation and transshipment network instances. We also provide comparisons against CPLEX 12.8 and demonstrate that the new GI algorithm with tabu search (TS) is effective on large problem instances, finding solutions with statistically equivalent objective values at least 700 times faster. The attractive outcomes produced by the current GI/TS implementation provide a significant advance in our ability to solve fixed‐cost network problems efficiently and invites its use for larger instances from a variety of application domains.

article Free Access Share on Sensitivity Analysis Procedures for Geometric Programs: Computational Aspects Authors: J. J. Dinkel Department of Management Science and Organizational Behavior, The Pennsylvania State University, 609 Business Administration Building, University Park, PA Department of Management Science and Organizational Behavior, The Pennsylvania State University, 609 Business Administration Building, University Park, PAView Profile , Mary S. Kochenberger Department of Management Science and Organizational Behavior, The Pennsylvania State University, 609 Business Administration Building, University Park, PA Department of Management Science and Organizational Behavior, The Pennsylvania State University, 609 Business Administration Building, University Park, PAView Profile , S. N. Wong Department of Management Science and Organizational Behavior, The Pennsylvania State University, 609 Business Administration Building, University Park, PA Department of Management Science and Organizational Behavior, The Pennsylvania State University, 609 Business Administration Building, University Park, PAView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 4Issue 1March 1978 pp 1–14https://doi.org/10.1145/355769.355770Published:01 March 1978Publication History 17citation487DownloadsMetricsTotal Citations17Total Downloads487Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF