Originally posted by: chrysg

Dear All,

I am developing a Concert application and am interested in branching using custom branching cuts that are not of the type "single_variable <=0 or >=1."
Given that I have multiple options at hand, I would like to implement some kind of look-ahead LP-testing. By this I mean to solve (completely or partially) the LP that would result from each of the hypothesized branches, and decide after I have seen the effect of each of the options.
This is similar in concept to the strong branching approach that CPLEX features, although to my understanding this is limited to branching on a single variable that is automatically selected by CPLEX -- not really compatible with a Branch Callback.

Are there any suggestions on how to best achieve this?
Do I have to re-declare at each iteration the complete model (with appropriate fixations), or can I somehow invoke a temporary copy of my main model?
Is there a way to utilize the built-in "strong branching engine" with custom branching cuts?

Thanks,

Chris
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Unfortunately, I doubt that such an advanced strategy is possible from Concert. Basically, you need to work on the presolved model rather than the original model in your branch callback, but this is not possible in Concert.

If you would be willing to switch to the C API, then I can explain how you can do what you want.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: chrysg

Tobias, thanks for your response.
This is how my Concert design looks so far:

• Every time I have a user global cut that I need to add to my model, I also add it in a global array (of type IloRangeArray or some other suitable form that will allow me to recreate the cut in question) where I store all global cuts.

• I do not have user local cuts in my application, but in this case I would envision a similar structure that would be private to the goal class that is used to spawn every new node. By initializing this array to the array of the parent node, we could maintain a list of local cuts relevant to a given node. Alternatively, there could be a global array of local cuts and pointers from each goal instance to the cuts that are relevant.

• Cutting planes automatically added by CPLEX I have no way of accessing...

• Now, whenever I need to perform LP-Testing, I declare a separate copy of the original (unpresolved root node) model (with integer variables being continuous), add the global and local cuts through the structures I have in memory, add the hypothesized branching rule I want to test and solve the model. I replace each branching rule, one by one, solving the model each time and, in the end, free up all this auxiliary memory and move on with executing the branching rule of choice.

(If CPLEX cuts are to be disabled...) the above do the job but even then seem kind of inefficient, particularly the requirement to keep all cuts in memory twice (once in the CPLEX structures, and once in my global array).
Although I would have to let go the concept of Goals, I am contemplating switching to the C API to avoid all these inefficiences. It is, anyways, my general understanding (please correct me if I am wrong) that the C API has more complete querrying procedures for each node, allowing you to control callback with more advanced ideas.

Would appreciate it if you could elaborate a little bit on how one can implement this LP-testing thing more efficiently through the C API.

Thanks,

Chris
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

For starters, the C-API would give you access to the LP actually solved at the current node. This LP would already contain all global and local cuts that CPLEX added.
Note that (unless you disabled presolve) this nodelp would also contain all presolve reductions so that you can separate your cuts on the presolved model.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Chris,

what you are proposing to do in Concert should work correctly. But as you pointed out, it will be a major performance bottleneck.
The main reason is not so much the duplication of the cuts in your own data structures. The issue is the LP solving.

When you do what you suggest, it means that CPLEX needs to solve all of these LPs from scratch each time. This is typically much slower than starting from an optimal basis and resolving the LP with the dual simplex after having added some rows or tightened some bounds.

In order to speed-up your Concert approach, you should solve the root relaxation once and store the basis. You should also keep this LP copy instead of throwing it away and constructing it again at every node.
Then, whenever you apply your strong branching procedure, first load in the optimal basis into your LP copy, then apply all necessary changes to reach the current node, and solve the LP. Then, store the new optimal basis in local arrays. Then, start your strong branching loop:
1. load in the optimal basis,
2. add the additional branching constraints,
3. solve and evaluate the LP,
4. remove the additional branching constraints,
5. repeat 1-4 until all branching candidates have been evaluated.
Finally, remove all local constraints to recover your root LP relaxation.

Of course, you can even do more advanced stuff like storing the local optimal bases at every node in the search tree, which would speed-up the initialization procedure you have to apply before going into your strong branching loop.

But overall, even this approach is likely to perform much worse than what you can easily do in the C API. The reason is that in the C API you can access and temporarily manipulate the local LP relaxation directly.

In a C API branch callback, you would query the nodelp with CPXgetcallbacknodelp(). Then, query the optimal basis and dual norms with CPXgetbasednorms(). Then do:
1. load in the basis and dual norms with CPXcopybasednorms(),
2. add the additional branching constraints with CPXaddrows(),
3. solve the LP with CPXdualopt() and query solution information with CPXsolution(),
4. remove the branching constraints with CPXdelrows(),
5. repeat 1-4 until all branching candidates have been evaluated,
6. load in the basis and dual norms with CPXcopybasednorms(),
7. call CPXdualopt() to restore the internal LP state that CPLEX needs to proceed.

I think this should work, but maybe CPLEX does not like you to work directly on the nodelp. If this is the case, then you just need to copy the nodelp locally and work on this local copy instead (which then saves you steps 6 and 7).
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: DianaHuerta

Hi Chysg

#CPLEXOptimizers
#DecisionOptimization

Not sure if people are still around after 5 years, so I am jumping in :-)

This issue has been discussed several times on the CPLEX Forums and the problem is exactly what you guessed: the environments. You cannot add an IloRange that was created using a callback-local environment to an IloRangeArray that was created using the global environment. And there are more technical issues concerning the environments.

The solution is: do not use IloRange or IloRangeArray to store the cuts. You can for example use a class like the following (untested code!) to represent a cut:

#include <ilcplex/ilocplex.h>

#include <map>
#include <list>
#include <vector>

/** Representation of a linear constraint that is sufficiently independent
 * of an IloEnv instance.
 */
struct LinearConstraint {
   /** A non-zero coefficient. */
   typedef std::pair<IloNumVar, double> NonZero;
   typedef std::list<NonZero> NonZeroList;

   /** Create an empty linear constraint. */
   LinearConstraint() : coefs(), lb(-IloInfinity), ub(IloInfinity) {}

   /** Create a linear constraint from an IloRange.
    * The constructor creates a linear constraint that represents r but
    * is not bound to a local environment.
    */
   LinearConstraint(IloRange const &r) : coefs(), lb(r.getLB()), ub(r.getUB()) {
      for (IloExpr::LinearIterator it = r.getLinearIterator(); it.ok(); ++it)
         coefs.push_back(NonZero(it.getVar(), it.getCoef()));
   }

   /** Convert this linear constraint to an IloRange.
    */
   IloRange toRange(IloEnv env, char const *name = 0) const {
      
      IloExpr expr(env);
      for (NonZeroList::const_iterator it = coefs.begin(); it != coefs.end(); ++it)
         expr += it->first * it->second;
      IloRange rng(env, lb, expr, ub, name);
      expr.end();
      return rng;
   }

private:
   NonZeroList coefs;
   double lb;
   double ub;
};

Then you define a global

std::vector<LinearConstraint> globalCutList;

and use that to store your constraints (remember to use appropriate locks if you are running multi-threaded since callbacks may be invoked in parallel). The LinearConstraint class described above should allow you to back and forth to IloRange easily.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: DianaHuerta

 

#CPLEXOptimizers
#DecisionOptimization