Aggregation of Inequalities in Integer Programming.

Abstract

Given an m x n zero-one matrix A approximately it is asked whether there is a single linear inequality ax less than or equal to b whose zero-one solutions are precisely the zero-one solutions of Ax less than or equal to e. An algorithm is developed for answering this question in O(mn sq) steps and other related problems are investigated. The results may be interpreted in terms of graph theory and threshold logic.

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1975
Accession Number
ADA018461

Entities

People

  • Peter L. Hammer
  • Vaclav Chvatal

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Evolutionary Algorithms
  • Graph Theory
  • Heuristic Methods
  • Inequalities
  • Integer Programming
  • Mathematics

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Team-Based Human-Centered Cognitive Task Decision Making and Information Performance.