NDLI: N-step mingling inequalities: new facets for the mixed-integer knapsack set

Content Provider	Springer Nature Link
Author	Kianfar, Kiavash Atamtürk, Alper
Copyright Year	2010
Abstract	The n-step mixed integer rounding (MIR) inequalities of Kianfar and Fathi (Math Program 120(2):313–346, 2009) are valid inequalities for the mixed-integer knapsack set that are derived by using periodic n-step MIR functions and define facets for group problems. The mingling and 2-step mingling inequalities of Atamtürk and Günlük (Math Program 123(2):315–338, 2010) are also derived based on MIR and they incorporate upper bounds on the integer variables. It has been shown that these inequalities are facet-defining for the mixed integer knapsack set under certain conditions and generalize several well-known valid inequalities. In this paper, we introduce new classes of valid inequalities for the mixed-integer knapsack set with bounded integer variables, which we call n-step mingling inequalities (for positive integer n). These inequalities incorporate upper bounds on integer variables into n-step MIR and, therefore, unify the concepts of n-step MIR and mingling in a single class of inequalities. Furthermore, we show that for each n, the n-step mingling inequality defines a facet for the mixed integer knapsack set under certain conditions. For n = 2, we extend the results of Atamtürk and Günlük on facet-defining properties of 2-step mingling inequalities. For n ≥ 3, we present new facets for the mixed integer knapsack set. As a special case we also derive conditions under which the n-step MIR inequalities define facets for the mixed integer knapsack set. In addition, we show that n-step mingling can be used to generate new valid inequalities and facets based on covers and packs defined for mixed integer knapsack sets.
Ending Page	98
Page Count	20
Starting Page	79
File Format	PDF
ISSN	00255610
e-ISSN	14364646
Journal	Mathematical Programming
Issue Number	1-2
Volume Number	132
Language	English
Publisher	Springer-Verlag
Publisher Date	2010-05-25
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Mathematical Methods in Physics Mathematics of Computing Calculus of Variations and Optimal Control; Optimization Numerical Analysis Theoretical, Mathematical and Computational Physics Mingling Mixed integer rounding Mixed integer programming Combinatorics Valid inequality Facet
Content Type	Text
Resource Type	Article
Subject	Mathematics 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

n-step mingling inequalities: new facets for the mixed-integer knapsack set

N-step mingling inequalities: new facets for the mixed-integer knapsack set (2012).

Generalized mixed integer rounding inequalities: facets for infinite group polyhedra

Mingling: mixed-integer rounding with bounds

Using cuts for mixed integer knapsack sets to generate cuts for mixed integer polyhedral conic sets

On n-step mir and partition inequalities for integer knapsack and single-node capacitated flow sets.

Unique lifting of integer variables in minimal inequalities

On the mixing set with a knapsack constraint

Generalized Mixed Integer Rounding Valid Inequalities (2006)

N-step mingling inequalities: new facets for the mixed-integer knapsack set

Similar Documents

n-step mingling inequalities: new facets for the mixed-integer knapsack set

N-step mingling inequalities: new facets for the mixed-integer knapsack set (2012).

Generalized mixed integer rounding inequalities: facets for infinite group polyhedra

Mingling: mixed-integer rounding with bounds

Using cuts for mixed integer knapsack sets to generate cuts for mixed integer polyhedral conic sets

On n-step mir and partition inequalities for integer knapsack and single-node capacitated flow sets.

Unique lifting of integer variables in minimal inequalities

On the mixing set with a knapsack constraint

Generalized Mixed Integer Rounding Valid Inequalities (2006)

N-step mingling inequalities: new facets for the mixed-integer knapsack set