Optimization Online


On Blocking and Anti-Blocking Polyhedra in Infinite Dimensions

Luis Rademacher(lrademac***at***cse.ohio-state.edu)
Alejandro Toriello(atoriello***at***isye.gatech.edu)
Juan Pablo Vielma(jvielma***at***mit.edu)

Abstract: We consider the natural generalizations of blocking and anti-blocking polyhedra in infinite dimensions, and study issues related to duality and integrality of extreme points for these sets. Using appropriate finite truncations, we give conditions under which complementary slackness holds for primal-dual pairs of the infi nite linear programming problems associated with infi nite blocking and anti-blocking polyhedra. We also give conditions under which the extreme points of in finite blocking and anti-blocking polyhedra are integral. We illustrate an application of our results on an in finite-horizon lot-sizing problem.

Keywords: blocking polyhedron, anti-blocking polyhedron, complementary slackness, integral extreme point

Category 1: Infinite Dimensional Optimization

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Combinatorial Optimization (Graphs and Matroids )

Citation: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology. November, 2013.

Download: [PDF]

Entry Submitted: 11/18/2013
Entry Accepted: 11/18/2013
Entry Last Modified: 11/18/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society