An integral linear program is one that has a maximizer that is integral. Sometimes it's possible to prove that a particular LP has this property, for example by proving that it's constraint matrix is totally unimodular.

Suppose that we have an integral LP, how can we then efficiently find an integral maximizer? After all, the optimum may be achieved by many different maximizers rather than just the integral ones.

  • $\begingroup$ cstheory.stackexchange.com/q/47280/5038 $\endgroup$
    – D.W.
    Jul 29, 2020 at 7:06
  • $\begingroup$ I’m voting to close this question because it was cross-posted and answered elsewhere. $\endgroup$
    – D.W.
    Jul 31, 2020 at 3:35


Browse other questions tagged or ask your own question.