NDLI: Mixing Sets Linked by Bidirected Paths

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Wolsey, Laurence A. Di Summa, Marco
Copyright Year	2011
Abstract	Recently there has been considerable research on simple mixed-integer sets, called mixing sets, and closely related sets arising in uncapacitated and constant capacity lot-sizing. This in turn has led to study of more general sets, called network-dual sets, for which it is possible to derive extended formulations whose projection gives the convex hull of the network-dual set. Unfortunately this formulation cannot be used (in general) to optimize in polynomial time. Furthermore the inequalities defining the convex hull of a network-dual set in the original space of variables are known only for some special cases. Here we study two new cases, in which the continuous variables of the network-dual set are linked by a bidirected path. In the first case, which is motivated by lot-sizing problems with (lost) sales, we provide a description of the convex hull as the intersection of the convex hulls of $2^n$ mixing sets, where n is the number of continuous variables of the set. However optimization is polynomial as only $n+1$ of the sets are required for any given objective function. In the second case, generalizing single arc flow sets, we describe again the convex hull as the intersection of an exponential number of mixing sets and also give a combinatorial polynomial-time separation algorithm.
Starting Page	1594
Ending Page	1613
Page Count	20
File Format	PDF
ISSN	10526234
DOI	10.1137/100811799
e-ISSN	10957189
Journal	SIAM Journal on Optimization (SJOPE8)
Issue Number	4
Volume Number	21
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2011-12-15
Access Restriction	Subscribed
Subject Keyword	convex hull descriptions mixing sets mixed-integer programming Mixed integer programming lot-sizing Polyhedral combinatorics, branch-and-bound, branch-and-cut
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Theoretical Computer Science Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Erratum: Lot-Sizing with Stock Upper Bounds and Fixed Charges

Lot-Sizing with Stock Upper Bounds and Fixed Charges

On Mixing Inequalities: Rank, Closure, and Cutting-Plane Proofs

Uncapacitated lot sizing with backlogging: the convex hull

Mod2 Cuts Generation Yields the Convex Hull of Bounded Integer Feasible Sets

A Feasible Active Set Method with Reoptimization for Convex Quadratic Mixed-Integer Programming

On Maximal S-Free Convex Sets

The Mixing Set with Flows

The mixing-MIR set with divisible capacities

Mixing Sets Linked by Bidirected Paths

Similar Documents

Erratum: Lot-Sizing with Stock Upper Bounds and Fixed Charges

Lot-Sizing with Stock Upper Bounds and Fixed Charges

On Mixing Inequalities: Rank, Closure, and Cutting-Plane Proofs

Uncapacitated lot sizing with backlogging: the convex hull

Mod2 Cuts Generation Yields the Convex Hull of Bounded Integer Feasible Sets

A Feasible Active Set Method with Reoptimization for Convex Quadratic Mixed-Integer Programming

On Maximal S-Free Convex Sets

The Mixing Set with Flows

The mixing-MIR set with divisible capacities

Mixing Sets Linked by Bidirected Paths