The mixing-MIR set with divisible capacities
type: Item
instance of: scholarly article
title: The mixing-MIR set with divisible capacities
zbMATH Open document ID: 1176.90433
published in: Mathematical Programming. Series A. Series B
publication date: 2008-06-30T00:00:00Z
review text: The authors study a generalization of the mixed integer rounding set, namely the mixing MIR set \(S=\{(x,y) \in \mathbb{R}_+ \times \mathbb{Z}^n: x+B_j y_j \geq b_j, j=1, \ldots, n\}\), where \(B_j, b_j \in \mathbb{R}_+ \setminus \{0\}\) and \(B_1|\cdots|B_n\), which arises in mixed integer programming. The authors determine all \(n+1\) extreme rays and all extreme points of \(P=conv(S)\) and show that the number of extreme points may grow exponentially with \(n\) in the worst case. They then develop a polynomial time algorithm for maximizing \(cx+dy\) over \((x,y) \in S\) as well as maximizing \((x^*,y^*)\cdot \omega\) over \(\omega \in \Omega\), where \(\Omega\) is the polar of \(P\).
reviewed by: Matthias Ehrgott
Mathematics Subject Classification ID: 90C11
Mathematics Subject Classification ID: 90C57
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 5294509
zbMATH Keywords: Mixed integer programming
zbMATH Keywords: cutting plane
zbMATH Keywords: simple mixed integer set
zbMATH Keywords: polyhedral combinatorics
author: Ming Zhao
author: I. R. jun. de Farias
MaRDI profile type: Publication
full work available at URL: s10107-007-0140-6
OpenAlex ID: W2090053073
cites work: Split closure and intersection cuts
cites work: Intersection Cuts—A New Type of Cutting Planes for Integer Programming
cites work: Facets of the knapsack polytope
cites work: Disjunctive Programming
cites work: Disjunctive programming: Properties of the convex hull of feasible points
cites work: A lift-and-project cutting plane algorithm for mixed 0-1 programs
cites work: Gomory cuts revisited
cites work: Subset Algebra Lift Operators for 0-1 Integer Programming
cites work: MIP: Theory and practice -- closing the gap
cites work: On the separation of split cuts and related inequalities
cites work: Edmonds polytopes and a hierarchy of combinatorial problems
cites work: Mixing MIR inequalities with two divisible coefficients
cites work: Chvátal closures for mixed integer programming problems
cites work: Elementary closures for integer programs.
cites work: Optimizing over the First Chvàtal Closure
cites work: Outline of an algorithm for integer solutions to linear programs
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: Mixing mixed-integer inequalities
cites work: Facet of regular 0–1 polytopes
cites work: Cones of Matrices and Set-Functions and 0–1 Optimization
cites work: Cutting planes in integer and mixed integer programming
cites work: Aggregation and Mixed Integer Rounding to Solve MIPs
cites work: Tight formulations for some simple mixed integer programs and convex objective integer programs
cites work: Q4040221
cites work: A recursive procedure to generate all cuts for 0-1 mixed integer programs
cites work: Integer knapsack and flow covers with divisible coefficients: Polyhedra, optimization and separation
cites work: Production Planning by Mixed Integer Programming
cites work: A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
cites work: A solution approach of production planning problems based on compact formulations for single-item lot-sizing models. (Abstract of thesis)
cites work: The Continuous Mixing Polyhedron
cites work: Faces for a linear inequality in 0–1 variables
cites work: Strong formulations for mixed integer programs: valid inequalities and extended formulations
DOI: 10.1007/S10107-007-0140-6
description: scientific article; zbMATH DE number 5294509