Originally posted by: davidoff

Hello

I'm having a continuous non-convex problem that have a LP part + bilinear inequalities like x2.y1 >= x1. y2

I did not find any way to transfer these constraints into the objecitve function in order to take advantage of non-convex QP in 12.6 (local or global). Indeed, adding the minimization of maxl(0, x1. y2 - x2.y1) to the objective function leads to a not extractable problem

Any comment on this ?

Now, I'm coming back to the implementation of Mc Cormick relaxations adapted to these inequalities. This will lead to a partition of the search in a tree. Indeed, when we solve the LP, we can find a point that violates bilinear inequalities. From this point, we can split the domain of one variable included in this inequality , say x2 and add a choice point : x2 <= x2* or x2 >=x2*+epsilon , where x2* is the current solution

Which type of callback needs to be implemented for that purpose ? I need to add reversible cuts at the end of each run of the continuous LP

Would Goals be easier ?

Thanks

David

Originally posted by: davidoff

I'm investigating goals first

Assume I have one constraint C :  2*x >= 1

Can I add a choice point where I change the linear coefficient of the constraint ? Is this reversible ?

Something like AndGoal(OrGoal( C.setLinearCoeff(x,3) ,C.setLinearCoeff(x,1) , this)

Thanks

You cannot modify existing constraints in a model while it is being optimized, neither with callbacks nor with goals.

The only thing you can do is add additional constraint or tighten variable bounds by means of the branch callback.

The callback to implement this would be the branch callback.

I am not clear what you mean by "reversible cuts". Do you mean you want to add cuts only for the LP solve and remove them immediately after the LP is solved?

I don't see why goals would be easier here. In general I try to stay away from goals since IMO callbacks are usually easier.

Originally posted by: davidoff

Thanks Daniel

 'Reversible' means here that if I explore the right branch, I indeed backtrack on the décisions taken on the left (the first one).

 I tried to implement first goals cause I want to branch on a set of constraints. Indeed, I have a set of 8 range constraints whose coefficients and bounds depend on the local bounds of 4 variables. Now, if for instance, the current value of x is 1.6, I would create the following branching scheme :

x<=1.6-epsilon

change the coefficients of those of the 8 constraints depending on the upper bound of x (which is now set to 1.6-epsilon). If let's say 2 constraints are impacted, we can say than this left branch is made of 3 constraints (these 2 + the new upper bound constraint on x)

I don't remember if a branch callback would allow that branching scheme ?

The goals seemed to be more adapted to this branching scheme since there is an api goal (in Java : IloCplex.constraintGoal(IloRange[]) ). However, it generates a core dump when I generate this new set of constraints.

Goals are implemented using callbacks. So anything that is possible with goals should also be possible with callbacks (and in my experience callbacks are easier to use than goals).

In order to create the right branch you can use function

IloCplex::BranchCallbackI::makeBranch(IloConstraintArray,IloNumVarArray,IloNumArray,IloCplex::BranchDirectionArray,IloNum,NodeData)

This function allows creation of a new branch that is specified by additional constraints and/or bound changes. The constraints and bound changes are only enforced on this new branch, so they will not affect anything on the left branch.

Originally posted by: davidoff

Thanks Daniel

I'll try the branch call back instead

note that with goals, I had to add a dummy integer variable in the model in order to use goals, since goals are only effective on Mixed Integer Problems, which is not the case of my initial problem.

I guess I will have to do the same with the branch call back (e.g branch call back are supposed to control the branching scheme for a mixed integer problem, not a continuous one) ?

Right, you have to force CPLEX do view your problem as an integer programming problem, otherwise it will not start the B&B algorithm. One easy way to do that is to add a dummy integer variable.

You may also want to add an incumbent callback that rejects any incumbents CPLEX proposes. Otherwise CPLEX may fix that dummy variable, claim this solution optional and never start B&B either.