Solving the problem

Highlights MIP emphasis and solution polishing parameters; tells where to find the application.

An emphasis on finding hidden feasible solutions has proven particularly effective for this problem so this example makes that selection by setting the MIPEmphasis parameter to 4. For more detail about setting the MIP emphasis parameter to find hidden feasible solutions, see MIP emphasis switch in the CPLEX Parameters Reference Manual.

Solution polishing is also useful in this problem. Activate solution polishing by specifying a positive value for the parameter that controls the amount of time (in seconds) spent on polishing. For detail about that parameter, see time before starting to polish a feasible solution in the CPLEX Parameters Reference Manual. For more detail about invoking solution polishing, see Solution polishing in this manual.

More generally, to invoke solution polishing and to emphasize finding hidden feasible solutions both tend to be effective strategies on models where adjusting a small subset of variables can easily yield better solutions. In other words, in such problems, local search heuristics are effective. The following types of models are well suited for these parameter settings of local search heuristics
  1. to emphasize finding hidden feasible solutions
  2. to invoke solution polishing on the feasible solutions
  • scheduling
  • knapsack
  • vehicle routing
  • set covering
  • set packing
  • set partitioning
(This list is suggestive, not exhaustive nor exclusive. Other types of problems can also benefit from this approach as well.)

You can see the entire example online in the standard distribution of CPLEX at yourCPLEXinstallation/examples/src/etsp.cpp. Implementations of the same model, using the same features of CPLEX, are available as Etsp.java, Etsp.cs, and Etsp.vb as well.