Take Action

Home | Faculty & Research Overview | Research

Research Details

Dual Row Modules and Polyhedra of Blocking Group Problems, Mathematical Programming

Abstract

Corresponding to every group problem is a row module. Duality for group problems is developed using the duality or orthogonality of the corresponding row modules. The row module corresponding to a group problem is shown to include Gomory's fractional cuts for the group polyhedron and all the vertices of the polyhedron of the blocking group problem. The polyhedra corresponding to a pair of blocking group problems are shown to have a blocking nature i.e. the vertices of one include some of the facets of the other and mutatis mutandis. The entire development is constructive. The notions of contraction, deletion, expansion and extension are defined constructively and related to homomorphic liftings and suproblems in a dual setting. Roughly speaking a homomorphic lifting is dual to forming a subproblem. A proof of the Gastou-Johnson generalization of Gomory's homomorphic lifting theorem is given, and dual constructions are discussed. A generalization of Gomory's subadditive characterization to subproblems is given. In the binary case, it is closely related to the work of Seymour on cones arising from binary matroids.

Type

Article

Author(s)

Sunil Chopra, Ellis L. Johnson

Date Published

1987

Citations

Chopra, Sunil, and Ellis L. Johnson. 1987. Dual Row Modules and Polyhedra of Blocking Group Problems. Mathematical Programming. 38(3): 229-270.

KELLOGG INSIGHT

Explore leading research and ideas

Find articles, podcast episodes, and videos that spark ideas in lifelong learners, and inspire those looking to advance in their careers.
learn more

COURSE CATALOG

Review Courses & Schedules

Access information about specific courses and their schedules by viewing the interactive course scheduler tool.
LEARN MORE

DEGREE PROGRAMS

Discover the path to your goals

Whether you choose our Full-Time, Part-Time or Executive MBA program, you’ll enjoy the same unparalleled education, exceptional faculty and distinctive culture.
learn more

Take Action