Originally posted by: SystemAdmin

Hello,

I have a quick question regarding the indicator constraints. In the LP file format, are the symbols <-> and -> implemented as "if and only if" and "if" constraints, respectively?

For example, is the following constraint

y = 1 <-> x <= 0

where y is a binary decision and x is a continuous decision, roughly translates into the following set of big M constraints??

x <= M(1-y)
x >= (m - epsilon)y + epsilon

Here M is a large constant, m is a large negative constant and epsilon is a small positive number.

Thanks for your help.

Kind regards,
Angelos
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> AngelosGeorghiou wrote:
> Hello,
>
> I have a quick question regarding the indicator constraints. In the LP file format, are the symbols <-> and -> implemented as "if and only if" and "if" constraints, respectively?
>
> For example, is the following constraint
>
> y = 1 <-> x <= 0
>
> where y is a binary decision and x is a continuous decision, roughly translates into the following set of big M constraints??
>
> x <= M(1-y)
> x >= (m - epsilon)y + epsilon
>
> Here M is a large constant, m is a large negative constant and epsilon is a small positive number.
>
> Thanks for your help.
>
> Kind regards,
> Angelos

I believe your translation is correct. You need constraints that specify

y = 1 --> x <= 0 and
x <= 0 --> y = 1

The first of these is straightforward and translates to x <= M(1-y) as you said.
The second can be modeled via its contrapositive:

y = 0 --> x > 0

which translates to x >= (m - epsilon)y + epsilon as you said. You could also
model the original condition x <= 0 --> y = 1 directly with something like

My >= -x + epsilon

which is a bit simpler and avoids the round off prone operation of subtracting
the small epsilon from the large (in absolute terms) m.

This also illustrates where indicator variables and their associated branching
can avoid numerical issues. The big M formulation requires not only a large
value for big M but a small value for epsilon that much be chosen correctly so
they enforce the intent of the constraint. So, not only do you need to choose
M properly, but you also need to choose epsilon properly. Indicator constraints
will at least avoid the usage of big M. However, the <-> operator will typically
require CPLEX to internally select an epsilon value, as it usually requires some
sort of strict inequality in one of the implications, and that ultimately requires
an epsilon value.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thank you for your quick response.

I am trying to use indicator constraints to enforce sets of constraints rather than individual constraints.

An illustrative examples could be

z = 1 <-> {x+y = 0, x-y=0}
z = 0 <-> {2x+y = 1, x-2y=1}

where z is a binary variable and x,y are continuous variables.

The way I have implemented it is the following:

for constraint z = 1 <-> {x+y = 0, x-y=0} I have

Auxiliary_z_1 = 1 <-> x+y = 0
Auxiliary_z_2 = 1 <-> x-y = 0
z = 1 <-> Auxiliary_z_1 + Auxiliary_z_2 = 2;

where Auxiliary_z_1 and Auxiliary_z_1 are binary variables.

Similarly for constraint z = 0 <-> {2x+y = 1, x-2y=1}.

The results are as expected but the problem takes a lot of time to be solved. Looking at the cplex log file I can see that the problem consists of a large number of binary variables, many more than the number of binary variables that I used to construct the problem. I suspect that the extra number of binary variables come from the reformulation of the indicator constraints, namely from the fact that I am trying to satisfy equality constraints, e.g. x+y=0. Unfortunately, I cannot reformulate the problem in a way that avoids equality constraints. Moreover, I am not sure if my formulation of the problem using the indicator constraints is the most efficient way to implement these constraints.

Do you think there is a way to get around this problem and improve solution time?

Kind regards,
Angelos
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> AngelosGeorghiou wrote:
> Thank you for your quick response.
>
> I am trying to use indicator constraints to enforce sets of constraints rather than individual constraints.
>
> An illustrative examples could be
>
> z = 1 <-> {x+y = 0, x-y=0}
> z = 0 <-> {2x+y = 1, x-2y=1}
>
> where z is a binary variable and x,y are continuous variables.
>
> The way I have implemented it is the following:
>
> for constraint z = 1 <-> {x+y = 0, x-y=0} I have
>
> Auxiliary_z_1 = 1 <-> x+y = 0
> Auxiliary_z_2 = 1 <-> x-y = 0
> z = 1 <-> Auxiliary_z_1 + Auxiliary_z_2 = 2;
>
> where Auxiliary_z_1 and Auxiliary_z_1 are binary variables.
>
> Similarly for constraint z = 0 <-> {2x+y = 1, x-2y=1}.
>
> The results are as expected but the problem takes a lot of time to be solved. Looking at the cplex log file I can see that the problem consists of a large number of binary variables, many more than the number of binary variables that I used to construct the problem. I suspect that the extra number of binary variables come from the reformulation of the indicator constraints, namely from the fact that I am trying to satisfy equality constraints, e.g. x+y=0. Unfortunately, I cannot reformulate the problem in a way that avoids equality constraints. Moreover, I am not sure if my formulation of the problem using the indicator constraints is the most efficient way to implement these constraints.
>
> Do you think there is a way to get around this problem and improve solution time?
>
> Kind regards,
> Angelos
I recommend two approaches to improving solution time, one with your existing
formulation and another with an alternate formulation.

Regarding the existing formulation, take a look at the node logs and assess whether
the slow performance comes from lack of progress in the best integer or best node
values. Then, set the appropriate CPLEX parameters based on where the lack of
progress comes from. For more information on that, have a look at the technote
at http://www-01.ibm.com/support/docview.wss?uid=swg21400023 for starters. If that
doesn't help, post to this thread again, and I will provide some additional info that
you might find useful.

