6
$\begingroup$

When using LinearProgramming with the Integers domain, Mathematica issues the following warning:

In[3]:= LinearProgramming[{1, 1}, {{5, 2}}, {3}, Automatic, Integers]

During evaluation of In[3]:= LinearProgramming::lpip: Warning: integer linear programming will use a machine-precision approximation of the inputs.

Out[3]= {1, 0}

Warning: integer linear programming will use a machine-precision approximation of the inputs.

I am not deeply familiar with integer programming. What are the practical implications of using a "machine-precision approximation"? I assume that this means is that the result may not be exact (optimal). Under what circumstances will this be the case, and how might one go about detecting it? Are there alternative functions in Mathematica which can avoid these issues?

$\endgroup$
  • $\begingroup$ My motivation is to solve computationally hard graph-theoretical problems that were encoded into ILP, and have some confidence about the exactness of the solution. The problems in question are known to have a feasible solution. The trick is: how to find the optimal one? $\endgroup$ – Szabolcs Apr 24 at 8:48
  • $\begingroup$ I think I have seen LinearProgramming fail to produce a correct integer-valued result even for a relatively simple problem when values of integers in the problem have grown larger than what is presentable at the requested precision (machine precision by default). Sadly I can't really remember details about this. Only mention on the whole subject in the documentation is "The integer programming algorithm is limited to the machine-number problems." I wonder what algorithm it uses... $\endgroup$ – kirma Apr 24 at 12:32
  • $\begingroup$ ... and it seems that WRI really wants these problems to be solved with Minimize: reference.wolfram.com/language/tutorial/… $\endgroup$ – kirma Apr 24 at 12:41
  • 2
    $\begingroup$ These use COIN-CLP under the hood, and it is known that results might be suboptimal when the machine precision LP solver is not adequate for the numbers that would appear in exact arithmetic. As noted by @kirma, Minimize does not have such restrictions. It is slow though because it uses exact artithmetic on the relaxed LPs. $\endgroup$ – Daniel Lichtblau Apr 24 at 15:33
  • 1
    $\begingroup$ The relaxed LPs even for a 0-1 ILP can get into precision problems. It has happened in solving traveling salesman problems, for example. $\endgroup$ – Daniel Lichtblau Apr 24 at 15:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.