Premium
The capacity formulation of the capacitated edge activation problem
Author(s) -
Mattia Sara
Publication year - 2018
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21797
Subject(s) - polyhedron , mathematical optimization , enhanced data rates for gsm evolution , path (computing) , vehicle routing problem , routing (electronic design automation) , focus (optics) , set (abstract data type) , computer science , mathematics , facet (psychology) , packing problems , branch and cut , integer programming , combinatorics , psychology , computer network , social psychology , physics , personality , optics , big five personality traits , programming language , telecommunications
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.