The general solution of a mixed integer linear programme over a cone

H. Paul Williams

LSE Research Online Documents on Economics from London School of Economics and Political Science, LSE Library

Abstract: We give a general method of finding the optimal objective, and solution, values of a Mixed Integer Linear Programme over a Cone (MILPC) as a function of the coefficients (objective, matrix and right- hand side). In order to do this we first convert the matrix of constraint coefficients to a Normal Form (Modified Hermite Normal Form (MHNF)). Then we project out all the variables leaving an (attainable) bound on the optimal objective value. For (M)IPs, including MILPC, projection is more complex, than in the Linear programming (LP) case, yielding the optimal objective value as a finite disjunction of inequalities The method can also be interpreted as finding the 'minimal' strengthening of the constraints of the LP relaxation which yields an integer solution to the associated LP.

JEL-codes: J50 (search for similar items in EconPapers)
Pages: 15 pages
Date: 2013-01
References: View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://eprints.lse.ac.uk/49681/ Open access version. (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:ehl:lserod:49681

Access Statistics for this paper

More papers in LSE Research Online Documents on Economics from London School of Economics and Political Science, LSE Library LSE Library Portugal Street London, WC2A 2HD, U.K.. Contact information at EDIRC.
Bibliographic data for series maintained by LSERO Manager ().