Search

This paper presents an effective perturbation-based thresholding search for two popular and challenging packing problems with minimal containers: packing N identical circles in a square and packing N identical spheres in a cube. Following the penalty function approach, we handle these constrained optimization problems by solving a series of unconstrained optimization subproblems with fixed containers. The proposed algorithm relies on a two-phase search strategy that combines a thresholding search method reinforced by two general-purpose perturbation operators and a container adjustment method. The performance of the algorithm is assessed relative to a large number of benchmark instances widely studied in the literature. Computational results show a high performance of the algorithm on both problems compared with the state-of-the-art results. For circle packing, the algorithm improves 156 best-known results (new upper bounds) in the range of 2 ≤ N ≤ 400 and matches 242 other best-known results. For sphere packing, the algorithm improves 66 best-known results in the range of 2 ≤ N ≤ 200 , whereas matching the best-known results for 124 other instances. Experimental analyses are conducted to shed light on the main search ingredients of the proposed algorithm consisting of the two-phase search strategy, the mixed perturbation and the parameters. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by the National Natural Science Foundation of China [Grants 61703213 and 61933005]. 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.1290) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0004) at (http://dx.doi.org/10.5281/zenodo.7579558). [ABSTRACT FROM AUTHOR]

For an unbalanced cooperative game, its grand coalition can be stabilized by some instruments, such as subsidization and penalization, that impose new cost terms to certain coalitions. In this paper, we study an alternative instrument, referred to as cost adjustment, that does not need to impose any new coalition-specific cost terms. Specifically, our approach is to adjust existing cost coefficients of the game under which (i) the game becomes balanced so that the grand coalition becomes stable, (ii) a desired way of cooperation is optimal for the grand coalition to adopt, and (iii) the total cost to be shared by the grand coalition is within a prescribed range. Focusing on a broad class of cooperative games, known as integer minimization games, we formulate the problem on how to optimize the cost adjustment as a constrained inverse optimization problem. We prove NP -hardness and derive easy-to-check feasibility conditions for the problem. Based on two linear programming reformulations, we develop two solution algorithms. One is a cutting-plane algorithm, which runs in polynomial time when the corresponding separation problem is polynomial time solvable. The other needs to explicitly derive all the inequalities of a linear program, which runs in polynomial time when the linear program contains only a polynomial number of inequalities. We apply our models and solution algorithms to two typical unbalanced games, including a weighted matching game and an uncapacitated facility location game, showing that their optimal cost adjustments can be obtained in polynomial time. History: Accepted by Area Editor Andrea Lodi for Design & Analysis of Algorithms—Discrete. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72022018 and 72091210]; the Research Grants Council of the Hong Kong SAR, China [Grant 16210020]; Hong Kong Polytechnic University [Grant P0032007]; and the Youth Innovation Promotion Association, Chinese Academy of Sciences [Grant 2021454]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.0268. [ABSTRACT FROM AUTHOR]

We study adjustable distributionally robust optimization problems, where their ambiguity sets can potentially encompass an infinite number of expectation constraints. Although such ambiguity sets have great modeling flexibility in characterizing uncertain probability distributions, the corresponding adjustable problems remain computationally intractable and challenging. To overcome this issue, we propose a greedy improvement procedure that consists of solving, via the (extended) linear decision rule approximation, a sequence of tractable subproblems—each of which considers a relaxed and finitely constrained ambiguity set that can be iteratively tightened to the infinitely constrained one. Through three numerical studies of adjustable distributionally robust optimization models, we show that our approach can yield improved solutions in a systematic way for both two-stage and multistage problems. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: Financial support by the Early Career Scheme from the Hong Kong Research Grants Council [Project No. CityU 21502820], the CityU Start-Up Grant [Project No. 9610481], the CityU Strategic Research Grant [Project No. 7005688], the National Natural Science Foundation of China [Project No. 72032005], and Chow Sang Sang Group Research Fund sponsored by Chow Sang Sang Holdings International Limited [Project No. 9229076] is gratefully acknowledged. 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.2021.0181), as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0181). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]