Originally posted by: SystemAdmin

Good evening,

Sorry to bother those who are not interested...

I am having difficulies when trying to solve a huge MIP model, which contains millions of non-zeros, about 200,000 of them are binary variables. However, most of these binaries are supposed to be 0, only 200 or 300 of them might be 1. And these binaries have a pretty straightforward linear equality relationship, means that they are not independent. I estimated that only 12,000 of them are independent binary decision variables. Besides, we only need to find a feasible solution which is not too ridiculous...Thus, my question is, is it still possible to get a such a solution using Cplex 12.5? What parameters should I change to achieve better computing performance?

Currently we are using a 32 threads, 126GB memory server to solve this monster model. I already changed several parameters:

CPLEX Parameter File Version 12.5.0.0
CPX_PARAM_LPMETHOD 4
CPX_PARAM_APIENCODING "UTF-8"
CPX_PARAM_EPRELAX 1.00000000000000e-03
CPX_PARAM_PARALLELMODE -1
CPX_PARAM_EPGAP 1.00000000000000e-01
CPX_PARAM_EPINT 1.00000000000000e-02
CPX_PARAM_RELOBJDIF 2.00000000000000e-02
CPX_PARAM_MIPEMPHASIS 3
CPX_PARAM_NETEPOPT 1.00000000000000e-03
CPX_PARAM_NETEPRHS 1.00000000000000e-03

I did try it several times on the server, and it went through the below information:

Presolve has improved bounds 2744926 times...
Tried aggregator 3 times.
MIP Presolve eliminated 402796 rows and 460707 columns.
MIP Presolve modified 828008 coefficients.
Aggregator did 127631 substitutions.
Reduced MIP has 2065593 rows, 1900906 columns, and 8518547 nonzeros.
Reduced MIP has 136392 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 47.09 sec. (16424.70 ticks)
Probing fixed 0 vars, tightened 302088 bounds.
Probing time = 49.32 sec. (9792.64 ticks)
Tried aggregator 2 times.
MIP Presolve eliminated 8256 rows and 7158 columns.
MIP Presolve modified 596352 coefficients.
Aggregator did 2544 substitutions.
Reduced MIP has 2054793 rows, 1891204 columns, and 8476991 nonzeros.
Reduced MIP has 134322 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 11.99 sec. (4339.51 ticks)
Probing time = 45.19 sec. (6310.91 ticks)
Clique table members: 39208.
MIP emphasis: best bound.
MIP search method: dynamic search.
Parallel mode: opportunistic, using up to 32 threads.
Then it will stuck here for a long time, during which the CPU usage is about 90%. However, if it went through and continue to the below:

Root relaxation solution time = 3528.64 sec. (174932.36 ticks)

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

• 0+ 0 2.03343e+07 3072.1983 153 99.98%

0 0 1221444.0634 3906 2.03343e+07 1221444.0634 153 93.99%
0 0 1222795.2941 4008 2.03343e+07 Cuts: 8974 185510 93.99%
0 0 1223238.0922 4193 2.03343e+07 Cuts: 8401 342845 93.98%
0 0 1223465.1370 4540 2.03343e+07 Cuts: 7115 501790 93.98%
Then the CPU usage drops to 100% or so, and the progress is slow.

So should I change any parameters to improve CPU usage in order to achieve best performance? I appreciate it very much if somebody could provide any suggestions on setting up the parameters. Thank you so much for your time in advance.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

OK, this line

Root relaxation solution time = 3528.64 sec. (174932.36 ticks)

tells you that solving the root relaxation takes quite some time. You should set CPX_PARAM_MIPDISPLAY to 4 to see more details about that.
Since you explicitly set the lpmethod to barrier, did you experiment with the other options (primal, dual, concurrent)?
When you say that CPU usage during the root solve is 90%, does that mean 90% of 32 cores are used or only 90% of a single core and the remaining cores are idle?
If you are only interested in some feasible solution you could set CPX_PARAM_INTSOLLIM to 1. That makes CPLEX stop at the first feasible solution.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Many thanks for the reply. I originally tried primal, but that tends to be slower than barrier. CPU usage is around 2600%. Thank you for the tips, but currently it already took 12 hrs for root-relaxation but still not be able to proceed. What's more, I notice that the memory usage is approaching 90% of the whole server as well. So is there any seetings which could potentially speed up the root relaxation and reduce memory usage (I know this maybe almost impossible but still...)?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: T_O

Did you try the dual algorithm? For the root node, it is typically faster than the primal algorithm (but slower than the barrier). For the other nodes, it should be the algorithm of choice.

You might set CPX_PARAM_STARTALG to 4 and CPX_PARAM_SUBALG to 2.

Best regards,
Thomas
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I will try the dual, thanks a lot for the inputs.

What's more, I relax the binaries by setting them to be continuous variables less than 1 but greater than 0, and manually solve the lp problem using primopt, it looks like much faster....
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

This is surprising. The only difference between manually changing the variables to continuous and solving the resulting LP with primal simplex as opposed to just setting the start algorithm to primal simplex should be the presolve reductions. Exploiting the integrality, MIP is typically able to perform more presolve reductions than the LP presolver. Thus, the final MIP model after MIP presolve and a subsequent LP presolve on the LP relaxation should be smaller than the LP model after LP presolve.

Maybe, the reason is a different pricing rule that is used for MIP. You may want to play with the "pgradient" and "dgradient" parameters (for primal and dual pricing rules, respectively).
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Just got segmentation fault this morning. I guess the reason is lacking memory. I am going to try a reduced version and set solution information display level to be highest, to see what might be the cause of slow root relaxation.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: T_O

If you know that at most 300 binary variables are nonzero, it might be helpful to add a constraint like
x1+x2+x3+...+xn <= 300
to get a tighter formulation (it could decrease the gap). But I am not sure about this as this constraint is totally dense. You could give it a try.

Best regards,
Thomas
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

This is very interesting... I will try it. So far I find out that the root relaxation went pretty quickly to an objective value very close to the optimal, but then it became very slow to get it better and better. I wonder if I could actually stop there and use that point to begin branch and cut......
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: T_O

Well, if it is adding Cuts to the root, it is actually doing branch & cut.

You could set the solution limit to 1 and disable cuts and heuristics after the solution is found. Then you could reset the solution limit and restart optimization. But I doubt it will help.

Best regards,
Thomas
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks very much for you guy's inputs. Since it is still too slow, I am trying to use a warm-start technic. However, a new question: when I feed Cplex an initial solution x0 (suppose this x0 is feasible and optimal for this problem), but the problem has multiple optimal solutions. So, will cplex stick to the x0 I gave it? Will it only search around x0's neighbor first? I tried some small problems and the results looks like Cplex will search wider region despite the hot start x0. Does anybody knows how Cplex takes advantage of an initial start? Many thanks for your time.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: T_O

The MIP-start is used for cutoffs during branch&bound. If your LP-relaxation is not very tight and there are many feasible solutions, your MIP-start might not really help you even if it is optimal.

I remember that there is a post in this forum that says that someone made a study where CPLEX was provided the optimal solutions for several MIPs. If I remember correctly, the running times did not decrease very much.

Maybe, you should try to reformulate your model.

Best regards,
Thomas
#CPLEXOptimizers
#DecisionOptimization