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's gravatar image

SurfsUp
31113
accept rate: 0%

edited 14 Jul '12, 16:45

fbahr's gravatar image

fbahr ♦
4.6k716

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

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.

-

link

answered 12 Jul '12, 09:38

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919
accept rate: 14%

edited 12 Jul '12, 10:15

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.

link

answered 14 Jul '12, 16:35

Carleton's gravatar image

Carleton
29214
accept rate: 0%

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.

link

answered 13 Jul '12, 18:01

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Cplex manual - The starbucks version for the "salesman" on the move...

(13 Jul '12, 18:05) Bo Jensen ♦

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

link

answered 16 Jul '12, 06:23

jfpuget's gravatar image

jfpuget
2.5k310
accept rate: 8%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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

Asked: 12 Jul '12, 09:07

Seen: 23,315 times

Last updated: 19 Jul '12, 18:20

OR-Exchange! Your site for questions, answers, and announcements about operations research.