Abstract We study linear bilevel programming problems, where (some of) the leader and the follower variables are restricted to be integer. A discussion on the relationships between the optimistic and the pessimistic setting is presented, providing necessary and sufficient conditions for them to be equivalent. A new class of inequalities, the follower optimality cuts, is introduced. They are used to derive a single-level non-compact reformulation of a bilevel problem, both for the optimistic and for the pessimistic case. The same is done for a family of known inequalities, the no-good cuts, and a polyhedral comparison of the related formulations is carried out. Finally, for both the optimistic and the pessimistic approach, we present a branch-and-cut algorithm and discuss computational results.

Abstract In this paper we study a network design problem arising in the management of a carrier network. The aim is to route a traffic matrix, minimizing a measure of the network congestion while guaranteeing a prescribed quality of service. We formulate the problem, devise presolve procedures to reduce the size of the corresponding mixed‐integer programming formulation and show that the proposed approach can efficiently solve some real‐life problems, leading to an improvement with respect to the current practice in a real case study.

Abstract The capacitated edge activation problem consists of activating a minimum cost set of capacitated edges to ensure the routing of some traffic demands. If the demands are subject to uncertainty, we speak of the robust capacitated edge activation problem. We consider a capacity formulation of the problem and investigate, from a polyhedral perspective, the similarities and the differences between the robust capacitated edge activation and the robust network loading polyhedron, as well as between the polyhedra corresponding to different routing and flows policies.

Given a capacitated network, the Capacitated Edge Activation problem consists of choosing the edges to be activated to ensure the routing of a set of demands. We focus on capacity formulations of the problem, that is, formulations including only design variables, whereas variables corresponding to the routes are projected out. First, we investigate the combinatorial properties of the problem to derive a capacity formulation both for splittable flows (the routes are unrestricted) and for unsplittable ones (each demand must be routed on a single path). Then, we study the corresponding polyhedron, identifying valid and facet‐defining inequalities. Finally, we develop a branch‐and‐cut algorithm and present computational results.

This article focuses on the problem of minimizing the energy consumption in a resilient telecommunications network. For each demand, an edge‐disjoint pair of paths (primary and backup) must be provided and the shared protection scheme is used. The energy consumption is due only to edges used in the no‐fault scenario, but both primary and backup paths contribute to capacity consumption. We propose a projected formulation for the problem and show its effectiveness by comparing it with the complete formulation. We propose valid inequalities for both formulations. We evaluate the performances of the proposed formulations and valid inequalities through computational tests. Furthermore, we investigate the relationship between the shared and the dedicated protection version of the problem. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 6–22 2017

We consider the robust network design problem, which consists of choosing capacities for the edges of a graph so that a set of uncertain traffic demands can be routed. The scope of the paper is to study the robust cut property (RCP), that is, we investigate when the cut inequalities are sufficient to guarantee a feasible routing under demand uncertainty. We provide conditions that ensure the RCP. We discuss the generalization to the problem with uncertain demands of the results that are known for the problem without uncertainty. © 2015 Wiley Periodicals, Inc.NETWORKS, Vol. 66(2), 159–168 2015

Abstract A multilayer network is a hierarchical network where each layer is built using the components of the previous one. Optical networks are an example of two layered networks. The multilayer network design problem consists of installing minimum cost integer capacities on the edges of all the layers so that a set of demands can be routed on the network. In this article, two versions of the optical network design problem are studied, and polyhedral results for the corresponding capacity formulations are presented. We also show how to extend the results to a network with an arbitrary number of layers. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2013