This paper considers a cooperative routing problem in which trucks and multiple drones serve a set of customers collaboratively. A truck can operate as a drone station, dispatching and collecting multiple drones for nearby customers to overcome the drone’s short operation range. Each customer has a time window, so either a truck or a drone must serve the customer within the time window. The travel time uncertainties of the truck and drone are addressed by adopting the robust optimization approach. We first present a compact mathematical formulation for the problem. Then, we develop a decomposition approach based on the branch-and-price framework. After defining extended variables for trucks and drones separately, we decompose the column generation subproblem into two optimization problems, resulting in a two-phase column generation algorithm. We also develop a heuristic algorithm based on the proposed column generation scheme for larger instances. The results of numerical experiments, including real-life benchmark instances, show that the proposed algorithm outperforms the state-of-the-art mixed-integer programming solver. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: Financial support from the Basic Science Research Program through the National Research Foundation of Korea funded by the Ministry of Science, ICT & Future Planning [Grant NRF-2021R1F1A1 048540] is gratefully acknowledged. C. Lee was supported by the Hankuk University of Foreign Studies Research Fund. 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.2023.0484 ), as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0484 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

The Benders decomposition algorithm often shows poor convergence. To improve the convergence of the Benders decomposition algorithm. Recently, it was proposed the use of feasibility cuts closest to a solution in the set defined by all feasibility cuts. We extend this feasibility cut selection scheme to a new cut selection scheme for optimality cuts and propose a new Benders separation framework that a single linear programming problem can solve. We show that optimality cuts generated by this scheme are Pareto optimal when some conditions are satisfied. Theoretical connections to the existing Benders cut generation methods are also identified. Extensive computational experiments on the multiple classes of benchmark problems demonstrate that the proposed algorithm improves the convergence speed and computational time. Summary of Contribution: The Benders decomposition algorithm is one of the most widely used algorithms in operations research. However, the Benders decomposition algorithm often shows poor convergence for some optimization problems. In this paper, to improve the convergence of the Benders decomposition algorithm, we propose a unified closest Benders cut generation scheme. We give theoretical properties of the proposed Benders cuts, including Pareto optimality and facet-defining conditions. Also, we conducted extensive computational tests on various instances, such as network design and expansion problems. The results show the effectiveness of the closest Benders cut compared with existing algorithms and Cplex.

The link prediction problem is an emerging real-life social network problem in which data mining techniques have played a critical role. It arises in many practical applications such as recommender systems, information retrieval, and marketing analysis of social networks. We propose a new mathematical programming approach for predicting a future network using estimated node degree distribution identified from historical data. The link prediction problem is formulated as an integer programming problem that maximizes the sum of link scores (probabilities) with respect to the estimated node degree distribution. The performance of the proposed framework is tested on real-life social networks, and the computational results show that the proposed approach can improve the performance of previously published link prediction methods.

The bandwidth packing problem (BWP) concerns the selection of calls from a given set and the assignment of one path to each selected call. The ultimate aim of the BWP is to maximize profit while the routings of the selected calls observe the capacity constraints of the links. Here, we additionally consider queueing delays in the network, which may cause a deterioration in the quality of service to users if they exceed the acceptable limits. The integer programming formulation for the BWP with the queueing delay restriction contains a nonlinear constraint that is intrinsic to the model. We apply the Dantzig-Wolfe decomposition to this nonlinear constraint, and since the Dantzig-Wolfe decomposition has exponentially many variables, we propose the branch-and-price procedure to find optimal solutions. We also propose a generalized Dantzig-Wolfe reformulation based on the aggregation of variables, which makes our branch-and-price algorithm more competitive. Computational results on cases of randomly generated networks and some real-life telecommunication networks demonstrate that our algorithm performs well for large networks.

Abstract We consider a network design problem in which flow bifurcations are allowed. The demand data are assumed to be uncertain, and the uncertainties of demands are expressed by an uncertainty set. The goal is to install facilities on the edges at minimum cost. The solution should be able to deliver any of the demand requirements defined in the uncertainty set. We propose an exact solution algorithm based on a decomposition approach in which the problem is decomposed into two distinct problems: (1) designing edge capacities; and (2) checking the feasibility of the designed edge capacities with respect to the uncertain demand requirements. The algorithm is a special case of the Benders decomposition method. We show that the robust version of the Benders subproblem can be formulated as a linear program whose size is polynomially bounded. We also propose a simultaneous cut generation scheme to accelerate convergence of the Benders decomposition algorithm. Computational results on real‐life telecommunication problems are reported, and these demonstrate that robust solutions with very small penalties in the objective values can be obtained. © 2012 Wiley Periodicals, Inc. Networks, 2013.