Lifted Flow Pack Facets of the Single Node Fixed-Charge Flow Polytope (1999)

Content Provider	CiteSeerX
Author	Atamtürk, Alper
Abstract	We present a class of facet-defining valid inequalities for the single node fixed-charge flow polytope. These inequalities are obtained through sequence independent lifting of the simpler flow pack inequalities that are valid for lower dimensional projections. We provide a comparison of the new inequalities with others from the literature. We also present computational results that show the effectiveness of these inequalities in solving mixed-integer programming problems with fixed-charges with a branch-and-cut algorithm. Keywords: fixed-charge problems, valid inequalities, lifting, superadditivity. This research is supported, in part, by a Junior Faculty Research Grant from the University of California. 1 Introduction The single node fixed-charge flow model is a basic structure that arises as an important relaxation of many 0-1 mixed-integer programming (BMIP) problems with fixed charges. The model consists of a flow balance inequality for a single node with demand b and variabl...
File Format	PDF
Language	English
Publisher Date	1999-01-01
Publisher Institution	Operations Research Letters
Access Restriction	Open
Subject Keyword	Single Node Fixed-charge Flow Polytope Flow Pack Facet Simpler Flow Pack Inequality Fixed Charge Branch-and-cut Algorithm New Inequality Facet-defining Valid Inequality Valid Inequality Sequence Independent Lifting Mixed-integer Programming Problem Many 0-1 Mixed-integer Programming Dimensional Projection Fixed-charge Problem Important Relaxation Basic Structure Computational Result Junior Faculty Research Grant Flow Balance Inequality Single Node Single Node Fixed-charge Flow Model
Content Type	Text
Resource Type	Technical Report