Unsplittable non-additive capacitated network design using set functions polyhedra. (February 2016)

• Record Type: Journal Article
• Authors: Benhamiche, Amal; Mahjoub, A. Ridha; Perrot, Nancy; Uchoa, Eduardo
• Is Part Of: Computers & operations research. Volume 66(2016)
• Page Start: 105
• Page End: 115
• Publication Date: 2016-02
• Subjects: Capacitated Network Design -- Set functions -- Polyhedra -- Branch-and-Cut; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2015.08.009
• Languages: English
• ISSNs: 0305-0548

Abstract

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. Abstract : Highlights: 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.