Resource title

A characterisation of all feasible solutions to an integer program

Resource image

image for OpenScout resource :: A characterisation of all feasible solutions to an integer program

Resource description

It is shown how the dual of Fourier–Motzkin elimination can be applied to eliminating the constraints of an Integer Linear Program. The result will, in general, be to reduce the Integer Program to a single Diophantine equation together with a series of Linear homogeneous congruences. Extreme continuous solutions to the Diophantine equation give extreme solutions to the Linear Programming relaxation. Integral solutions to the Diophantine equation which also satisfy the congruences give all the solutions to the Integer Program.

Resource author

Resource publisher

Resource publish date

Resource language

en

Resource content type

Resource resource URL

http://eprints.lse.ac.uk/31609/

Resource license