Originally posted by: skkim

Guys, this is sort of a report on my trial on branchcallback for the project I have been working on. I hope this note could be useful for somebody. The basic algorith is branch and price and the solution process is as follows. I had developed BNP for my thesis, and I think it should work, but for the last couple weeks' effort fail me in doing so.

1. Initialize the master LP.

2. Solving the master LP until no vaild new column appears.

3. After the first BB tree node is done, I used conversion to convert MLP to a MIP.

4. Here I added branchcallback function. Inside the branchcallback function,

     4-1. there is a method to solve the MLP, but I made this method skipped at the root node since the step 2 solves the rootnode.

     4-2. based on results of step 3, two makebranches are executed. Here the branch directions are branchdown as all selected branching variables should be zero.

5. the process goes through nodecallback function, and gives the next node.

6. It comes to the branchcallback function.

    6-1. In this case, it goes through the method to solve the MLP. ** Here is the first problem. Since I did makebranch at step 4, some of columns should be fixed to zero, but  it didn't happen. But don't get me wrong. For BNP, I used this approach for my thesis and it worked out well though I used JAVA, not C++ though. ***

----------------------------------------------------------------------

Not only this process, but also did I try 4 or 5 other processes to make this work. If you want, I could upload those scenarios too.

I suspected it is likely I chose wrong objects for makebranch, and I tried many ways I could think of, but any of them still didn't work.

So, right now, I am going to use a very unproductive way - creating BBTree, BBNodes, and managing BBTree by myself, not by Cplex.

Even though I really don't like this due to possible ineffectiveness, long and painful code structure, etc, at least I have a design on how to implement.

Later after making this work, I will come back to use branchcallback function. Let me know if you have any other thought. I can tell you if I have tried or not. If I didn't, I can go for it later.

Why do solve the MLP explicitly in the branch callback? When the branch callback is invoked, CPLEX has already solved the relaxation at the current node, so there is no need to solve the MLP again.

If you still want to solve the MLP, how do you do that? Do you use a new IloCplex instance for that? You cannot use the IloCplex instance that invoked the branch callback for that since this is unsupported behavior.

How did you conclude that no columns are fixed to zero? If you re-solve the original MLP then of course no columns are fixed to zero (the original model instance is not modified by CPLEX during B&B). However, calling the branch callback's getLBs() and getUBs() methods you should be able to find some variables that have both bounds set to zero.

In summary, from your description I think you are doing some very strange (if not wrong) things with CPLEX. It seems to me as if there is a good chance that you may be using CPLEX in the wrong way here. Maybe trim down your branch callback to the essential code and show this here.

Originally posted by: skkim

Why do solve the MLP explicitly in the branch callback? --> so solving the MLP is for adding more columns at eachBB node. So, each node may have different MLP to start. That is the strategy of the BNP algorithm.

Do you use a new IloCplex instance for that? You cannot use the IloCplex instance that invoked the branch callback for that since this is unsupported behavior. --> In fact, I started with using the same IloCplex instance, but it didn't work out. And I created a new IloCplex instance, but it didn't work out either. so, I came back to use the same IloCplex instance again and tried to use different ways for branchcallback function.

How did you conclude that no columns are fixed to zero? If you re-solve the original MLP then of course no columns are fixed to zero (the original model instance is not modified by CPLEX during B&B). However, calling the branch callback's getLBs() and getUBs() methods you should be able to find some variables that have both bounds set to zero. --> that's what I did. using getLBs and getUBs. And also, I exported the LP file both inside  the MLP solving method and inside the branchcallback function, but both LP files also show no change.

there is a good chance that you may be using CPLEX in the wrong way here.. -> that's one of many doubtful points I have had.

 trim down your branch callback to the essential code and show this here. --> let me put it on the following reply. Thanks.

OK, now I understand a little better.

I think the fundamental problem here is that you cannot add columns to a problem while CPLEX is solving this problem. You can add constraints (as cuts or lazy constraints) but cannot add new columns. While CPLEX is solving a problem the number of columns in that problem must stay fixed. So if you want to do real branch-and-price (potentially add new columns at each search tree node) then you will have to maintain the search tree yourself and cannot use the CPLEX search tree.

Originally posted by: skkim

Wow.. that changes the whole thing.

I thought this is a little different from solving cutting stock problem.

In the cutting stock problem, we are adding new pattern at each iteration, until any valid pattern is found.

Once we are done with the root node, if we find fractional solution, we fix some variables, and move to the next node.

At the next node, we may be able to find a new pattern, which means a new variable. Isn't it? Or do we just keep the same pattern we found at the root node?

You are right, in branch and price you may find a new pattern at each node. And that is why you cannot use CPLEX directly here (it does not allow adding new variables during the search).