Extended formulation for hop constrained ...
Document type :
Compte-rendu et recension critique d'ouvrage
Title :
Extended formulation for hop constrained distribution network configuration problems
Author(s) :
de Boeck, Jérôme [Auteur]
Département d'Informatique
Fortz, Bernard [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Graphes et Optimisation Mathématique [Bruxelles] [GOM]
Département d'Informatique
Fortz, Bernard [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Graphes et Optimisation Mathématique [Bruxelles] [GOM]
Journal title :
European Journal of Operational Research
Pages :
488 - 502
Publisher :
Elsevier
Publication date :
2018-03
ISSN :
0377-2217
English keyword(s) :
Distribution networks
Hop constraints
Extended formulations
Layered graphs
Hop constraints
Extended formulations
Layered graphs
HAL domain(s) :
Computer Science [cs]/Operations Research [math.OC]
English abstract : [en]
A distribution network is a system aiming to transfer a certain type of resource from feeders to customers. Feeders are producers of a resource and customers have a certain demand in this resource that must be satisfied. ...
Show more >A distribution network is a system aiming to transfer a certain type of resource from feeders to customers. Feeders are producers of a resource and customers have a certain demand in this resource that must be satisfied. Distribution networks can be represented on graphs and be subject to constraints that limit the number of intermediate nodes between some elements of the network (hop constraints) because of physical constraints. This paper uses layered graphs for hop constrained problems to build extended formulations. Preprocessing techniques are also presented to reduce the size of the layered graphs used. The presented model is studied on the hop-constrained minimum margin problem in an electricity network. This problem consists of designing a connected electricity distribution network, and to assign customers to electricity feeders at a maximum number of hops H so as to maximize the minimum capacity margin over the feeders to avoid an overload for any feeder. Numerical results of our model are compared with those of state-of-the-art solution techniques of the minimum margin problem form Rossi et al. [20]. Variations of the initial problem are also presented, considering losses due to transportation or by replacing hop constraints by distance constraints, a variation arising in the context of multicast transmission in telecommunications.Show less >
Show more >A distribution network is a system aiming to transfer a certain type of resource from feeders to customers. Feeders are producers of a resource and customers have a certain demand in this resource that must be satisfied. Distribution networks can be represented on graphs and be subject to constraints that limit the number of intermediate nodes between some elements of the network (hop constraints) because of physical constraints. This paper uses layered graphs for hop constrained problems to build extended formulations. Preprocessing techniques are also presented to reduce the size of the layered graphs used. The presented model is studied on the hop-constrained minimum margin problem in an electricity network. This problem consists of designing a connected electricity distribution network, and to assign customers to electricity feeders at a maximum number of hops H so as to maximize the minimum capacity margin over the feeders to avoid an overload for any feeder. Numerical results of our model are compared with those of state-of-the-art solution techniques of the minimum margin problem form Rossi et al. [20]. Variations of the initial problem are also presented, considering losses due to transportation or by replacing hop constraints by distance constraints, a variation arising in the context of multicast transmission in telecommunications.Show less >
Language :
Anglais
Popular science :
Non
Collections :
Source :
Files
- https://hal.inria.fr/hal-01665624/document
- Open access
- Access the document
- https://hal.inria.fr/hal-01665624/document
- Open access
- Access the document
- https://hal.inria.fr/hal-01665624/document
- Open access
- Access the document
- document
- Open access
- Access the document
- MMPrev1.1.pdf
- Open access
- Access the document
- MMPrev1.1.pdf
- Open access
- Access the document