Originally posted by: MarcoMojana

Hi,
I'm dealing with a problem that, under particular circumstances, can be decomposed in two (or more) smaller problems. The upper bound for a decomposed problem is the sum of the UB of the subproblems and the same applies to the lower bound. I would like to find a good lower bound, because I need to prove the optimality of a known solution.

I cannot use the branch callback to enforce this decomposition because I can only add constraints/change bounds. Moreover, when CPLEX performs a branch, it assumes that the LB of the parent node is equal to the smallest LB of the children (and not the sum).

I have looked at the solve callback, but it seems that there you can only choose the solver to use. Moreover there is no "preemption" support: you can either solve the node completely or discard it. In my case the subproblems could be difficult to solve and if the sum of their LB does not determine the global LB, there is no point in trying to improve their LB.

I would like that CPLEX would invoke the solve callback multiple times on the same node, in such way I can resume the solver of the subproblems and provide a better LB: is it possible? Does it exists an alternative strategy (branching with one dummy child)?

Thank you!

M. Mojana
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I would like to understand some more details of your procedure.
After decomposing the problem, I guess you are only finding lower bounds for each component and you are not solving each component to optimality, right?
Is the sum of the lower bounds a better lower bound than the LP bound, or are you just decomposing the problems because this is faster than solving the LP relaxation as a whole?

If you can solve some or all components to optimality, then you can just do this in the cut callback and then fix the variables of the solved components to their respective values.

If you use the decomposition to speed-up the LP relaxation solves, then you should use the solve callback, solve the component relaxations, and combine this to get a basis for the full LP relaxation. Then, install this basis in the CPLEX nodelp and solve the nodelp (which should then be done in 0 iterations).

If you can find tighter lower bounds with your decomposition approach but cannot find the optimal solutions of the components, then there is not that much that you can do to speed-up the solving process in CPLEX. In my experience, the lower bounds of the nodes in the search tree are not that important. Basically, the only thing that matters (apart from node selection, which is not that crucial) is whether the lower bound is above or below the incumbent value. If you find a better incumbent, then you can of course prune nodes with larger lower bounds, but since you are already having the optimal solution at hand, this will not happen in your case.

For the overall search, the much more important result of solving the LP relaxation is the x vector of the relaxation solution, because this tells CPLEX how it should branch. So, if your decomposition gives you a better idea of how a feasible solution in the current sub-tree looks like, then it might be useful to derive a branching strategy from this knowledge.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: MarcoMojana

>I would like to understand some more details of your procedure.
>After decomposing the problem, I guess you are only finding lower bounds for each component and you are not solving each component to optimality, right?
Right

>Is the sum of the lower bounds a better lower bound than the LP bound, or are you just decomposing the problems because this is faster than solving the LP relaxation as a whole?
I do it just because it takes less time to solve 2 subproblems of size n that one of size 2n

>If you can solve some or all components to optimality, then you can just do this in the cut callback and then fix the variables of the solved components to their respective values.
Since I need a good LB, I don't want to solve nodes that do not affect the global LB.

If you use the decomposition to speed-up the LP relaxation solves, then you should use the solve callback, solve the component relaxations, and combine this to get a basis for the full LP relaxation. Then, install this basis in the CPLEX nodelp and solve the nodelp (which should then be done in 0 iterations).
That's not my case

If you can find tighter lower bounds with your decomposition approach but cannot find the optimal solutions of the components, then there is not that much that you can do to speed-up the solving process in CPLEX. In my experience, the lower bounds of the nodes in the search tree are not that important. Basically, the only thing that matters (apart from node selection, which is not that crucial) is whether the lower bound is above or below the incumbent value. If you find a better incumbent, then you can of course prune nodes with larger lower bounds, but since you are already having the optimal solution at hand, this will not happen in your case.

What I'm currently doing is:

• cut callback:

if problem is decomposable
solve one of the subproblems
add a cut objfunc >= sum_i LB subproblem i
else
let CPLEX decide
end if

• branch callback:

if problem decomposable
generate only one child identical to the parent
else
generate two children by adding a row in the LPs
end if

In this way I'm sure that a node that represents a decomposable problem is never removed (the child is identical to the parent) and that every time CPLEX want to improve a node LB the correct subproblem is solved. What do you think about this procedure?

Thank you!

M. Mojana
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Typically, constraints that are parallel to the objective function are very bad for the performance of CPLEX. If your objective function is c*x and you introduce a constraint c*x >= c', then you make the LP relaxation of the problem very degenerate because you introduce a probably large dimensional face of identical objective values. This is not so much a problem for the LP solves, but it causes trouble for cutting plane separation and branching variable selection. The issue is that on such a degenerate LP relaxation, adding a cut or branching on a variable would most often not affect the objective function value at all. The LP just moves to a different vertex of the optimal face. And this means, that all of the statistical approaches that CPLEX employs to measure the quality of a cut or a branching will fail, because they look primarily at the impact to the objective function value.

In some cases, though, the advantage of the additional pruning and the better node selection that you will get by encoding your stronger dual bounds directly into the LP may outweigh the issues with branching and cut separation, in particular if you have a custom problem specific branching rule. So, you need to test it on your problem. I would compare against a version that just uses the cut callback, and the only thing that it does would be to prune a node when you find out that your dual bound is above the current incumbent value.

Tobias
#CPLEXOptimizers
#DecisionOptimization