Decision-making processes involving fixed charges arise in various real-world applications and can often be modeled as mixed-integer nonlinear programs (MINLPs) with semicontinuous variables. Perspective reformulation, a technique leveraging perspective functions, offers tight formulations for such MINLPs. In this article, we address the challenge of solving such reformulations by introducing perspective Benders cuts, a family of generalized Benders optimality cuts, and compare them with the classic generalized Benders cuts and the perspective cuts. We focus on their applications to two fixed-charge nonlinear resource allocation problems: a generalized sensor placement problem and a generalized uncapacitated facility location problem. The original quadratic allocation cost functions in these problems are extended to a class of reducible convex functions. By leveraging the reducible property of nonlinear resource allocation problems, we develop an ad-hoc procedure of solving the reduced quadratic subproblems to efficiently separate perspective Benders cuts. These features contribute to a highly efficient branch-and-Benders-cut approach, as demonstrated through extensive computational experiments on various sets of benchmark instances. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Funding: K. Yang acknowledges financial support from China Scholarship Council [Grant 202406110031]. This work was also supported by the National Science Fund for Outstanding Young Scholars [Grant 62122093], the National Natural Science Foundation of China [Grants 72101264, 72431011, and 72421002], the Science and Technology Innovation Program of Hunan Province [Grant 2023RC3008], Open Project of Xiangjiang Laboratory [Grant 22XJ02003], and the University Fundamental Research Fund [Grant 23-ZZCX-JDZ-28]. H. Yang’s work is funded by National Natural Science Foundation of China [Grant 72201232 and 72231008], Guangdong Provincial Key Laboratory of Mathematical Foundations for Artificial Intelligence [Grant 2023B1212010001], and Shenzhen Key Laboratory of Crowd Intelligence Empowered Low-Carbon Energy Network [Grant ZDSYS20220606100601002]. 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.2024.0984 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0984 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Recent years have witnessed a surge of interest in solving combinatorial optimization problems (COPs) using machine learning techniques. Motivated by this trend, we propose a learning-augmented exact approach for tackling an NP-hard COP, the Orienteering Problem with Time Windows, which aims to maximize the total score collected by visiting a subset of vertices in a graph within their time windows. Traditional exact algorithms rely heavily on domain expertise and meticulous design, making it hard to achieve further improvements. By leveraging deep learning models to learn effective relaxations of problem restrictions from data, our approach enables significant performance gains in an exact dynamic programming algorithm. We propose a novel graph convolutional network that predicts the directed edges defining the relaxation. The network is trained in a supervised manner, using optimal solutions as high-quality labels. Experimental results demonstrate that the proposed learning-augmented algorithm outperforms the state-of-the-art exact algorithm, achieving a 38% speedup on Solomon’s benchmark and more than a sevenfold improvement on the more challenging Cordeau’s benchmark.

We study parallel machine scheduling for makespan minimization with uncertain job processing times. To incorporate uncertainty and generate solutions that are, in some way, insensitive to unfolding information, three different modeling paradigms are adopted: a robust model, a chance-constrained model, and a distributionally robust chance-constrained model. We focus on devising generic solution methods that can efficiently handle these different models. We develop two general solution procedures: a cutting-plane method that leverages the submodularity in the models and a customized dichotomic search procedure with a decision version of a bin packing variant under uncertainty solved in each iteration. A branch-and-price algorithm is designed to solve the bin packing problems. The efficiency of our methods is shown through extensive computational tests. We compare the solutions from the different models and report the general lessons learned regarding the choice between different frameworks for planning under uncertainty. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72101264 and 71801218] and the Science and Technology Innovation Team in Higher Educational Institutions of Hunan Province [Grant 2020RC4046]. Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2022.1229 .

The scheduling of agile Earth observation satellites is to select a subset of candidate targets each associated with a profit during their visible time windows in order to maximize the collected profits, under some operational constraints. For each pair of two consecutive observations, a transition time is required to perform a rotating movement of the camera, depending on the start times of the two observations. This time-dependency significantly increases the complexity of the scheduling problem. To solve this problem efficiently, we model the time-dependent transition time and prove that it satisfies the first-in–first-out rule and the triangle inequalities rule. On this basis, we develop a novel hybrid heuristic, called “greedy randomized iterated local search” (GRILS). A specific insert operator, including a fast feasibility check and an assignment procedure are specifically designed to address the operational constraints of the scheduling. Extensive experiments on the single satellite instances and multisatellite instances demonstrate that our algorithm outperforms the state-of-the-art algorithms with respect to solution quality and computation time.

We study the resource loading problem, which arises in tactical capacity planning. In this problem, one has to plan the intensity of execution of a set of orders to minimize a cost function that penalizes the resource use above given capacity limits and the completion of the orders after their due dates. Our main contributions include a novel mixed-integer linear-programming (MIP)‐based formulation, the investigation of the polyhedra associated with the feasible intensity assignments of individual orders, and a comparison of our branch-and-cut algorithm based on the novel formulation and the related polyhedral results with other MIP formulations. The computational results demonstrate the superiority of our approach. In our formulation and in one of the proofs, we use fundamental results of Egon Balas on disjunctive programming.