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/ .

We present a new flow-based formulation for identical parallel machine scheduling with a regular objective function and without idle time. The formulation is constructed with the help of a decision diagram that represents all job sequences that respect specific ordering rules. These rules rely on a partition of the planning horizon into, generally nonuniform, periods and do not exclude all optimal solutions, but they constrain solutions to adhere to a canonical form. The new formulation has numerous variables and constraints, and hence we apply a Dantzig-Wolfe decomposition to compute the linear programming relaxation in reasonable time; the resulting lower bound is stronger than the bound from the classical time-indexed formulation. We develop a branch-and-price framework that solves three instances from the literature for the first time. We compare the new formulation with the time-indexed and arc time–indexed formulation by means of a series of computational experiments. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This work was partially funded by the European Union’s Horizon 2020 research and innovation program under [Marie Skłodowska-Curie Grant 754462]. 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.0301 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0301 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Suppose a target is hidden in one of the vertices of an edge-weighted graph according to a known probability distribution. Starting from a fixed root node, an expanding search visits the vertices sequentially until it finds the target, where the next vertex can be reached from any of the previously visited vertices. That is, the time to reach the next vertex equals the shortest-path distance from the set of all previously visited vertices. The expanding search problem then asks for a sequence of the nodes, so as to minimize the expected time to finding the target. This problem has numerous applications, such as searching for hidden explosives, mining coal, and disaster relief. In this paper, we develop exact algorithms and heuristics, including a branch-and-cut procedure, a greedy algorithm with a constant-factor approximation guarantee, and a local search procedure based on a spanning-tree neighborhood. Computational experiments show that our branch-and-cut procedure outperforms existing methods for instances with nonuniform probability distributions and that both our heuristics compute near-optimal solutions with little computational effort. Summary of Contribution: This paper studies new algorithms for the expanding search problem, which asks to search a graph for a target hidden in one of the nodes according to a known probability distribution. This problem has applications such as searching for hidden explosives, mining coal, and disaster relief. We propose several new algorithms, including a branch-and-cut procedure, a greedy algorithm, and a local search procedure; and we analyze their performance both experimentally and theoretically. Our analysis shows that the algorithms improve on the performance of existing methods and establishes the first constant-factor approximation guarantee for this problem.

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 .

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.

We study the parallel machine scheduling problem to minimize the sum of the weighted completion times of the jobs to be scheduled (problem Pm∥∑wj Cj in the standard three-field notation). We use the set covering formulation that was introduced by van den Akker et al. [van den Akker J, Hoogeveen J, van de Velde S (1999) Parallel machine scheduling by column generation. Oper. Res. 47(6):862–872.] for this problem, and we improve the computational performance of their branch-and-price (B&P) algorithm by a number of techniques, including a different generic branching scheme, zero-suppressed binary decision diagrams (ZDDs) to solve the pricing problem, dual-price smoothing as a stabilization method, and Farkas pricing to handle infeasibilities. We report computational results that show the effectiveness of the algorithmic enhancements, which depends on the characteristics of the instances. To the best of our knowledge, we are also the first to use ZDDs to solve the pricing problem in a B&P algorithm for a scheduling problem. The online supplement is available at https://doi.org/10.1287/ijoc.2018.0809 .

We consider the problem of deciding whether a given directed graph can be vertex partitioned into two acyclic subgraphs. Applications of this problem include testing rationality of collective consumption behavior, a subject in microeconomics. We prove that the problem is NP-complete even for oriented graphs and argue that the existence of a constant-factor approximation algorithm is unlikely for an optimization version that maximizes the number of vertices that can be colored using two colors while avoiding monochromatic cycles. We present three exact algorithms—namely, an integer-programming algorithm based on cycle identification, a backtracking algorithm, and a branch-and-check algorithm. We compare these three algorithms both on real-life instances and on randomly generated graphs. We find that for the latter set of graphs, every algorithm solves instances of considerable size within a few seconds; however, the CPU time of the integer-programming algorithm increases with the number of vertices in the graph more clearly than the CPU time of the two other procedures. For real-life instances, the integer-programming algorithm solves the largest instance in about a half hour, whereas the branch-and-check algorithm takes approximately 10 minutes and the backtracking algorithm less than 5 minutes. Finally, for every algorithm, we also study empirically the transition from a high to a low probability of a YES answer as a function of the number of arcs divided by the number of vertices.

Abstract This article investigates the relationship between resource allocation and early‐start policies (ES‐policies), which are a type of scheduling policies introduced for stochastic scheduling and which can be represented by a directed acyclic graph. We present a formal treatment of resource flows as a representation of resource‐allocation decisions, extending the existing literature. Our results lead to suggestions for efficiency enhancements to enumeration algorithms for ES‐policies. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 58(1), 50–58 2011

Abstract This article examines the complexity of resource‐allocation decisions for resource‐constrained project scheduling. The allocation decisions are modeled by means of precedence networks and are closely related to ES‐policies, which are a type of scheduling policies introduced for stochastic scheduling. We find that even a number of ‘surrogate’ objective functions, whose use has recently been proposed by multiple sources, lead to hard problems. Our results confirm that resource allocation is difficult even when objective‐function evaluation by itself is not intractable. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 58(1), 59–67 2011