3
$\begingroup$

Im solving n-dimensional Knapsack problem as LP problem.

I noticed that sometimes dual LP problem may be solved much faster than primal.

My test problem contains 500k variables and 50k constraints, integers only.

When I force 'presolve dual setting' I see much better results in some cases comparing to 'presolve dual setting' set to auto, but sometimes primal is faster. https://www.ibm.com/docs/en/cofz/12.10.0?topic=parameters-presolve-dual-setting

Is there any way to understand that primal problem will take a lot of time and try dual instead?

btw. When problem is slow I see a lot of iterations like, maybe a lot of iterations with same gap may be an indicator

enter image description here

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

If the primal LP problem suffers from degeneracy, I believe dual simplex may be faster. You might try using the barrier method to solve the (primal) LP. In cases where the LP has degeneracy issues, I think barrier has been known to speed things up.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I have tried all the methods for primal problem and have not found any performance improvement $\endgroup$
    – John
    Commented May 11, 2023 at 19:13
  • $\begingroup$ Yes, so primal problem suffers from degeneracy, but how to detect that automatically and switch to dual using python API? is that even possible? $\endgroup$
    – John
    Commented May 11, 2023 at 19:14
  • 1
    $\begingroup$ I don't know of any way to detect degeneracy automatically (other than to inspect the RHS for zeros after each pivot, which would really slow things down. You might look at the "simplex perturbation limit" parameter. Changing it from the default (automatic) to a small(ish) value might help if degeneracy is the problem. Then again, if barrier did not help, it might be that degeneracy is not the issue. $\endgroup$
    – prubin ♦
    Commented May 11, 2023 at 19:53
  • $\begingroup$ I decided to decrease accuracy to increase speed by changing 'relative MIP gap tolerance' and 'absolute MIP gap tolerance' $\endgroup$
    – John
    Commented May 24, 2023 at 12:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.