Preprocessing

• Before LP relaxation is solved

• Check for infeasibilities, eliminate redundant constraints, strengthen variable bounds, improve coefficients, “probing”.

  • Employs structure

• Reduce cost fixing (after LP is solved)

  • Typically removes ½ the variables in set partitioning problems arising from crew scheduling applications

• At root node, or at subsequent nodes

• Trade off: time preprocessing against benefit

• Is it worth it for your problem?

  • Solvers allow different levels
    of preprocessing

Previous slide

Next slide

Back to first slide

View graphic version