Recent developments have drawn focus towards the efficient calculation of flows in AC power grids, which are difficult to solve systems of nonlinear equations. The common linearization approach leads to the well known and often used DC formulation, which has some major drawbacks. To overcome these drawbacks we revisit an alternative linearization of the AC … Read more
Affinely-Adjustable Robust Counterparts provide tractable alternatives to (two-stage) robust programs with arbitrary recourse. We apply them to robust network design with polyhedral demand uncertainty, introducing the affine routing principle. We compare the affine routing to the well-studied static and dynamic routing schemes for robust network design. All three schemes are embedded into the general framework … Read more
Energy consumption of communication systems is becoming a fundamental issue and, among all the sectors, wireless access networks are largely responsible for the in- crease in consumption. In addition to the access segment, wireless technologies are also gaining popularity for the back- haul infrastructure of cellular systems mainly due to their cost and easy deployment. … Read more
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