We consider the capacity planning of telecommunication networks with linear investment costs and uncertain future traffic demands. Transmission capacities must be large enough to meet, with a high quality of service, the range of possible demands, after adequate routings of messages on the created network. We use the robust optimization methodology to balance the need … Read more
Telecommunication systems make use of optical signals to transmit information. The strength of a signal in an optical network deteriorates and loses power as it gets farther from the source, mainly due to attenuation. Therefore, to enable the signal to arrive at its intended destination with good quality, it is necessary to regenerate it periodically … Read more
The problem of routing and wavelength assignment (RWA) in wavelength division multiplexing (WDM) optical networks consists in routing a set of lightpaths and assigning a wavelength to each of them, such that lightpaths whose routes share a common fiber are assigned different wavelengths. This problem was shown to be NP-hard when the objective is to … Read more
We study the problem of detecting a maximum embedded network submatrix in a {-1,0,+1}-matrix. Our aim is to solve the problem to optimality. We introduce a 0-1 integer linear formulation for this problem based on its representation over a signed graph. A polyhedral study is presented and a branch-and-cut algorithm is described for finding an … Read more
We study the maximum flow problem subject to binary disjunctive constraints in a directed graph: A negative disjunctive constraint states that a certain pair of arcs in a digraph cannot be simultaneously used for sending flow in a feasible solution. In contrast to this, positive disjunctive constraints force that for certain pairs of arcs at … Read more
We study the version of the asymmetric prize collecting traveling salesman problem, where the objective is to find a directed tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. In \cite{Amico}, the authors … Read more
Given a general mixed integer program (MIP), we automatically detect block structures in the constraint matrix together with the coupling by capacity constraints arising from multi-commodity flow formulations. We identify the underlying graph and generate cutting planes based on cuts in the detected network. Our implementation adds a separator to the branch-and-cut libraries of Scip … Read more
Hop constraint is associated with modern communication network flows. We consider the problem of designing an optimal undirected network with integer-valued edge-capacities that meets a given set of single-commodity, hop-constrained network flow value requirements. We present a strongly polynomial, combinatorial algorithm for the problem with value of hop-parameter equal to three when values of flow … Read more
We study the minimum spanning tree problem, the maximum matching problem and the shortest path problem subject to binary disjunctive constraints: A negative disjunctive constraint states that a certain pair of edges cannot be contained simultaneously in a feasible solution. It is convenient to represent these negative disjunctive constraints in terms of a so-called conflict … Read more
We propose a unifying framework for polyhedral approximation in convex optimization. It subsumes classical methods, such as cutting plane and simplicial decomposition, but also includes new methods, and new versions/extensions of old methods, such as a simplicial decomposition method for nondifferentiable optimization, and a new piecewise linear approximation method for convex single commodity network flow … Read more