A Graph-Theoretic Equivalence for Integer Programs

1 February 1973

journal article
Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research

Vol. 21 (1), 261-269
https://doi.org/10.1287/opre.21.1.261

Abstract

This paper is concerned with the relation between 0-1 integer programs and graphs. An equivalence is established between solving 0-1 integer programs with quadratic or linear objective functions and solving a cut problem on a related graph.

Keywords

ALGEBRA
SET THEORY
GRAPHICS
OPTIMIZATION
MATHEMATICAL PROGRAMMING

Cited by 25 articles