Originally posted by: Michael_D

What about the following procedure to circumvent Big-M-constraints of the form
x_i == 1 => a_iy <= b_i
where x_i is a binary variable, a_i a row vector, y a vector of continuous variables and b_i a scalar:

Start the optimization with those constraints that contain only x variables.
Each time the LP relaxation is solved, when/before/after adding Cplex and/or user cuts, check for each binary variable x_i whether its lower bound at the current branch-and-bound node is strictly positive.
If so, add the corresponding constraint a_iy <= b_i as a local, non-purgeable cut at the current branch-and-bound node.
This is because in any feasible solution in the subtree rooted at this node, the variable will have value 1 and thus the constraint will have to be fulfilled by any solution in the subtree.

Is this (more or less) the way the logical constraints in Concert C++/indicator constraints in the C API work? If not, what exactly do they do, and do you think that it is worthwhile to try out the above procedure?

A related question: Is it safe to add a local, non-purgeable cut in the cut callback using addLocal() if this cut renders the resulting LP infeasible? Will this simply lead to the pruning of the current branch-and-bound node? Or might this break internal structures Cplex has built up during the solution and result in undefined behaviour?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> Michael_D wrote:
> What about the following procedure to circumvent Big-M-constraints of the form
> x_i == 1 => a_iy <= b_i
> where x_i is a binary variable, a_i a row vector, y a vector of continuous variables and b_i a scalar:
>
> Start the optimization with those constraints that contain only x variables.
> Each time the LP relaxation is solved, when/before/after adding Cplex and/or user cuts, check for each binary variable x_i whether its lower bound at the current branch-and-bound node is strictly positive.

You'll want more than just strictly positive, since 0 < x < epsilon could mean that x is really supposed to be zero and you've picked up some rounding error.

> If so, add the corresponding constraint a_iy <= b_i as a local, non-purgeable cut at the current branch-and-bound node.
> This is because in any feasible solution in the subtree rooted at this node, the variable will have value 1 and thus the constraint will have to be fulfilled by any solution in the subtree.

I don't see this. The fact that x > 0 in the LP relaxation does not imply that every integer feasible solution in this node has x = 1, nor does it imply that the optimal solution does (even if x > 0 means x is big enough that we can rule out rounding error).

What you could do is force a branch on x (x = 0 in one child, x = 1 in the other) and add the constraint to the second child. It's not clear to me that this is necessarily a good way to make branching decisions, though.
>
> Is this (more or less) the way the logical constraints in Concert C++/indicator constraints in the C API work?

No, I don't think so.

> If not, what exactly do they do,

I think it's a mix of big M and branching decisions (see Tobias's first answer on this thread).

> and do you think that it is worthwhile to try out the above procedure?

MIPs are perverse, so it might be better on some (assuming you add the branching piece I mentioned above -- as stated I think it will produce wrong answers) and worse on others. The big concern for me would be that you get no benefit from the indicator constraints in computing bounds until you add them (and adding the same constraint in various nodes will cost some overhead). You don't get much benefit from "big M" constraints with quasi-infinite values of M, either, but sometimes you can produce reasonably tight choices for M and get some benefit from leaving the constraints in the original model.
>
> A related question: Is it safe to add a local, non-purgeable cut in the cut callback using addLocal() if this cut renders the resulting LP infeasible? Will this simply lead to the pruning of the current branch-and-bound node? Or might this break internal structures Cplex has built up during the solution and result in undefined behaviour?

It's safe, and the node will indeed be pruned if infeasible, provided that you use a LazyConstraintCallback and not a UserCutCallback. (The former is allowed to lop off seeming feasible solutions; the latter is not.)

If you're having problems with this type of constraint (and you don't get good results using CPLEX indicator constraints), you might look up "combinatorial Benders cuts".

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: Michael_D

Thanks a lot, Paul, for your detailed answer. The Cplex/Concert logical constraints did indeed not work well for my model, so these combinatorial Benders' cuts will get a chance.
#CPLEXOptimizers
#DecisionOptimization