Adjacent Vertices of the Convex Hull of Feasible 0-1 Points.

Abstract

In the paper the authors give a constructive characterization of adjacency relations between integer vertices of the feasible set of an all zero-one program. This characterization can be used, for instance, to generate all integer vertices of the feasible set, adjacent to a given integer vertex. As a by-product, the authors establish a strong bound on the diameter of the convex hull of feasible 0-1 points. (Author)

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1973
Accession Number
AD0765766

Entities

People

  • Egon Balas
  • Manfred Padberg

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Behavior And Behavior Mechanisms
  • Behavioral Disciplines And Activities
  • Behavioral Sciences
  • Cooperation
  • Diameters
  • Geometry
  • Group Dynamics
  • Mathematics
  • Physical Properties
  • Psychology

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research