Search

In this paper, we introduce a mixed integer quadratic formulation for the congested variant of the partial set covering location problem, which involves determining a subset of facility locations to open and efficiently allocating customers to these facilities to minimize the combined costs of facility opening and congestion while ensuring target coverage. To enhance the resilience of the solution against demand fluctuations, we address the case under uncertain customer demand using $\Gamma$-robustness. We formulate the deterministic problem and its robust counterpart as mixed-integer quadratic problems. We investigate the effect of the protection level in adapted instances from the literature to provide critical insights into how sensitive the planning is to the protection level. Moreover, since the size of the robust counterpart grows with the number of customers, which could be significant in real-world contexts, we propose the use of Benders decomposition to effectively reduce the number of variables by projecting out of the master problem all the variables dependent on the number of customers. We illustrate how to incorporate our Benders approach within a mixed-integer second-order cone programming (MISOCP) solver, addressing explicitly all the ingredients that are instrumental for its success. We discuss single-tree and multi-tree approaches and introduce a perturbation technique to deal with the degeneracy of the Benders subproblem efficiently. Our tailored Benders approaches outperform the perspective reformulation solved using the state-of-the-art MISOCP solver Gurobi on adapted instances from the literature.

This paper analyzes the performance of five well-known off-the-shelf optimization solvers on a set of congested capacitated facility location problems formulated as mixed-integer conic programs (MICPs). We aim to compare the computational efficiency of the solvers and examine the solution strategies they adopt when solving instances with different sizes and complexity. The solvers we compare are Gurobi, Cplex, Mosek, Xpress, and Scip. We run extensive numerical tests on a testbed of 30 instances from the literature. Our results show that Mosek and Gurobi are the most competitive solvers, as they achieve better time and gap performance, solving most instances within the time limit. Mosek outperforms Gurobi in large-size problems and provides more accurate solutions in terms of feasibility. Xpress solves to optimality about half of the instances tested within the time limit, and in this half, it achieves performance similar to that of Gurobi and Mosek. Cplex and Scip emerge as the least competitive solvers. The results provide guidelines on how each solver behaves on this class of problems and highlight the importance of choosing a solver suited to the problem type.

This paper addresses the site and power assignment problem arising in the optimal design of wireless networks. It is well-known that natural formulations of this problem are sources of numerical instabilities and make the optimal solution challenging for state-of-the-art solvers, even in small-sized instances. We tackle this limitation from a computational perspective by suggesting two implementation procedures that can speed up the solution of this problem. The first is an extremely effective branching rule for a compact reformulation of this problem. Presolve operations are used as a second strategy to manage numerical instability. The approaches are validated using realistic LTE instances kindly provided by Fondazione Ugo Bordoni. The proposed implementation techniques have proved capable of significantly accelerating the solution of the problem, beating the performance of a standard solution.