[en] We consider a mixed integer set which generalizes two well-known sets: the single node fixed- charge network set and the single arc design set. Such set arises as a relaxation of feasible sets of general mixed integer problems such as lot-sizing and network design problems.
We derive several families of valid inequalities that, in particular, generalize the arc resid- ual capacity inequalities and the flow cover inequalities. For the constant capacitated case we provide an extended compact formulation and give a partial description of the convex hull in the original space which is exact under a certain condition. By lifting some basic inequalities we provide some insight on the difficulty of obtaining such a full polyhedral description for the constant capacitated case. Preliminary computational results are presented.
Disciplines :
Mathematics
Author, co-author :
Agra, Agostinho; University of Aveiro
Doostmohammadi, Mahdi; University of Aveiro
Louveaux, Quentin ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète
Language :
English
Title :
Valid inequalities for the single arc design problem with set-ups
M.W. Padberg, T.J. Van Roy, L.A. Wolsey, Valid linear inequalities for fixed charge problems, Oper. Res. 33 (1985) 842-861.
T.L. Magnanti, P. Mirchandani, R. Vachani, The convex hull of two core capacitated network design problems, Math. Program. 60 (1993) 233-250.
Y. Pochet, L.A. Wolsey, Production Planning by Mixed Integer Programming, Springer, New York, 2006.
Y. Zhao, D. Klabjan, A polyhedral study of lot-sizing with supplier selection, Discrete Optim. 9 (2012) 65-76.
C. Archetti, L. Bertazzi, G. Laporte, M.G. Speranza, A branch-and-cut algorithm for a vendor-managed inventory-routing problem, Transp. Sci. 41 (2007) 382-391.
A. Agra, M. Doostmohammadi, Facets for the single node fixed-charge network set with a node set-up variable, Optim. Lett. 8 (2014) 1501-1515.
K. Martin, Using separation algorithms to generate mixed integer model reformulations, Oper. Res. Lett. 10 (1991) 119-128.
K. Aardal, Y. Pochet, L.A. Wolsey, Capacitated facility location: valid inequalities and facets, Math. Oper. Res. 20 (1995) 562-582.
E. Balas, Disjunctive programming: properties of the convex hull of feasible points, Discrete Appl. Math. 89 (1998) 3-44.
M. Doostmohammadi, Polyhedral study of mixed integer sets arising from inventory problems (Ph.D. dissertation), University of Aveiro, 2014.
Q. Louveaux, L.A. Wolsey, Lifting, superadditivity, mixed integer rounding and single node flow sets revisited, 4OR 1 (2003) 173-207.
G.L. Nemhauser, L.A. Wolsey, Integer and Combinatorial Optimization, Wiley, New York, 1988.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.