Originally posted by: pamayadque

Hi,

I am working with Cplex Concert Technology for Java. I have got a question and I would like to know if someone could help me to find a solution.

I am implementing a model that solves a linear program (basically a minimum cost flow problem) with some side constraints difficult to express into linear constraint. However, some of those constraints can be forced by changing the bounds on de flow variables once the solution obtained is probed not to be feasible. What I would like to do is the following.

1. Solve the Min cost flow problem
2. That solution would be the node 0 of a search tree.
3. Changed the bounds of some variables (or adding constraints on the flows of some variables) to fixed its value for example to cero. These would define two children one in which the flow in a specific arc is cero and one in which that flow is not fixed.
4. Solve the problem at the child level (it is still a MCFP)
5. Go to Step 3 and repeat the procedure as in a Typical Branch and Price problem.

I have read the information related with callbacks and goals. However, the first difficulty I have found is how to force Cplex to start a tree when my problem does not have integer variables.

Does anybody know whether this is possible in Cplex, or should I consider to use a different approach to administrate the search tree and use Cplex to solve each node?

hope I have Explained myself well…Thanks in advance
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

At least in the C API you can simply change the problem type to MIP, even though all variables are continuous. Then you will get a search tree (obviously, if you would not have any callbacks that reject solutions, the problem will be solved at the root node).
I don't know exactly, whether the same can be done through Concert.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

In order to use delayed constraint generation for a pure LP register a LazyConstraintCallback. Look at this thread. It talks about how to do that.
However, this will only give you a loop in which you can do delayed constraint generation based on the current solution CPLEX has. Do you really need to branch during your algorithm?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> pamayadque wrote:

> 3. Changed the bounds of some variables (or adding constraints on the flows of some variables) to fixed its value for example to cero. These would define two children one in which the flow in a specific arc is cero and one in which that flow is not fixed.

I'm a bit confused. How would the second child (flow not fixed) differ from the parent?

I think you can use the CPLEX branching mechanism by supplying an incumbent callback (to decide whether to accept an LP's solution or split the node) and a branch callback (to create the children), but it depends in part on what the second child should look like.

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

Originally posted by: pamayadque

Hi,

Thanks for ur answers. I am already implementing the algorithm using goals. (It is not ready yet)

Paul, you are right. However, I am relaxing some other constraints, I did not mention that when I posted. But that was a great remark, I will be sure that I got a proper branching rule.

Thanks again

Pablo
#CPLEXOptimizers
#DecisionOptimization