In the above formulation, the sum of Z variables is always smaller than capacity "c", but equal to zero if binary variables X equals 0.
I would model this by using two constraints:
- one plain linear constraint: sum(Zs) <= c
- one _indicator_ constraint, stating that sum(Zs) is zero when X is zero. To express this in DOcplex, use Model.add_indicator,
which takes three arguments:
- a binary variable (here X)
- a linear constraint, whose truth value will be controlled by X, here it is sum(Zs) ==0
- a value(0 or 1) which triggers the action between the binary variable and the linear constraint: default is 1 but in your case it's 0: the sum of Zs variables becomes equal to zero when X is 0.
Here is a very simple example code to illustrate this:
def model_with_indicators():
m = Model()
zs = m.continuous_var_list(3, name='Z')
x = m.binary_var(name='X')
# this comnstraint is NOT posted
all_zeros = m.sum(zs) == 0
m.add_indicator(x, all_zeros, active_value=0, name="my_indicator")
m.add(m.sum(zs) <= 10) # capacity
m.maximize(m.sum(zs))
# force x to 0 to see what happens
x.ub= 0
return m
Solving this model yields all Zs to 0, because X ==0 forces the linear constraint "sum(zs) ==0" to be satisfied.
Note that
- the "sum(zs)==0" should NOT be added to the model, as its truth value is not certain: it depends on the value of X
- we had to specify "active_value=0" as the triggering value (default is 1)
- no more big-M value is used, which result in a much safer model.
Here is an extract of the DOcplex documentation for `Model.add_indicator`
def add_indicator(self, binary_var, linear_ct, active_value=1, name=None):
""" Adds a new indicator constraint to the model.
An indicator constraint links (one-way) the value of a binary variable to
the satisfaction of a linear constraint.
If the binary variable equals the active value, then the constraint is satisfied, but
otherwise the constraint may or may not be satisfied.
Let me know if you have questions.
Philippe.
------------------------------
Philippe Couronne
------------------------------
Original Message:
Sent: Sat October 10, 2020 02:59 AM
From: Ken Nguyen
Subject: please help for MIP model running long time
Dear Philippe,
I have a constraint with Big_M as below. Could you help me transfer it to an indicator constraint in CPLEX?
------------------------------
Ken Nguyen
Original Message:
Sent: Thu October 08, 2020 05:01 AM
From: Philippe Couronne
Subject: please help for MIP model running long time
Not exactly. I see two action items:
1. substitute big-M formulations on binary variables with indicator constraints, wherever possible.
2. investigate why some linear constraints have such a huge range of coefficients (1e+16): this should definitely be modeled in a different manner.
Philippe.
------------------------------
Philippe Couronne
Original Message:
Sent: Thu October 08, 2020 04:28 AM
From: Ken Nguyen
Subject: please help for MIP model running long time
Dear Philippe,
That means that I need to fix Big_M coefficients that are less than 1e+6 to get the result in rich quality. Right?
Best regards,
Ken Nguyen
------------------------------
Ken Nguyen
Original Message:
Sent: Thu October 08, 2020 03:57 AM
From: Philippe Couronne
Subject: please help for MIP model running long time
Your model has numerous numerical issues, which are likely to impact its run performance, and are certyain
to result in poor quality of the solution
The first issue I see is many big-M formulations with 1e+7 coefficients.
This is known to introduce numerical instability, and you should prefer indicator constraints instead.
Cplex manages the association between binary variable and constraint internally, without instabilities.
See this article for more details:
https://www.ibm.com/support/knowledgecenter/SSSA5P_12.10.0/ilog.odms.cplex.help/CPLEX/UsrMan/topics/discr_optim/indicator_constr/04_Interactive.html
I also see coefficients in constraints with a ratio of 1e+16, this is too much. The range of orders of magnitudes should not exceed 1e+6, in other
terms, the ratio of the biggest coefficient (in absolute value) should not exceed 1e+6, otherwise you will encounter numerical instabilities.
A ratio of 1e+16 is definitely too large, and should be fixed.
There are other issues, but these two topics seem to me the highest priority to fix.
Philippe.
------------------------------
Philippe Couronne
Original Message:
Sent: Wed October 07, 2020 03:55 PM
From: Ken Nguyen
Subject: please help for MIP model running long time
Dear Philippe,
Could you see the file attached and tell me to know, where are numerical stability issues?
Thank you,
Best regards,
Ken Nguyen
------------------------------
Ken Nguyen
Original Message:
Sent: Wed October 07, 2020 09:42 AM
From: Philippe Couronne
Subject: please help for MIP model running long time
Commands should be run from the "cplex.exe" interactive optimizer.
This executable is located in the COS installation at: <cos_root>/cplex/bin/x64_win64/cplex.exe.
A full description of the interactive optimizer can be found here:
https://www.ibm.com/support/knowledgecenter/SSSA5P_12.10.0/ilog.odms.cplex.help/CPLEX/homepages/interactiveoptimizercommands.html
Note that when serializing the model, you should use SAV format to avoid numerical roundoffs.
The script I suggest is then the following:
> read myproblem.sav <------------ path where your SAV file is.
> display problem stats
> set read datacheck 2
> opt
Data analysis is performed before solve, so you might as well set a time limit of 1 to perform the analysis and stop after.
The output of this script should help use detect (or rule out) numerical stability issues.
Philippe.
------------------------------
Philippe Couronne
Original Message:
Sent: Wed October 07, 2020 08:21 AM
From: Ken Nguyen
Subject: please help for MIP model running long time
Dear Philippe,
Thank you,
How to run `display problem stats` in CPLEX?
Best regards,
Ken Nguyen
------------------------------
Ken Nguyen
Original Message:
Sent: Wed October 07, 2020 06:14 AM
From: Philippe Couronne
Subject: please help for MIP model running long time
From the logs you sent, it appears your problem is mostly a LP, and time is spent on the first linear relaxation.
A common cause for poor LP performance is ill-conditioning.
To rule out such numerical issues, I suggest you do the following actions, under Cplex interactive:
- once the problem is read by cplex interactive, run `display problem stats`: this command will compute the lowest and highest magnitudes
of coefficients; if the ratio between highest and lowest is too high, this indicates numerical issues.
- before running solve in cplex interactive, set the `read datacheck` parameter to 2. This value will perform detailed checks on numerical issues,
see https://www.ibm.com/support/knowledgecenter/SSSA5P_12.10.0/ilog.odms.cplex.help/CPLEX/UsrMan/topics/progr_consid/modelingAssistance/introModelingAssistance.html
for details.
To summarize, here's the augmented script to run in cplex interactive to check for numerical issues:
> read ...
> display problem stats
> set read datacheck 2
> opt
If your problem suffers from numerical issues, this should show up as warnings in the output.
Philippe.
------------------------------
Philippe Couronne
Original Message:
Sent: Sun October 04, 2020 11:28 AM
From: Ken Nguyen
Subject: please help for MIP model running long time
Hi Xavier,
Please find the new copied the log, the model is running over 24 hours. Could you help me to get results?
Best regards,
Ken Nguyen
------------------------------
Ken Nguyen
Original Message:
Sent: Fri October 02, 2020 10:22 AM
From: Ken Nguyen
Subject: please help for MIP model running long time
Hi Xavier,
1. "set mip strategy startalgorithm of 4" is the fastest compared with other algorithms. I tried with small data example and get results about 3 minutes. The log for this example can see "log_smalldata" attached.
2. But when run with big data with using "set mip strategy startalgorithm of 4" , the model does not stop for a long time (over 25 hours), so I copy lines into a file "log_bigdata".
No, it is stuck at the log line for a long time. So, could you help me with how to get results for the big data case for a few hours?
Thank you,
Best regards,
Ken Nguyen
------------------------------
Ken Nguyen
Original Message:
Sent: Fri October 02, 2020 06:34 AM
From: Xavier Nodet
Subject: please help for MIP model running long time
1. You chose "set mip strategy startalgorithm 4". That is Barrier + Crossover. Did you try other algorithms as well? The default is to run concurrent opt, which means that CPLEX will run Dual simplex, Primal Simplex and Barrier+Crossover. But if the issue is that Crossover takes a very long time (as seems to be the case), then you may want to switch to another algorithm instead.
2. Was CPLEX still printing log lines regularly when you stopped it, or did it stop to print any log line for a long time before you copied the log? During the last part of the log (from 'Dual crossover'), CPLEX actually runs two crossover algorithms concurrently (Primal and Dual). But it can only print the log for one, in this case Dual. Knowing whether Dual was stopped or not may indicate which of the two is slower.
3. Is there a specific reason why you didn't try the latest version available on https://ibm.biz/CPLEXonAI? Version 12.8 is already 3 years old, and version 12.10 is available since last December.
------------------------------
Xavier
Original Message:
Sent: Fri October 02, 2020 05:26 AM
From: Ken Nguyen
Subject: please help for MIP model running long time
Dear everyone,
I am using CPLEX 12.8 on a PC with RAM 64GB. But the model is running for a long time (15 hours) and doesn't get results. Although I used "set mip strategy startalgorithm" with a number between 1 and 5, the model still works for such a long time.
Could you look at the attached log, and help me? I am really grateful.
Best regards,
Nguyen
------------------------------
Ken Nguyen
------------------------------
#DecisionOptimization