CODEWITHSUNDEEP
javacplexheuristicsbranch-and-bound
abouttime
abouttime

Reputation: 1

CPLEX heuristics give different computational results

when we solve a maximization mip problem using cplex, can cplex heuristics affect the upper bound of the objective value?

as far as I understand, cplex heuristic can improve the lower bound of the optimal value but NOT the upper bound. but in my test, if i turn off cplex heuristic, it gives very poor upper bound. the difference of upper bounds(heuristic on/ off) is very huge to ignore. help me :-(

Upvotes: 0

Views: 381

Answers (1)

dfrib
dfrib

Reputation: 73166

A basic example for this study, lets assume your MIP is a a pure binary linear program (BLP) with only binary valued decision variables (no continuous ones mixed in). Further, assume that CPLEX solves your MIP using only basic Branch and Bound (BAB), leaving out advanced branching and node picking techniques.

Since your program is one of maximization, as you mention, naturally a good heuristic will affect the lower bound on objective function value of the optimal solution.

In our simple example, the upper bound will mainly be based on the currently best (best w.r.t. max. obj. function value) solution to the continuously relaxed BLP subproblems. I.e., the LP solution of active nodes (not yet pruned of branched upon) in your BAB tree where the binearity constraint on your decision variables, say x_i ∈ {0, 1}^n, has been replaced by its continuous relaxation, say x_i ∈ [0, 1]^n.

At this point, (meta-)heuristics can have great effect on e.g.

  • How we choose which nodes we want to process in the BAB tree. I.e., after one node has been pruned or branched upon, how do we decide upon which node to pick next?
  • Also, if heuristics can provide us, at an early point, with a good lower bound (say, best incumbent solution) then we might swiftly be able to prune (by bound) many nodes in the tree that we would possible otherwise process explicitly, in case a good lower bound was not available.

The choice of nodes has a great impact on the progress of the upper bound (max. problem) during the solution process, and likewise; naturally a smaller solution space (due to many pruned nodes) will increase the likelyhood/"velocity" of improving the upper bound of the problem.

Another point in the process where good heuristics can have an impact on the solution process as a whole is naturally in the pre-processing stage; prior to starting the BAB tree traversal. Really clever heuristics can reduce the solution space substantially, especially if we're attempting to solve a problem that allows apparent refactoring/decomposition into a less complex problem. It's possible that such pre-processing steps are not heuristics (and in so not deactivated when you turn off CPLEX heuristics), per se, but I would say they live in the same family.

Upvotes: 0

Related Questions