Unsplittable non-additive capacitated network design using set functions polyhedra

Unsplittable non-additive capacitated network design using set functions polyhedra

0.00 Avg rating0 Votes
Article ID: iaor201530004
Volume: 66
Issue: 4
Start Page Number: 105
End Page Number: 115
Publication Date: Feb 2016
Journal: Computers and Operations Research
Authors: , , ,
Keywords: programming: linear, programming: integer, graphs
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.