Regarding alternate formulations, while I agree that your formulation above correctly
enforces the conditions you are trying to model, it ultimately involves 3 if and only
if indicator constraints for each condition you want to model. Anything you can
do to reduce the number of indicator constraints might help. I think you could
reduce it down to one by using slack and surplus variables on each equality constraint
and then using an indicator to force all the slack and surplus variables to 0 to
enforce your constraints, e.g.

x + y + u1 - v1 = 0
x - y + u2 - v2 = 0
u1, u2, v1, v2 >= 0

z = 1 <-> u1 + v1 + u2 + v2 = 0

I think that works. Clearly if z = 1 it forces both of your equality constraints
to hold. If z = 0, then u1 + v1 + u2 + v2 != 0, so at least one of your constraints
does not hold.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hello,

Thank you very much. Your suggestions are very helpful.

I have a question regarding the solution time of these MILP problems. I am not quite sure I can interpret the cplex.log file correctly. Please find attached the cplex.log file for one of the problem instances I am considering.

My question is as follows. In my understanding, the column "Objective" reports the objective value at the current node, the column "Best Integer" is the best integer feasible solution, and the "Best Bound" reports the best lower bound for the MILP. Is this correct?

As you can see in the log file, the "Best Bound" remains constant, and equal to the optimal value, through out the algorithm, while the "Best Bound" gradually decreases to the optimal solution (the problem is a minimization). In this example, I have used the default emphasis parameters, and I have also supplied to the solver a list of initial solutions.

I can't quite understand this behavior. Typically, the upper bound converges to the optimal solution very fast and the lower bound takes a lot of time to converge. Why is the problem behaving in this way? Does this has something to do with the indication constraints?

I have tried all the permutations of the emphasis parameters with little success. Most of the time the default parameters seem to be the most robust. Do you have any suggestions on how to accelerate the algorithm? This behavior is the same for most problem instances that I consider. I don't necessarily look for the global optimum but if I stop the algorithm prematurely, the quality of the solution is quite far from optimal, since the "Best Integer" has very slow convergence.

Kind regards,
Angelos
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> AngelosGeorghiou wrote:
> Hello,
>
> Thank you very much. Your suggestions are very helpful.
>
> I have a question regarding the solution time of these MILP problems. I am not quite sure I can interpret the cplex.log file correctly. Please find attached the cplex.log file for one of the problem instances I am considering.
>
> My question is as follows. In my understanding, the column "Objective" reports the objective value at the current node, the column "Best Integer" is the best integer feasible solution, and the "Best Bound" reports the best lower bound for the MILP. Is this correct?

Exactly.

>
> As you can see in the log file, the "Best Bound" remains constant, and equal to the optimal value, through out the algorithm, while the "Best Bound" gradually decreases to the optimal solution (the problem is a minimization). In this example, I have used the default emphasis parameters, and I have also supplied to the solver a list of initial solutions.
>
> I can't quite understand this behavior. Typically, the upper bound converges to the optimal solution very fast and the lower bound takes a lot of time to converge. Why is the problem behaving in this way? Does this has something to do with the indication constraints?

The indicator constraints could indeed be involved here. While the indicator constraints have an advantage as previously discussed regarding
better numerics than the big M formulation, their primary disadvantage is
that when CPLEX relaxes an indicator constraint in a node relaxation for
your MILP, it does so by removing the indicator constraints completely.
This compares unfavorably with relaxing of integer variables, where the
variables remain in the problem (along with their bounds), but are now
continuous. Now, if you use a big M formulation instead of an indicator
formulation and have to use very large big M values, then your big M formulation will have node LP relaxation essentially as weak as the indicator constraints.

Given this background, the question you need to ask is whether you can
formulate your model with modest size big M values. In other words, for
the variables the constraints of interest here, do you know that their
upper bounds are actually quite modest (e.g. <= 10000 or something like
that), but currently you still have infinite upper bounds on those
variables? If so, you might be able to use big M values on the order
of 10000, in which case the big M formulation may be tighter and avoid
some of the numerical disadvantages we previously discussed. In that
case, give the big M formulation a try.
>
> I have tried all the permutations of the emphasis parameters with little success. Most of the time the default parameters seem to be the most robust. Do you have any suggestions on how to accelerate the algorithm? This behavior is the same for most problem instances that I consider. I don't necessarily look for the global optimum but if I stop the algorithm prematurely, the quality of the solution is quite far from optimal, since the "Best Integer" has very slow convergence.

If you already tried MIP emphasis = 3 (i.e. just focus on improving the
best node value), and you still saw no improvement in the best node as
in the log you attached, then the odds are that you will not find other
parameter settings that will make progress in the best node. You might
try setting the presolve symmetry parameter to 5 in addition to MIP emphasis = 3, but I'm not overly optimistic.

Beyond that you might consider an alternate approach where you just
focus on trying to move the best integer solution faster. To that
end, take the best run you had so far, and also set the frequency for
the RINS heuristic to something like 120 nodes. Using interactive CPLEX,
use the command 'set mip strategy rins 120' to do this. That won't speed
help make progress in the best node, but it may help CPLEX find the best
integer solution in less time.

Finally, you could also look into tightening your formulation
by adding cuts specific to your model that CPLEX's more generic cuts
(e.g. flow cover cuts, mixed integer rounding cuts, zero half cuts) will
not find.

Ed

>
> Kind regards,
> Angelos
#CPLEXOptimizers
#DecisionOptimization