Unsplittable non-additive capacitated network design using set functions polyhedra

In this paper, we address the Unsplittable Non-Additive Capacitated Network Design problem, a variant of the Capacitated Network Design problem where the flow of each commodity cannot be split, even between two facilities installed on the same link. We propose a compact formulation and an aggregated...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2016-02, Vol.66, p.105-115
Main Authors: Benhamiche, Amal, Mahjoub, A. Ridha, Perrot, Nancy, Uchoa, Eduardo
Format: Article
Language:English
Subjects:
Branch-and-Cut
Capacitated Network Design
Formulations
Inequalities
Mathematical analysis
Mathematical functions
Mathematical models
Network flow problem
Networks
Operations research
Packing problem
Polyhedra
Polyhedrons
Set functions
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we address the Unsplittable Non-Additive Capacitated Network Design problem, a variant of the Capacitated Network Design problem where the flow of each commodity cannot be split, even between two facilities installed on the same link. We propose a compact formulation and an aggregated formulation for the problem. The latter requires additional inequalities from considering each individual arc-set. Instead of studying those particular polyhedra, we consider a much more general object, the unitary step monotonically increasing set function polyhedra, and identify some families of facets. The inequalities that are obtained by specializing those facets to the Bin Packing function are separated in a Branch-and-Cut for the problem. Several series of experiments are conducted on random and realistic instances to give an insight on the efficiency of the introduced valid inequalities. •We give two ILP formulations for the UNACND problem.•We introduce polyhedra associated with a general class of functions.•We provide two classes of facets that are valid for all considered functions.•We devise a Branch-and-Cut algorithm embedding both classes of inequalities.•Our approach gives promising results and shows the efficiency of our inequalities.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2015.08.009