This paper introduces an ℓ1-norm model based on Total Variation Minimization for tomographic reconstruction. The reconstructions produced by the proposed model are more accurate than those obtained with classical reconstruction models based on the ℓ2-norm. This model can be linearized and solved by linear programming techniques. Furthermore, the complementary slackness conditions can be exploited to reduce the dimension of the resulting formulation by removing unnecessary variables and constraints. Since the efficacy of the reduced formulation strongly depends on the quality of the dual-multipliers used when applying the reduction method, Lagrangian relaxation is used to obtain near-optimal multipliers. This allows solving larger instances in an efficient way.

This paper introduces the hub location problem under interhub link failures, a hub location problem in which activated interhub links may fail with a given probability. Two different optimization models are studied, which construct hub backbone networks protected under interhub link disruptions by imposing that, for each commodity, an additional routing path exists besides its original routing path. Both models consider the minimization of the fixed costs of the activated hubs and interhub links plus the expected value of the routing costs of the original and alternative paths. The first model builds explicitly the alternative routing paths, whereas the second model guarantees that, for each commodity, at least one alternative path exists using a large set of connectivity constraints although the alternative paths are not built explicitly. The results of extensive computational testing allow us to analyze the performance of the two proposed models and to evaluate the extra cost required to design a robust backbone network under interhub link failures. The obtained results support the validity of the proposal. History: Accepted by David Alderson, Area Editor for Network Optimization: Algorithms & Application. Funding: The authors of this research acknowledge financial support by the Spanish Ministerio de Ciencia y Tecnología, Agencia Estatal de Investigación and Fondos Europeos de Desarrollo Regional (FEDER) via projects PID2020-114594GB-C21 and MTM2019-105824GB-I00. The authors also acknowledge partial support from projects FEDER-US-1256951, Junta de Andalucía P18-FR-422, P18-FR-2369, B-FQM-322-UGR20 (COXMOS), and NetmeetData: Ayudas Fundación BBVA a equipos de investigación científica 2019. The first author was partially supported by the IMAG-Maria de Maeztu grant [CEX2020-001105-M/AEI/10.13039/501100011033] and UE-NextGenerationEU (ayudas de movilidad para la recualificación del profesorado universitario). Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2023.1296 .

Abstract This article deals with the problem of partitioning a graph into connected components by optimizing some balancing objective functions related to the vertex weights. Objective functions based on the gap or range of the partition's components, that is, the difference between the maximum and minimum weight of a vertex in the component, have been already introduced in the literature. Here we introduce the notion of aggregated gap, defined as the sum of the differences between the weights of the vertices and the minimum weight of a vertex in the component. We study new connected ‐partitioning problems whose objective is a function of the components' aggregated gap, and give NP‐hardness results for these problems on general graphs. Mathematical programming formulations are proposed for these problems adopting flow‐based constraints for modeling connectivity in a partition. Even if they are introduced for the new aggregated gap problems, such formulations are rather general and apply also to the classical non‐aggregated gap problems. Extensive computational tests, both for aggregated and non‐aggregated gap problems, are performed on a set of squared grids and randomly generated graphs with up to 120 vertices, and a number of components ranging from 2 to 9. In our experiments, we test several alternative formulations for our problems providing a comparative analysis of their performance.

In this paper, a heuristic procedure is proposed for the facility location problem with general Bernoulli demands. This is a discrete facility location problem with stochastic demands that can be formulated as a two-stage stochastic program with recourse. In particular, facility locations and customer assignments must be decided here and now, i.e., before knowing the customers who will actually require to be served. In a second stage, service decisions are made according to the actual requests. The heuristic proposed consists of a greedy randomized adaptive search procedure followed by a path relinking. The heterogeneous Bernoulli demands make prohibitive the computational effort for evaluating feasible solutions. Thus the expected cost of a feasible solution is simulated when necessary. The results of extensive computational tests performed for evaluating the quality of the heuristic are reported, showing that high-quality feasible solutions can be obtained for the problem in fairly small computational times. The online supplement is available at https://doi.org/10.1287/ijoc.2017.0755 .

This paper presents a branch-and-price algorithm for the capacitated hub location problem with single assignment, in which Lagrangean relaxation is used to obtain tight lower bounds of the restricted master problem. A lower bound that is valid at any stage of the column generation algorithm is proposed. The process to obtain this valid lower bound is combined with a constrained stabilization method that results in a considerable improvement on the overall efficiency of the solution algorithm. Numerical results on a battery of benchmark instances of up to 200 nodes are reported. These seem to be the largest instances that have been solved to optimality for this problem.