If $p \geq t$ are positive integers, a t-composition of p is an ordered t-tuple of positive integers summing p. If $T=(s_1, s_2, \dots, s_t)$ is a t-composition of p and W is a $p-(t-1) \times t$ matrix, call $W(T)= \sum_{k=1}^t w_{s_k k}$ the weight of the t-composition T. We show that finding a minimum … Read more
The central objective of this paper is to develop a transparent, consistent, self-contained, and stable country risk rating model, closely approximating the country risk ratings provided by Standard and Poor’s (S&P). The models should be non-recursive, i.e., they should not rely on the previous years’ S&P ratings. The selected set of variables includes not only … Read more
The semi-Lagrangian Relaxation (SLR) method has been introduced in Beltran et al. (2006) to solve the p-median problem. In this paper we apply the method to the Uncapacitated Facility Location (UFL) problem. We perform computational experiments on two main collections of UFL problems with unknown optimal values. On one collection, we manage to solve to … Read more
In adversarial environments, disabling the communication capabilities of the enemy is a high priority. We introduce the problem of determining the optimal number and locations for a set of jamming devices in order to neutralize a wireless communication network. This problem is known as the WIRELESS NETWORK JAMMING PROBLEM. We develop several mathematical programming formulations … Read more
A classical theorem in Combinatorial Optimization proves the existence of fully polynomial- time approximation schemes for the knapsack problem. In a recent paper, Van Vyve and Wolsey ask whether for each 0 < epsilon ≤ 1 there exists an extended formulation for the knapsack problem, of size polynomial in the number of variables and/or 1/epsilon ... Read more
The purpose of this paper is to illustrate the diversity of combinatorial problems encountered in the design of wireless switching systems. This is done via a representative selection of examples of real problems along with their associated resolution methods. It should be emphasized that all the resolution methods presented in this paper are successfully operating … Read more
Exploiting sparsity is essential to improve the efficiency of solving large optimization problems. We present a method for recognizing the underlying sparsity structure of a nonlinear partially separable problem, and show how the sparsity of the Hessian matrices of the problem’s functions can be improved by performing a nonsingular linear transformation in the space corresponding … Read more
This paper is devoted to the approximate resolution of a strongly NP-hard resource-constrained scheduling problem which arises in relation to the operability of certain high availability real time distributed systems. We present an algorithm based on the simulated annealing metaheuristic and, building on previous research on exact resolution methods, extensive computational results demonstrating its practical … Read more
This paper is devoted to the study of a resource-constrained scheduling problem which arises in relation to the operability of certain high availability real-time distributed systems. After a brief survey of the literature, we prove the NP-hardness of the problem and exhibit a few polynomial special cases. We then present a branch-and-bound algorithm for the … Read more
We consider optimization problems related to the prevention of large-scale cascading blackouts in power transmission networks subject to multiple scenarios of externally caused damage. We present computation with networks with up to 600 nodes and 827 edges, and many thousands of damage scenarios. CitationCORC Report TR-2005-07, Columbia UniversityArticleDownload View PDF