We report on a growing class of assignment problems that are increasingly of interest and very challenging in terms of the difficulty they pose to attempts at exact solution. These problems address economic issues in the location and design of factories, hospitals, depots, transportation hubs and military bases. Others involve improvements in communication network design. … Read more
Random-key genetic algorithms were introduced by Bean (1994) for solving sequencing problems in combinatorial optimization. Since then, they have been extended to handle a wide class of combinatorial optimization problems. This paper presents a tutorial on the implementation and use of biased random-key genetic algorithms for solving combinatorial optimization problems. Biased random-key genetic algorithms are … Read more
In this paper we define semidefinite packing programs and describe an algorithm to approximately solve these problems. Semidefinite packing programs arise in many applications such as semidefinite programming relaxations for combinatorial optimization problems, sparse principal component analysis, and sparse variance unfolding technique for dimension reduction. Our algorithm exploits the structural similarity between semidefinite packing programs … Read more
The facility layout problem is a global optimization problem that seeks to arrange a given number of rectangular facilities so as to minimize the total cost associated with the (known or projected) interactions between them. This paper is concerned with the single-row facility layout problem (SRFLP), the one-dimensional version of facility layout that is also … Read more
Identifying critical nodes in a graph is important to understand the structural characteristics and the connectivity properties of the network. In this paper, we focus on detecting critical nodes, or nodes whose deletion results in the minimum pair-wise connectivity among the remaining nodes. This problem, known as the CRITICAL NODE PROBLEM has applications in several … Read more
Given a power grid modeled by a network together with equations describing the power flows, power generation and consumption, and the laws of physics, the so-called N – k problem asks whether there exists a set of k or fewer arcs whose removal will cause the system to fail. We present theoretical results and computation … Read more
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