Main Content

Tuning Integer Linear Programming

Change Options to Improve the Solution Process

Note

Often, you can change the formulation of a MILP to make it more easily solvable. For suggestions on how to change your formulation, see Williams[1].

After you runintlinprogonce, you might want to change some options and rerun it. The changes you might want to see include:

  • Lower run time

  • Lower final objective function value (a better solution)

  • Smaller final gap

  • More or different feasible points

Here are general recommendations for option changes that are most likely to help the solution process. Try the suggestions in this order:

  1. For a faster and more accurate solution, increase theCutMaxIterationsoption from its default10to a higher number such as25. This can speed up the solution, but can also slow it.

  2. For a faster and more accurate solution, change theCutGenerationoption to'intermediate'or'advanced'. This can speed up the solution, but can use much more memory, and can slow the solution.

  3. For a faster and more accurate solution, change theIntegerPreprocessoption to'advanced'. This can have a large effect on the solution process, either beneficial or not.

  4. For a faster and more accurate solution, change theRootLPAlgorithmoption to'primal-simplex'. Usually this change is not beneficial, but occasionally it can be.

  5. To try to find more or better feasible points, increase theHeuristicsMaxNodesoption from its default50to a higher number such as100.

  6. 试图找到更多或更好的可行点,魅力nge theHeuristicsoption to either'intermediate'or'advanced'.

  7. 试图找到更多或更好的可行点,魅力nge theBranchRuleoption to'strongpscost'or, if that choice fails to improve the solution,'maxpscost'.

  8. For a faster solution, increase theObjectiveImprovementThresholdoption from its default of zero to a positive value such as1e-4. However, this change can causeintlinprogto find fewer integer feasible points or a less accurate solution.

  9. To attempt to stop the solver more quickly, change theRelativeGapToleranceoption to a higher value than the default1e-4. Similarly, to attempt to obtain a more accurate answer, change theRelativeGapToleranceoption to a lower value. These changes do not always improve results.

Some “Integer” Solutions Are Not Integers

Often, some supposedly integer-valued components of the solutionx (intcon)are not precisely integers.intlinprogconsiders as integers all solution values withinIntegerToleranceof an integer.

To round all supposed integers to be precisely integers, use theroundfunction.

x (intcon) = round(x(intcon));

Caution

Rounding can cause solutions to become infeasible. Check feasibility after rounding:

max(A*x - b)% see if entries are not too positive, so have small infeasibilitymax(abs(Aeq*x - beq))% see if entries are near enough to zeromax(x - ub)% positive entries are violated boundsmax(lb - x)% positive entries are violated bounds

Large Components Not Integer Valued

intlinprogdoes not enforce that solution components be integer valued when their absolute values exceed2.1e9. When your solution has such components,intlinprogwarns you. If you receive this warning, check the solution to see whether supposedly integer-valued components of the solution are close to integers.

Large Coefficients Disallowed

intlinprogdoes not allow components of the problem, such as coefficients inf,A, orub,超过1e15in absolute value. If you try to runintlinprogwith such a problem,intlinprogissues an error.

If you get this error, sometimes you can scale the problem to have smaller coefficients:

  • For coefficients infthat are too large, try multiplyingfby a small positive scaling factor.

  • For constraint coefficients that are too large, try multiplying all bounds and constraint matrices by the same small positive scaling factor.

References

[1] Williams, H. Paul.Model Building in Mathematical Programming, 5th Edition.Wiley, 2013.