On Connections Between Zero-One Integer Programming and Concave Programming Under Linear Constraints

M. Raghavachari
Additional contact information
M. Raghavachari: Carnegie-Mellon University, Pittsburgh, Pennsylvania and Indian Institute of Management, Ahmedabad, India

Operations Research, 1969, vol. 17, issue 4, 680-684

Abstract: Consider the zero-one integer programming problem P 1 i:minimize Z = c ′ x subject to Ax ≦ b , 0 ≦ x i ≦ 1, x j = 0 or 1, j = 1, 2, …, n , where A is an m × n matrix, c ′ = ( c 1 , …, c n ), x ′ = ( x 1 , …, x n ), and b is an m × 1 vector with b ′ = ( b 1 , …, b m ). Assume the elements of A , b , c are all rational. This paper characterizes the feasible solutions of P 1 , shows that P 1 is equivalent to a problem of minimizing a concave quadratic objective function over a convex set, and applies a method developed by Tul to solve such a problem to yield a procedure for the zero-one integer programming problem.

Date: 1969
References: Add references at CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.17.4.680 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:17:y:1969:i:4:p:680-684

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().