In this paper we present an algorithmic framework for solving a class of combinatorial optimization problems on graphs with bounded pathwidth. The problems are NP-hard in general, but solvable in linear time on this type of graphs. The problems are relevant for assessing network reliability and improving the network’s performance and fault tolerance. The main … Read more
This paper is concerned with the single-row facility layout problem (SRFLP). A globally optimal solution to the SRFLP is a linear placement of rectangular facilities with varying lengths that achieves the minimum total cost associated with the (known or projected) inter- actions between them. We demonstrate that the combination of a semidefinite programming relaxation with … Read more
Consider the problem that consists in maximizing the revenue generated by tolls set on a subset of arcs of a transportation network, and where origin-destination flows are assigned to shortest paths with respect to the sum of tolls and initial costs. In this work, we address the instance where toll arcs must be connected, as … Read more
We study the problem of optimizing nonlinear objective functions over matroids presented by oracles or explicitly. Such functions can be interpreted as the balancing of multi-criteria optimization. We provide a combinatorial polynomial time algorithm for arbitrary oracle-presented matroids, that makes repeated use of matroid intersection, and an algebraic algorithm for vectorial matroids. Our work is … Read more
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