In hierarchical clustering, a hierarchy of nested data partitions is obtained. Commonly used agglomerative and divisive heuristics do not optimize over a global objective function. Although several objective functions and approximation algorithms have been proposed, exact methods that find optimal solutions based on these objective functions have received little attention. In this paper, we consider an objective function involving a sum of partitional clustering objectives over each level. We introduce two compact mixed-integer linear programming formulations as well as a set-covering formulation that can handle various objective functions. In addition, we provide a branch-and-price framework to solve the set-covering formulation. We apply our branch-and-price approach to real-world data instances containing up to 200 observations compared with 15 in the literature. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. 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.0903 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0903 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

We study an integrated market selection and production planning problem. There is a set of markets with deterministic demand, and each market has a certain revenue that is obtained if the market’s demand is satisfied throughout a planning horizon. The demand is satisfied with a production scheme that has a lot-sizing structure. The problem is to decide on which markets’ demand to satisfy and plan the production simultaneously. We consider both single and multiobjective settings. The single objective problem maximizes the profit, whereas the multiobjective problem includes the maximization of the revenue and the minimization of the production cost objectives. We develop a decomposition-based exact solution algorithm for the single objective setting and show how it can be used in a proposed three-phase algorithm for the multiobjective setting. The master problem chooses a subset of markets, and the subproblem calculates an optimal production plan to satisfy the selected markets’ demand. We investigate the subproblem from a cooperative game theory perspective to devise cuts and strengthen them based on lifting. We also propose a set of valid inequalities and preprocessing rules to improve the proposed algorithm. We test the efficacy of our solution method over a suite of problem instances and show that our algorithm substantially decreases solution times for all problem instances. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: This work was supported by TUBITAK [Grant 1059B191801782].

We consider a single-item multilevel lot-sizing problem with a serial structure where one of the levels has an inventory capacity (the bottleneck level). We propose a novel dynamic programming algorithm combining Zangwill’s approach for the uncapacitated problem and the basis-path approach for the production capacitated problem. Under reasonable assumptions on the cost parameters the time complexity of the algorithm is [Formula: see text] with L the number of levels in the supply chain and T the length of the planning horizon. Computational tests show that our algorithm is significantly faster than the commercial solver Cplex applied to a standard formulation and can solve reasonably sized instances up to 48 periods and 12 levels in a few minutes. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the National Research Foundation of Korea (NRF) funded by the Ministry of Education [Grant 2014R1A1A2058513].