Originally posted by: MohammadReza

Hello,

I have faced a problem while solving my problem with CPLEX. That is about complexity!!

I have constructed a problem which is so complex. Many constraints are involved. I can not avoid bringing them into account. I tried to solve some instances (.lp files), but after 24 hours time limit, program ends with a sub-optimal solution.

I can extend time limit, but that is not going to help much, because for large size problems, still I am stuck with sub-optimal solutions.
I tried to reduce optimality tolerance and integrality tolerance to 1e-05 and 1e-04 respectively, but did not have a remarkable change.

Do you know how can I improve it? Any comment is appreciated.

Thanks
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Unfortunately, the answer to your question would probably fill up a full year's worth of doctoral seminars (which, sadly, I probably would not be qualified to teach). Among the possibilities:

a) A tighter formulation might help. ("Tighter" here means one that produces stronger bounds.) Unfortunately, there is no general recipe for providing tight formulations.

b) If the incumbent stabilizes early but the best bound moves slowly, it might actually be that you have the optimal solution but do not know it.

c) If the bound moves slowly, adding bound tightening constraints (cuts) on the fly might help -- assuming you have some way of determining them. CPLEX does a good job of adding "generic" cuts, but for certain problems there may be problem-specific ways to generate better cuts.

d) If the model's structure is amenable to decomposition, that might help. (Then again, it might not.)

e) If you can find a heuristic that quickly finds a good solution, running the heuristic first and injecting the solution might help (or it might not).

f) An "outer approximation" approach, such as Benders decomposition, might (or might not) help.

All of these require trial-and-error testing, and most require some insight/creativity based on the specific structure of the problem. Finally,

g) You may get better results by adjusting some of the (many!) parameters CPLEX provides.

For option (g), at least, there may be some guidance. Recent versions of CPLEX provide a tuning mechanism that will automatically run through combinations of parameters and try to find an optimal (or at least good) set of non-default values. Since tuning involves multiple solutions of the test problem(s), you will not want to run it on your full model. So I would suggest creating a small example that contains the same structure as the full model, but considerably scaled down, and then tuning CPLEX using that example. The user guide that ships with CPLEX explains how to use the tuning feature.

/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: MohammadReza

Hi Paul,

Thanks a lot for your long reply. Your points are very useful.

I have tried to squeeze the constraints to reduce the search space. The issue is that my problems are dealing with high number of constraints and large instances are facing time limit. I do wireless network optimization and design task. I don’t want to decompose the problem and use sequential approach. One of the contributions to my tasks is to do it globally.

Yes, the best bound moves slowly. This is the problem. (Part C of your comments)

Actually I have adapted local search and tabu search which provide approximate solutions with gap of 2% to 3%, but I need further refinement. The heuristics do their best and I use multi-start tabu search to find more precise answers.

Injecting the solution form heuristics to CPLEX a fantastic idea, but I don’t know have any idea how to do it. My heuristics are in C++, while my CPLEX code is in text (.lp) files.

About tuning the CPLEX, I reduced the optimality tolerance to 0.001 and integrality tolerance to 0.01 (I am not sure if this is a valid job) and got better CPU time for medium size problems, but large size problems still have time limit issue.

I appreciate if you can please give me some more clues on item c and item e.

Thanks again for your reply.

M Reza
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Mohammad,

> MohammadReza wrote:
>
> I have tried to squeeze the constraints to reduce the search space.

I'm not sure what you mean here by "squeeze" the constraints. If you mean that you have tried to pare down the number of constraints, keep in mind that while redundant constraints are usually undesirable for LPs (they just slow down pivoting), for MIPs they may actually be useful in tightening the continuous relaxation of the model. Also, something I failed to mention before is sparsity. You want your constraint matrix to be as sparse as possible, even if that means introducing additional variables and constraints. For instance, if a certain linear combination of variables appears repeatedly in the model, it may help to create a new variable, constrain it to equal that expression, and replace all occurrences of the expression with the variable. (I read a blog post recently where someone got a significant speed-up on a nonlinear problem by doing this.)
>
> Injecting the solution form heuristics to CPLEX a fantastic idea, but I don’t know have any idea how to do it. My heuristics are in C++, while my CPLEX code is in text (.lp) files.

So you are solving the MIP model using CPLEX's interactive solver? You will need to create an MST file (which is an XML text file) containing the starting solution, then use the interactive optimizer's read command to read the MST file (after reading the LP file and before solving). The documentation that comes with CPLEX includes a chapter on file formats that gives a little information (not a lot, but perhaps enough) on the MST format.
>
> About tuning the CPLEX, I reduced the optimality tolerance to 0.001 and integrality tolerance to 0.01 (I am not sure if this is a valid job) and got better CPU time for medium size problems, but large size problems still have time limit issue.

I would still recommend doing a tuning run on one or more "toy" examples. This would help you decide how to set things like probing, application of heuristics, branching strategy etc. With the interactive optimizer, you set up a text file listing parameter values you want to freeze (if there are any), then use the 'tune' command followed by the names of the test .lp files and the (optional) .prm file specifying parameters not to be changed. See User's Manual for CPLEX > Programming considerations > Tuning tool for details.

Also, you can experiment with different algorithms for the root node and for the other nodes. If you're doing communications network design, possibly network simplex will do better than the defaults, which are typically primal simplex at the root and dual simplex at the other nodes. If your model tends toward degeneracy, you might want to try barrier for the root (and perhaps the other nodes, although I think dual simplex is usually best on subproblems).
>
> I appreciate if you can please give me some more clues on item c and item e.

I think I've passed along about as much as I have on (e) above. As far as (c) goes, beyond tuning CPLEX I don't think there is anything specific that I can add. If you are reading LP files into the interactive optimizer (which means you have no ability to control the solution process on the fly), then all that is left is to get the best possible initial formulation. Other than maintaining sparsity (mentioned above), I don't have any general advice. Considerable study goes into finding "tight" formulations for models, but those results are problem-specific. I don't know anything specific about formulations for communication networks.

Good luck,
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: MohammadReza

Hi Paul,

Thanks for your comments.

I liked the idea of providing initial mst solution for CPELX (12.1 in my case). I am using interactive mode.

I changed the parameter set advance to 2 (2 = alternate advanced start) to let CPLEX to accept the .xml file. To find a proper xml file format for my problem, I first solved it a sample problem and using write command, saved the solution as mst format. The output comes in xml format automatically!Goood!

In the second step, I replaced the value for variables with the solution which I already had by using tabu search.

I put .lp file and .xml file in the same folder and run CPLEX from that folder. I tried to read the .xml file with CPLEX, CPLEX seems finds the file and lists the file type options for me to select. I chose mst from the list , but CPLEX says : No problem exists. No file read.”

I am attaching my .lp file and .xml file here.
I doubt my .xml file is in proper format. According to
http://www-eio.upc.es/lceio/manuals/cplex-11/html/reffileformatscplex/reffileformatscplex21.html
, I am missing some parts of the header and quality parts in my .xml file. (I have just value for objective function from tabu search.)

Do you think my .xml file in correct format? Why yes, CPLEX can not read my .xml file.

Thanks

Mohammad Reza
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: MohammadReza

Hi Paul,

Thanks for your comments.

I liked the idea of providing initial mst solution for CPELX (12.1 in my case). I am using interactive mode.

I changed the parameter set advance to 2 (2 = alternate advanced start) to let CPLEX to accept the .xml file. To find a proper xml file format for my problem, I first solved it a sample problem and using write command, saved the solution as mst format. The output comes in xml format automatically!Goood!

In the second step, I replaced the value for variables with the solution which I already had by using tabu search.

I put .lp file and .xml file in the same folder and run CPLEX from that folder. I tried to read the .xml file with CPLEX, CPLEX seems finds the file and lists the file type options for me to select. I chose mst from the list , but CPLEX says : No problem exists. No file read.”

I am attaching my .lp file and .xml file here.
I doubt my .xml file is in proper format. According to
http://www-eio.upc.es/lceio/manuals/cplex-11/html/reffileformatscplex/reffileformatscplex21.html
, I am missing some parts of the header and quality parts in my .xml file. (I have just value for objective function from tabu search.)

Do you think my .xml file in correct format? if yes, CPLEX can not read my .xml file.

Thanks

Mohammad Reza
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: MohammadReza

Hi Paul,

Thanks for your comments.

I liked the idea of providing initial mst solution for CPELX (12.1 in my case). I am using interactive mode.

I changed the parameter set advance to 2 (2 = alternate advanced start) to let CPLEX to accept the .xml file. To find a proper xml file format for my problem, I first solved it a sample problem and using write command, saved the solution as mst format. The output comes in xml format automatically!Goood!

In the second step, I replaced the value for variables with the solution which I already had by using tabu search.

I put .lp file and .xml file in the same folder and run CPLEX from that folder. I tried to read the .xml file with CPLEX, CPLEX seems finds the file and lists the file type options for me to select. I chose mst from the list , but CPLEX says : No problem exists. No file read.”

I am attaching my .lp file and .xml file here.
I doubt my .xml file is in proper format. According to
http://www-eio.upc.es/lceio/manuals/cplex-11/html/reffileformatscplex/reffileformatscplex21.html
, I am missing some parts of the header and quality parts in my .xml file. (I have just value for objective function from tabu search.)

Do you think my .xml file in correct format? if yes, why CPLEX can not read my .xml file.

Thanks

Mohammad Reza
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: MohammadReza

Sorry for multiple posts. Here is the .xml file.

Thanks
M Reza
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

The XML file needs to have extension .mst. I did the following: renamed your LP file to mr.lp (less typing) and your XML file to mr.mst; started CPLEX; issued the commands

read mr.lp
read mr.mst
mip

and it appeared to work. Here's an excerpt from the log:

MIP start file 'mr.mst' read.
Warning:  No solution found from 1 MIP starts.
Retaining values of one MIP start for possible repair.

The warning means that the solution you supplied is not a complete feasible solution. The following line indicates that CPLEX will attempt to repair it (which at minimum means supplying values for any variables you did not specify, and possibly includes applying heuristics) to try to get a feasible start.

Here are the first few lines of the node log:

Nodes                                         Cuts/ 
   Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap
 
      0     0  1269234.0039    81                1269234.0039      938         
*     0+    0                      4077160.0000  1269234.0039      938   68.87%
*     0+    0                      2375804.0000  1269234.0039     1394   46.58%
      0     0  1385472.6410   227  2375804.0000     Cuts: 400     1394   41.68%

You should be able to tell from that whether the heuristic solution is letting you find a good incumbent faster than if you ran the model without the heuristic solution.

/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: MohammadReza

Hi Paul,

You are right. I corrected my script. CPLEX is now able to read the initial solution. The cost of the initail solution is 2416404.0000, which CPLEX calculated after reading the initial solution.
I took the following from the logfile:
.....
Problem 't1-20000-35-5-5-5-5-5.lp' read.
Read time = 0.04 sec.
MIP start file 't1-20000-35-5-5-5-5-5.mst' read.
1 of 1 MIP starts provided solutions.
MIP start 'm1' defined initial solution with objective 2416404.0000.
....

But surprisingly the CPU time increased!! see the log files:

============== without initial solution==========
GUB cover cuts applied: 88
Clique cuts applied: 82
Cover cuts applied: 116
Implied bound cuts applied: 94
Flow cuts applied: 385
Mixed integer rounding cuts applied: 429
Zero-half cuts applied: 82
Multi commodity flow cuts applied: 17
Gomory fractional cuts applied: 27

Solution pool: 15 solutions saved.

MIP - Integer optimal, tolerance (0.0001/1e-06): Objective = 2.3758040000e+06
Current MIP best bound = 2.3756791865e+06 (gap = 124.813, 0.01%)
Solution time = 236.88 sec. Iterations = 598800 Nodes = 8451 (3)
=====================================================================================
============== with initial solution==========
GUB cover cuts applied: 92
Clique cuts applied: 83
Cover cuts applied: 131
Implied bound cuts applied: 89
Flow cuts applied: 352
Mixed integer rounding cuts applied: 472
Zero-half cuts applied: 85
Multi commodity flow cuts applied: 33
Gomory fractional cuts applied: 20

Solution pool: 10 solutions saved.

MIP - Integer optimal, tolerance (0.0001/1e-06): Objective = 2.3758040000e+06
Current MIP best bound = 2.3755718947e+06 (gap = 232.105, 0.01%)
Solution time = 761.11 sec. Iterations = 1405657 Nodes = 29070 (17)
================================================================================

Do you have any idea why this happened? Should I try more problems?

Thanks
M Reza
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> MohammadReza wrote:
>
> Do you have any idea why this happened?

Because integer programming problems are perverse. By injecting an initial solution, you change the path CPLEX follows through the search tree. So possibly you get lucky and stumble on a really good solution early in the search without the injection, but with the injection you take a different path that happens not to find a comparably good solution so quickly (and thus plows through more nodes). There could be other factors at work as well, but that is the first explanation that comes to mind.

> Should I try more problems?

If you are trying to decide whether or not to give the initial solution, yes, you should experiment more. It may be that the initial solution helps more often than it hurts.

/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: EdKlotz

> MohammadReza wrote:
> Hello,
>
> I have faced a problem while solving my problem with CPLEX. That is about complexity!!
>
> I have constructed a problem which is so complex. Many constraints are involved. I can not avoid bringing them into account. I tried to solve some instances (.lp files), but after 24 hours time limit, program ends with a sub-optimal solution.
>
> I can extend time limit, but that is not going to help much, because for large size problems, still I am stuck with sub-optimal solutions.
> I tried to reduce optimality tolerance and integrality tolerance to 1e-05 and 1e-04 respectively, but did not have a remarkable change.
>
> Do you know how can I improve it? Any comment is appreciated.
>
> Thanks

I took a look at the model you sent. As you pointed out, lack of progress in the best
node value appeared to be the primary performance bottleneck. With this in mind,
I set CPLEX's MIP emphasis parameter to 3; this instructs CPLEX to set various
other MIP parameters to try to get faster improvement in the best node value. This
can also sometimes diminish the progress in the best integer, so you may also want
to use settings that help CPLEX find more feasible solutions such as setting the
RINS heuristic frequency to a value between 50-200 nodes, depending on your rate
of throughput. With just MIP emphasis = 3, I got the following with CPLEX 12.1:

300 229 2372701.5629 106 2381179.0000 2360012.3844 59653 0.89%

• 327+ 240 2377604.0000 2360012.3844 63906 0.74%

400 259 cutoff 2377604.0000 2363005.9607 77878 0.61%

• 486+ 193 2375804.0000 2374683.7939 93285 0.05%

Solution pool: 7 solutions saved.

MIP - Integer optimal solution: Objective = 2.3758040000e+06
Solution time = 18.26 sec. Iterations = 93332 Nodes = 486
With MIP emphasis 3 and the RINS frequency set to 150, CPLEX 12.1 did even better:

MIP - Integer optimal, tolerance (0.0001/1e-06): Objective = 2.3758040000e+06
Current MIP best bound = 2.3756013008e+06 (gap = 202.699, 0.01%)
Solution time = 10.44 sec. Iterations = 73142 Nodes = 653 (8)

Note also that the more recent CPLEX 12.2 can solve the model within a few minutes
with default settings. However, it does not do better than 12.1 with the alternate
settings I mentioned above. The additional improvements that help the defaults do
better also appear to slow the rate of node throughput when setting MIP emphasis to 3.
If you are an academic user, your university or college can update to CPLEX Optimization Studio 12.2 at no charge.

Can we add this model to our CPLEX R&D test set?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: MohammadReza

Hi Paul,
You are right. Injecting initial solution cost more CPU time in my case. I decided to ignore this solution.

Thanks
M Reza
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: MohammadReza

Hi Ed,

Thanks a lot for your help. It really saved me. I got very good solutions with the following settings:

1)set simplex tolerance optimality 1e-02
2)set mip tolerance integrality 1e-03
3)set emph mip 3
4)set mip strategy rinsheur 100

I have a question. I have changed tolerance optimality from the default (1e-06) to 1e-02 and tolerance integrality from the default (1e-5) to 1e-03. Is there any possibility that the generated solutions are not optimal due to change in these two parameters?

Of course you can add it into your test list. I can also send you more complex problems I have generated. Is this your email: klotz@ilog.com ?

Thanks
Mohammad Reza
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

Mohammed,

> MohammadReza wrote:
> Hi Ed,
>
> Thanks a lot for your help. It really saved me. I got very good solutions with the following settings:
>
> 1)set simplex tolerance optimality 1e-02
> 2)set mip tolerance integrality 1e-03
> 3)set emph mip 3
> 4)set mip strategy rinsheur 100
>
> I have a question. I have changed tolerance optimality from the default (1e-06) to
> 1e-02 and tolerance integrality from the default (1e-5) to 1e-03. Is there any
> possibility that the generated solutions are not optimal due to change in these two
> parameters?

The solutions are optimal within the tolerances you specify. I do not recommend
adjusting tolerances like this to get good performance. I recommend changing tolerances when the nature of your model indicates that CPLEX's default tolerances
may yield solutions within those tolerances that aren't consistent with the intent
of the model. Regarding performance, I would expect that, like me, you would get
good performance just with settings 3) and 4) above, leaving tolerances at their
default.

Specific to your model, consider a constraint like

+ f22,0,0,0
+ f22,0,1,0
+ f22,0,2,0
+ f22,0,3,0
+ f22,0,4,0
- 400000x3,0,0
- 600000x3,0,1
- 1000000x3,0,2 <= 0

Here the x variables are binary. From this constraint, we see that if all three
of these x variables are 0, you don't want any of the associated f variables in the
constraint to take on nonzero value. Yet, if you set the relatively loose integrality
tolerance of 1e-3, you indicate to the optimizer that a solution with x variables
set to 1e-3 is acceptable. Yet, such a solution violates the intent of the model if I understand it correctly. By setting each x variable to 1e-3, you enable the f variables
to take on a significant level of resource (i.e. 400 + 600 + 1000 = 2000) without paying
the full fixed cost that your model intends. So, if anything, on this model I recommend you consider reducing the feasibility and integrality tolerance values to less
then the reciprocal of the maximum big M value in the model (1000000).

>
> Of course you can add it into your test list. I can also send you more complex problems I have generated. Is this your email: klotz@ilog.com ?
Thanks. We don't need a huge number of models, but if you have one or two more
that are more challenging to solve, we would definitely be interested. klotz@ilog.com
used to be my e-mail address, but that is now obsolete since IBM acquired ILOG.
My updated address is

klotz 'at' us 'dot' ibm 'dot' com
>
> Thanks
> Mohammad Reza
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

Mohammad,

>
> Of course you can add it into your test list. I can also send you more complex problems I have generated. Is this your email: klotz@ilog.com ?
>
> Thanks
> Mohammad Reza

One other thing regarding the models. Here's the standard IBM statement we send out to
any of our product users regarding our usage of their data. You need not take any action.

---

Thank you for the opportunity to assist with your CPLEX support request. This email explains the uses that will be made of the information and mathematical model(s) (“Data”) you have been or will be sending for review in connection with your request.
We will use your Data to attempt to resolve the issues identified in the support request. In addition, unless you notify us otherwise within 5 business days of receiving this email, your Data will be retained for use in the further development of CPLEX and related software. While all retained Data will remain your property, all developments made to the software will belong to us.
Data that includes personal identifying information must not be submitted. “Personal identifying information” includes individual names, social security numbers, addresses, and similar information, all of which is governed by applicable privacy laws and regulations. You agree that none of the Data includes any such personal identifying information and that you are in compliance with applicable privacy laws and regulations.
Thank you again for allowing us to assist you.

---

#CPLEXOptimizers
#DecisionOptimization