Originally posted by: BastianMeier

Hello @all,

I try to implement the GAP (generalized assigment problem) as described in http://www2.isye.gatech.edu/~mwps/publications/or45.pdf with Cplex 12.2.

The main idea is to branch on the integer variables in the GAP-model but to solve another problem on each node (which is a Dantzig-Wolfe decomposition i already have implemented) based on the branching information of these node.

This means for all nodes i want to solve the lp-relaxed problem by myself and "inform" the branching algorithm of the solution. Following the description of the SolveCallback i can influence how the problem on each node is solved and even submit an solution for the lp-relaxed problem. In practice it did not work. I cannot access the node to get information on branching. Also i wasn't able to submit a solution using setVectors() and useSolution() - Java API.

The example provided with cplex and the reference manual did not help. Also the discussion at http://www.mathkb.com/Uwe/Forum.aspx/op-research/1413/Branch-and-Price-Using-ILOG-Cplex-9-1-and-Solver-6-1 did not solve my problem. We also tried and failed using SCIP to perform Branch and Price because we weren't able to branch on the original problem while optimizing the DW-problem.

My questions are:
1. Did i have a wrong interpretation of SolveCallback? In my opinion it is the only Callback which is fired before the lp-relaxed problem is solved.
2. Can i use SolveCallback to solve the lp-relaxed problem by myself and transfer the solution to the node? If yes, how to read the branching information out of the node?
3. If my interpretation is wrong, is there another Callback to solve GAP as described above?

Thank you for your help,
Bastian
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I am not used to the Java API, so I discuss C here instead. I hope that it is relatively easy to translate this to Java.
Here is the relevant part from the C API documentation:

---

ILOG CPLEX calls the solve callback before ILOG CPLEX solves the subproblem defined by the current node. The user can choose to solve the subproblem in the solve callback instead by setting the user action argument of the callback. The optimization that the user provides to solve the subproblem must provide a CPLEX solution. That is, the Callable Library routine CPXgetstat must return a nonzero value. The user may access the lp pointer of the subproblem with the Callable Library routine CPXgetcallbacknodelp.

---

In other words: the solve callback provides a way to use an alternative algorithm to solve the LP relaxation at the current node. But in the end you have to install this solution into the CPLEX LP solver.
This means, you cannot solve a different relaxation; you can only use a different algorithm to solve the LP relaxation. For example, you could implement some algorithm based on decomposition that has nothing to do with the simplex algorithm to find a solution to the LP relaxation. Then, you would use this solution as a warm start for CPLEX primal or dual simplex (in Java by means of setvectors()), and finally call the simplex solver to construct the necessary solution information inside CPLEX. Ultimately, everything you do in the solve callback is just a way to provide a good (or even optimal) starting point for the CPLEX LP solver in the hope that this combination will solve the nodelps faster than the standard dual simplex.

If you really want to use a different relaxation than the canonical LP relaxation for your problem, you need to use a different framework. CPLEX is really hard-wired to the LP relaxation. SCIP can use other relaxation types, at least in the newer versions of SCIP. Gerald Gamrath from ZIB successfully implemented a Dantzig-Wolfe decomposition which I think should in principle be similar to what you want to do. You may want to ask him directly or post your question again on the SCIP mailing list.

You say that you want to solve the LP-relaxed problem by your solve callback. If this is true, then you can use CPLEX. As far as I understand the Java API, you need to first call setVectors(), then solve(), and then useSolution(). Maybe, you just forgot the solve() call.

Since the object oriented APIs always work in the original problem space, I think that you cannot access the nodelp (which is defined in the presolved space). This would be needed to query the branching decisions (just compare the local bounds to the global bounds). But as I said, I do not know the Java API very well. Maybe, someone else can jump in and give you some more hints. It could be that you need to switch to the C API in order to be able to query the branching decisions. In C, this is definitely possible.

Hope this helps,

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Branching information is not directly available in Java and C++ APIs. However, it is rather simple to keep track of that. Is was dicussed for example in this thread.
Unfortunately, the approach there builds on the nodeData user object that can be specified for each node and this data cannot be queried from a SolveCallback. But maybe it is possible to construct something with the help of the NodeCallback. The NodeCallback can query the nodeData object and selects the next node to be processed.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: BastianMeier

