Originally posted by: clemsonmacrone

I am working on a customized branching strategy using branch callback for ilog cplex.

The problem is an integer based multicommodity flow problem that minimizes a single scalar multiple of the capacities
letting x_j the set of arcs for each commodity, A be the ArcIncidence, b_j be the origin destinations vector j, c be the capacity vector and a be the single scalar multiple.

min a
s.t.
Ax_j = b_j for all commodities j
(/sum_i x_i) - ac = 0
x= {0,1}

My Problem is that when I use branch callback, cplex does not recognize when the solution is feasible. This is because the relaxation of the system has many alternate optimal solutions. For example, the relaxation will have every path for every commodity feasible (each arcs along the path has value 1) but will also have some fractional arc cycle that does not affect the objective function. This causes cplex to think the solution is not optimal when in fact it is.

I have written the code to recognize when this happens and identify the feasible paths for each commodity. I need a way to tell cplex that this is a feasible solution and treat the obj value as the new upper bound in the search tree.

I have tried prune() but I think that just deletes the node I am on.
I have also tried making a single branch and setting all other arcs not on the feasible paths equal to zero but I haven't figured out how to make ilog select that branch next. Also I would think that their would be a better way than this.

Any help would greatly appreciated
Thanks
Cam
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> clemsonmacrone wrote:

>
> I have written the code to recognize when this happens and identify the feasible paths for each commodity. I need a way to tell cplex that this is a feasible solution and treat the obj value as the new upper bound in the search tree.
>
One approach is to add a heuristic callback. Have the heuristic callback get the current solution (via getValues), use your existing code to polish the LP solution into a valid MILP solution where relevant, and in such case inject the polished solution as a new incumbent.

If the code to recognize and polish solutions has to be in the branch callback for some reason, you can still do this by having the branch callback put the polished solution in a holding area (queue). The heuristic callback then checks the queue each time it's called and, if the queue is nonempty, pops the single solution in the queue and injects it.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization