# CPLEX Problem when removing perturbation

 2 Hello everyone! Again, I have a problem with my gigantic LP (3 million variables) that I want CPLEX to solve. So the linear program basically describes objects of in images moving over time. It works perfectly fine when I give a manual upper bound for the time (e.g. I only parse 20 time steps). But when I use the full data (100 time steps), it gets weird, namely: The dual objective value changes each iteration in a reasonable way, e.g. it goes up to 263 (I am expecting a number between 250 and 300). But after some thousand iterations, CPLEX removes a perturbation and boom, the objective goes down to -millions. I read that a resetting of the Markovitz Threshold (see the log) is an indicator of numerical problems. Could that be the case? I have tried to tell CPLEX to not change the dual norms, but now it is solving since 30 minutes and the dual objective is still only around 175. I really have no idea what is going wrong, especially since the program works fine for a subset of the data. Has anyone experienced this before? I would appreciate your tips very much! Let me know if you need more information about something in particular. Thank you very much and have a nice day! Here is part of the log: Iteration: 67655 Dual objective = 183.533442 Iteration: 68621 Dual objective = 190.114622 Iteration: 69518 Dual objective = 196.371050 Iteration: 70575 Dual objective = 203.308454 Iteration: 71482 Dual objective = 206.882308 Iteration: 72410 Dual objective = 211.269087 Iteration: 73321 Dual objective = 216.911677 Iteration: 74402 Dual objective = 221.701661 Iteration: 75398 Dual objective = 224.822140 Iteration: 76423 Dual objective = 229.342227 Iteration: 77487 Dual objective = 233.143312 Iteration: 78385 Dual objective = 236.676269 Iteration: 79357 Dual objective = 238.933035 Elapsed time = 21.13 sec. (80000 iterations). Iteration: 80443 Dual objective = 244.158417 Iteration: 81537 Dual objective = 247.623521 Iteration: 82447 Dual objective = 250.756436 Iteration: 83349 Dual objective = 252.734475 Iteration: 84231 Dual objective = 255.267888 Iteration: 85151 Dual objective = 257.401259 Iteration: 86096 Dual objective = 260.683480 Iteration: 86954 Dual objective = 262.815207 Removing perturbation. Reinitializing dual norms . . . Iteration log . . . Iteration: 1 Dual objective = 263.096968 Perturbation started. Iteration: 102 Dual objective = 263.096968 Removing perturbation. Iteration: 418 Dual objective = -52999999735.812897 Perturbation started. Iteration: 519 Dual objective = -52999999735.815498 Iteration: 1068 Dual objective = -9999917905.551868 Iteration: 1587 Dual objective = 116436.956836 Elapsed time = 19.30 sec. (2000 iterations). Markowitz threshold set to 0.1 Iteration: 2054 Dual objective = 135067.734477 Iteration: 3173 Dual objective = 135069.301852 Iteration: 4094 Dual objective = 135069.988800 Iteration: 5288 Dual objective = 135071.986818 Iteration: 6548 Dual objective = 135073.385536 Iteration: 7747 Dual objective = 135074.066019 Iteration: 8947 Dual objective = 135074.714765 Iteration: 10100 Dual objective = 135075.248656 Iteration: 11269 Dual objective = 135075.759028 Iteration: 12393 Dual objective = 135076.230404 Iteration: 13567 Dual objective = 135076.874201 Iteration: 14717 Dual objective = 135077.520679 Iteration: 15848 Dual objective = 135077.953414 Elapsed time = 29.54 sec. (16000 iterations). Iteration: 16705 Dual objective = 135078.643132 Iteration: 17762 Dual objective = 135079.079370 Iteration: 18842 Dual objective = 135079.951029 Iteration: 19918 Dual objective = 135080.575799 Iteration: 20917 Dual objective = 135028.426595 Iteration: 21910 Dual objective = 135028.800759 Elapsed time = 39.94 sec. (23000 iterations). Iteration: 23031 Dual objective = 135029.981897 Iteration: 24064 Dual objective = 135030.752972 Iteration: 25237 Dual objective = 135031.780180 Iteration: 26503 Dual objective = 135032.726037 Iteration: 27643 Dual objective = 135033.448021 Iteration: 28719 Dual objective = 135034.157546 Removing perturbation. Dual simplex solved model. Solution value = 282.829 FIRST TEST: ACTUALLY OPTIMAL:?Infeasible // comes from cplex.getStatus();  asked 12 Jul '12, 09:07 SurfsUp 31●1●2●3 accept rate: 0% fbahr ♦ 4.6k●7●17 Hello everyone! Thank you very much for your suggestions. I only work one day a week thus I couldn't try them out yet, but I will tomorrow. I will let you know of the results. Bo: Unfortunately I cannot share the data, I am not allowed to. (19 Jul '12, 16:26) SurfsUp

 4 Disclaimer : I am no cplex expert and you will probably get a better answer at cplex support forum. When cplex removes perturbation your basis is most likely refactored and judged instabil, which is why they also choose to raise the markowitz tolerance to increase stability on internal solves in the simplex algorithm. The reason why you see huge change in objective can be either : When the basis matrix B is close to singular, then solving linear equations like xB = v and Bx = v can blow up in size. So the dual variables (and/or the primal variables) take on large values. Dual feasiblity is lost and it decide to regain feasibility be swapping a lot of variables with large bounds from one bound to another, which makes the solution feasible but changes objective. Since Cplex is a state of art optimizer, I doubt it's second bullit point but one is much more likely. These things can occur, I would advise you to investigate your data to examine for badly scaled data. If this happens a lot, you could (only on these types of models) raise the default level of the markowitz tolerance, but generally I am against too much fiddling with standard parameters. You could also set a maximum iteration count which equals just before it goes wrong, when it has stopped print out the condition number of the basis matrix stored inside the solver. If it's high, then we are definitely in case one. One thing I think is a bit strange, is they start to recount iterations, I don't remember having seen a log with this before i.e in same solve. BTW : If you in anyway can share the data, I would be interested to take a look at this LP model, in such case please contact me, see profile for details. - answered 12 Jul '12, 09:38 Bo Jensen ♦ 5.0k●2●10●19 accept rate: 14%
 3 Care of Alexandra Newman and Ed Klotz via an e-mail discussion, Try: 1) Playing with the numerical emphasis parameter. 2) Reading the problem into interactive cplex and displaying the problem stats to see if the problem is poorly scaled. If there are more than 10 orders of magnitude separating the largest and smallest numerical values in A, b, and/or c, then the data need to be rescaled. answered 14 Jul '12, 16:35 Carleton 292●1●4 accept rate: 0%
 1 I don't have my CPLEX docs handy (and, oddly, the coffee shop I'm sitting in doesn't seem to have a copy), but you should be able either to track basis condition numbers (kappa values) or stop the optimization when a negative one zillion dual objective occurs and grab the kappa for the last basis. That will let you judge whether it's a numerical instability problem (which I think highly likely). Plus, I second what Bo said. answered 13 Jul '12, 18:01 Paul Rubin ♦♦ 14.6k●5●13 accept rate: 19% Cplex manual - The starbucks version for the "salesman" on the move... (13 Jul '12, 18:05) Bo Jensen ♦
 0 I warmly thank Bo, Carleton, and Paul for their useful answers. As said, you could (should?) ask such product specific question on our support forum: http://www.ibm.com/developerworks/forums/forum.jspa?forumID=2059 answered 16 Jul '12, 06:23 jfpuget 2.5k●3●10 accept rate: 8%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×191
×21
×6
×2
×1