Thanks to both of you.

I've looked for a possible implementation.

BranchCallback can be used to pass branching information to every node using getBranch(a,b,c) and setBranch(a,b,c, BranchingInfoForNodeArray).

As Daniel mentioned SolveCallback did not know which Node is currently active.

Because i want to use the Cplex-Branching algorithm NodeCallback cannot be used to provide information about the next node to be chosen(at least i did not find a method to get the node cplex will choose). On multicore systems there are several possibilities at the same time because of which the information cannot be transported to a global variable outside the callback.

Since we cannot pass the node information to the SolveCallback it seems that my approach will not work using CPLEX.

Maybe i can find a tool to perform Branching in Java and solve the lp-relaxed models using CPLEX and my Dantzig-Wolfe-implementation.

Since i cannot pass the node information to the SolveCallback it seems that my approach will not work using CPLEX alone. If anyone has an idea how it will work with CPLEX i would be thankful for a message.

So far i mark this thread solved. Thanks againt to Tobias and Daniel
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I am very sorry :-( I misread the documentation of the SolveCallback.
It does provide access to the node-specific data via function getNodeData() inherited from ControlCallbackI.
So doing what you want is possible:

• store branching information in the node data using a BranchCallback,
• retrieve that information via getNodeData() in the SolveCallback.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: BastianMeier

Hello Daniel,

Referring to MIPCallback ControlCallback and SolveCallback directly inherit from MIPCallback.

ControlCallback provides getNodeData(), but it cannot be used in SolveCallback because it is no Subclass of ControlCallback.

I also checked the library for Cplex 12.2 to ensure i did not miss an important update.

Did i have a wrong library/version/documentation?

Basti
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Ah, you want to do it in Java. Sorry, I assumed you were doing C++.
In the C++ API SolveCallback is derived from ControlCallback but in Java it is derived from MIPCallback.
So I'm afraid you are right. In C++ you can access the user object from the SolveCallback but in Java you can't.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: BastianMeier

I'm not familiar with C++. Is there a special reason for the difference between Java and C++? Maybe we have to change to C++.

Thank you for your help.

Basti
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I cannot think of a reason at the moment. It might be a technical subtlety. It might as well be a bug in the design.
I will try to figure that out but it won't help you anyway :-(
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: BastianMeier

If it is a bug in design it may be changed with a future release. But for now it won't help. What a pity.

THX,

Basti
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Actually, looking a little closer at the source code I am pretty sure that it is a bug in the design.
The node data information is actually available in the callback but just not accessible. I think there is a way to write a solve callback that allows you to access this information.
If you are interested in this please send me a message to daniel(dot)junglas(at)de(dot)ibm(dot)com and I will tell you how to do that.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Dear Bastian,

I've found this thread in a google search and even outdated it is related with some questions that I'm considering right now. Did you have success implementing branch and price with cplex? What language did you used? C++ or Java?

I'll will begin an effort to implement a BP algorithm to solve a IP with constraints close to the GAP (However, my my master problem is of form Ax <=b where A is a full matrix) and would appreciate to hear
any comments about your experience with cplex with those languages.

Best Regards
Tiago
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: BastianMeier

Hello Tiago,

 

sorry for my late reply. We stopped working on Branch&Price and turned towards finding special heuristics for our problem. This was because we got poor results implementing Benders decomposition on our problem. Also Uwe Padberg mentioned in his thesis ("Stochachstische Optimierung von Erdgasportfolios im mittelfristigen Zeitbereich") that his attempts to use decomposition approachs to reduce solution times failed.

Currently i am starting a new project with students to implement a Branch&Price-Strategy on a subset of the energy portfolio optimization problem where better results might be possible. We are at the beginning, discussing algorithms, programming languages to be used and so on, so yet there are no experiences to communicate and no decisions on the programming language are made. Maybe in a year we will have first calculational results.

I'd like to use Java but so far i am not sure that this is possible. Unfortunately, so far i have no hints and comments on B&P with Cplex for you.

Godspeed to you,

 

Bastian

#CPLEXOptimizers
#DecisionOptimization