I'm using Mathematica 7's NMaximize to solve a linear programming problem with thousands of 0/1 integer variables, thousands of linear constraints and a linear target. I suppose I could use LinearProgramming but building inequalities and using NMaximize is very straightforward.

I was wondering which method is NMaximize using to solve the problems so I did as follows:

  • I solve it using the by-default Automatic method. It took 2 minutes.
  • The I tried every method listed in the help page (Differential evolution, Nelder-Mead, Simmulated Annealing, Random Search) to check which of them gets the same timing.

To my surprise, none of the manually configured methods could finish in 10 minutes. In addition, StepMonitor and EvaluationMonitor are never evaluated when using the automatic method, not even at the end.

So I suppose it is using another method, not listed in the documentation, to solve the problem.

Is there a way to know which method is being used? Maybe NMaximize has transformed the problem and is solving it with LinearProgramming?

  • 6
    $\begingroup$ Yes, it is almost certainly recognizing it has an ILP and invoking FindMinumum code. This in turn uses the COIN-CLP library for such problems. $\endgroup$ Jul 1 '15 at 15:08
  • $\begingroup$ You might want to see this. $\endgroup$ Jul 1 '15 at 17:49
  • $\begingroup$ Thank you for the answers. It really seems it is using the ILP solver, which is great. Is there any advantage in building the matrices for LinearProgramminginstead of relying on NMaximize to do that? $\endgroup$
    – siritinga
    Jul 2 '15 at 6:09
  • $\begingroup$ @Guesswhoitis. that is not working in this case. I see no "method" output. It seems that it just call LinearProgramming with no information of doing so. $\endgroup$
    – siritinga
    Jul 2 '15 at 6:11
  • 1
    $\begingroup$ Yes, that was my point. Now you know that NMaximize[] is indeed doing something special. As for directly building the matrices and directly using LP, I would think that would be more efficient, but you will have to test to be sure. $\endgroup$ Jul 2 '15 at 6:18

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.