I have need the yours help,

I use the glpsol 4.39 for solve to= integer problem but I have the serious problem becouse when the sover begi= ns the integer optmization after a series of Warning it stops and provides =

following error:

* 3798: obj =3D 4.500000000e+0= 02 infeas =3D 1.532e-007 (0)

* 3800: obj =3D 4.5000000= 00e+002 infeas =3D 1.532e-007 (0)

Warning: numerical instability (= primal simplex, phase II)

3880: obj =3D 2.133333333e+= 001 infeas =3D 5.492e-002 (0)

* 3946: obj =3D 2.133333= 333e+001 infeas =3D 3.536e-008 (0)

Warning: numerical instability = (primal simplex, phase II)

3979: obj =3D 1.536000000e= +001 infeas =3D 2.673e-005 (0)

Warning: numerical instability (pri= mal simplex, phase I)

3996: obj =3D 1.536000000e+001&= nbsp; infeas =3D 5.094e-001 (0)

4000: obj =3D 1.53600= 0000e+001 infeas =3D 4.128e-001 (0)

Warning: numerical instability= (primal simplex, phase I)

4116: obj =3D 1.536000000e= +001 infeas =3D 4.128e-001 (0)

4200: obj =3D 1.= 536000000e+001 infeas =3D 3.997e-001 (0)

Warning: numerical instab= ility (primal simplex, phase I)

4206: obj =3D 1.53600= 0000e+001 infeas =3D 4.128e-001 (0)

Warning: numerical instability= (primal simplex, phase I)

4239: obj =3D 1.536000000e= +001 infeas =3D 4.128e-001 (0)

Warning: numerical instability (pri= mal simplex, phase I)

4348: obj =3D 1.536000000e+001&= nbsp; infeas =3D 4.128e-001 (0)

4400: obj =3D 1.53600= 0000e+001 infeas =3D 4.116e-001 (0)

Warning: numerical instability= (primal simplex, phase I)

4454: obj =3D 1.536000000e= +001 infeas =3D 4.128e-001 (0)

4600: obj =3D 1.= 536000000e+001 infeas =3D 1.974e-001 (0)

4800: obj = =3D 1.536000000e+001 infeas =3D 3.544e-002 (0)

= 5000: obj =3D 1.536000000e+001 infeas =3D 3.683e-003 (0)

&nb= sp; 5200: obj =3D 1.536000000e+001 infeas =3D 1.464e-003 = (0)

* 5263: obj =3D 1.536000000e+001 infeas =3D 4.750e= -010 (0)

* 5350: obj =3D 1.536000000e+001 infeas =3D 3= .779e-008 (0)

OPTIMAL SOLUTION FOUND

Integer optimization begins...

Warning: numerical insta= bility (dual simplex, phase II)

8400: obj =3D 1.62242= 5024e+001 infeas =3D 8.375e+004 (0)

8600: obj =3D&nbs= p; 1.895000000e+001 infeas =3D 7.889e+004 (0)

8800: o= bj =3D 2.040354491e+001 infeas =3D 7.881e+004 (0)

&nbs= p; 9000: obj =3D 2.255415671e+001 infeas =3D 7.553e+004 (0)

= 9200: obj =3D 2.239914212e+001 infeas =3D 6.271e+0= 04 (0)

9400: obj =3D 2.252087341e+001 infeas = =3D 5.111e+004 (0)

9600: obj =3D 2.211764706e+001&nbs= p; infeas =3D 4.167e+004 (0)

9800: obj =3D 2.30576923= 1e+001 infeas =3D 4.064e+004 (0)

10000: obj =3D 2.305= 769231e+001 infeas =3D 4.064e+004 (0)

10200: obj =3D = 2.305769231e+001 infeas =3D 3.888e+004 (0)

10400: obj =3D&n= bsp; 2.305769231e+001 infeas =3D 3.247e+004 (0)

10600: obj = =3D 2.305769231e+001 infeas =3D 2.965e+004 (0)

10800:= obj =3D 2.213176676e+001 infeas =3D 2.855e+004 (0)

1= 1000: obj =3D 2.211764706e+001 infeas =3D 2.726e+004 (0)

War= ning: numerical instability (primal simplex, phase I)

11028: obj = =3D 2.211764706e+001 infeas =3D 2.673e+004 (0)

Warning: nume= rical instability (primal simplex, phase I)

11030: obj =3D = 2.211764706e+001 infeas =3D 2.778e+005 (0)

Warning: numerical inst= ability (primal simplex, phase I)

11031: obj =3D 4.52557878= 0e+001 infeas =3D 2.588e+004 (0)

Warning: numerical instability (p= rimal simplex, phase I)

11108: obj =3D 3.234802074e+001&nbs= p; infeas =3D 2.263e+004 (0)

11200: obj =3D 3.234802074e+00= 1 infeas =3D 2.263e+004 (0)

11400: obj =3D 3.23480207= 4e+001 infeas =3D 2.263e+004 (0)

11600: obj =3D 3.234= 802074e+001 infeas =3D 2.263e+004 (0)

Warning: numerical instabili= ty (primal simplex, phase I)

11661: obj =3D 1.257798385e+00= 1 infeas =3D 4.691e+004 (0)

Warning: numerical instability (primal= simplex, phase I)

11662: obj =3D 1.638371041e+001 in= feas =3D 2.348e+004 (0)

Warning: numerical instability (primal simplex, = phase I)

11665: obj =3D 1.768067227e+001 infeas =3D 2= .340e+004 (0)

Warning: numerical instability (primal simplex, phase I)

11667:= obj =3D 1.413832339e+000 infeas =3D 2.360e+004 (0)

1= 1800: obj =3D 1.075646683e+001 infeas =3D 2.337e+004 (0)

&nb= sp; 12000: obj =3D 1.075646637e+001 infeas =3D 2.337e+004 (0)

12400: obj =3D 1.484263291e+001 infeas =3D 2.316e= +004 (0)

12600: obj =3D 1.958018804e+001 infeas =3D 2= .310e+004 (0)

12800: obj =3D 2.355981856e+001 infeas = =3D 2.299e+004 (0)

13000: obj =3D 2.457031250e+001 in= feas =3D 2.262e+004 (0)

13200: obj =3D 2.457031250e+001&nbs= p; infeas =3D 2.262e+004 (0)

13400: obj =3D 2.457031250e+00= 1 infeas =3D 2.237e+004 (0)

13600: obj =3D 2.45703125= 0e+001 infeas =3D 2.226e+004 (0)

13800: obj =3D 2.457= 031250e+001 infeas =3D 2.226e+004 (0)

14000: obj =3D = 2.457031250e+001 infeas =3D 2.210e+004 (0)

14200: obj =3D&n= bsp; 4.379007521e+001 infeas =3D 2.189e+004 (0)

14400: obj = =3D 5.369333333e+001 infeas =3D 1.829e+004 (0)

14600:= obj =3D 5.450620690e+001 infeas =3D 1.402e+004 (0)

1= 4800: obj =3D 5.450620690e+001 infeas =3D 1.255e+004 (0)

&nb= sp; 15000: obj =3D 5.450101169e+001 infeas =3D 1.224e+004 (0)

15400: obj =3D 2.774705321e+001 infeas =3D 1.080e= +004 (0)

15600: obj =3D 2.578124476e+001 infeas =3D 1= .027e+004 (0)

15800: obj =3D 2.578342748e+001 infeas = =3D 8.535e+003 (0)

16000: obj =3D 2.507363461e+001 in= feas =3D 8.315e+003 (0)

16200: obj =3D 2.532280750e+001&nbs= p; infeas =3D 7.344e+003 (0)

16400: obj =3D 2.532214850e+00= 1 infeas =3D 4.985e+003 (0)

16600: obj =3D 2.53160570= 9e+001 infeas =3D 4.432e+003 (0)

16800: obj =3D 2.481= 585932e+001 infeas =3D 4.273e+003 (0)

17000: obj =3D = 2.455727186e+001 infeas =3D 4.233e+003 (0)

17200: obj =3D&n= bsp; 2.449272181e+001 infeas =3D 4.225e+003 (0)

17400: obj = =3D 2.449185306e+001 infeas =3D 4.225e+003 (0)

17600:= obj =3D 2.580778477e+001 infeas =3D 4.092e+003 (0)

1= 7800: obj =3D 2.557197523e+001 infeas =3D 4.035e+003 (0)

&nb= sp; 18000: obj =3D 2.556749134e+001 infeas =3D 4.032e+003 (0)

18400: obj =3D 2.565202748e+001 infeas =3D 4.014e= +003 (0)

18600: obj =3D 2.510221488e+001 infeas =3D 3= .996e+003 (0)

18800: obj =3D 2.457184842e+001 infeas = =3D 3.588e+003 (0)

Warning: numerical instability (primal simplex, phase= I)

18902: obj =3D 7.403277042e+000 infeas =3D 2.181e= +005 (0)

Warning: numerical instability (primal simplex, phase I)

&nb= sp; 18903: obj =3D -6.093643043e+001 infeas =3D 3.044e+005 (0)

War= ning: numerical instability (primal simplex, phase I)

18904: obj = =3D -6.931097193e+001 infeas =3D 3.143e+005 (0)

Warning: numerical= instability (primal simplex, phase I)

18909: obj =3D -2.62641882= 0e+003 infeas =3D 1.359e+006 (0)

Warning: numerical instability (p= rimal simplex, phase I)

18922: obj =3D -4.342685881e+002 in= feas =3D 1.125e+006 (0)

Warning: numerical instability (primal simplex, = phase I)

18923: obj =3D -3.219125747e+002 infeas =3D 1.055e= +006 (0)

Warning: numerical instability (primal simplex, phase I)

&nb= sp; 18989: obj =3D -3.992741648e+002 infeas =3D 9.077e+005 (0)

War= ning: numerical instability (primal simplex, phase I)

18990: obj = =3D -5.474916752e+002 infeas =3D 8.893e+005 (0)

Warning: numerical= instability (primal simplex, phase I)

18992: obj =3D 2.348= 451895e+002 infeas =3D 9.200e+005 (0)

19000: obj =3D = 2.330763120e+002 infeas =3D 9.115e+005 (0)

Warning: numerical inst= ability (primal simplex, phase I)

19136: obj =3D 2.77501031= 0e+003 infeas =3D 8.735e+005 (0)

Warning: numerical instability (p= rimal simplex, phase I)

19142: obj =3D 4.511997575e+012&nbs= p; infeas =3D 2.111e+014 (0)

Warning: numerical instability (primal simp= lex, phase I)

19143: obj =3D -5.785084625e+001 infeas =3D 1= .020e+006 (0)

Warning: numerical instability (primal simplex, phase I)

Warning: numerical instability (primal simplex, phase I)

1= 9164: obj =3D -8.287391196e+002 infeas =3D 7.722e+005 (0)

Warning:= numerical instability (primal simplex, phase I)

19166: obj =3D -= 9.364509697e+004 infeas =3D 7.476e+006 (0)

Warning: numerical inst= ability (primal simplex, phase I)

19168: obj =3D -5.333885292e+00= 2 infeas =3D 8.959e+005 (0)

Warning: numerical instability (primal= simplex, phase I)

19169: obj =3D 4.885836875e+002 in= feas =3D 1.718e+006 (0)

Error: unable to factorize the basis matrix (1)<= br>Sorry, basis recovery procedure not implemented yet

ios_driver: unabl= e to solve current LP relaxation; glp_simplex

+ 19172: mip =3D &nbs= p; not found yet >=3D &nb= sp; -inf &= nbsp; (1

glp_intopt: cannot solve current LP relaxation

Time us= ed: 102.6 secs

Memory used: 430.8 Mb (451738750 bytes)

I tried already to not use the pres= over.

Help me help me help me.

t= hanks you

Una risposta istantanea? Usa= Messenger da Hotmail ------------E6555324B364FE-- From MAILER-DAEMON Thu Sep 03 15:14:11 2009 Received: from mailman by lists.gnu.org with archive (Exim 4.43) id 1MjHl5-0003Jb-Fq for mharc-bug-glpk@gnu.org; Thu, 03 Sep 2009 15:14:11 -0400 Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1MjHl2-0003G8-M5 for bug-glpk@gnu.org; Thu, 03 Sep 2009 15:14:08 -0400 Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1MjHkx-00039p-NJ for Bug-glpk@gnu.org; Thu, 03 Sep 2009 15:14:08 -0400 Received: from [199.232.76.173] (port=36046 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1MjHkx-00039b-Gw for Bug-glpk@gnu.org; Thu, 03 Sep 2009 15:14:03 -0400 Received: from kuber.nabble.com ([216.139.236.158]:46284) by monty-python.gnu.org with esmtps (TLS-1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from

When "\n" is= used in a printf statement, it provides a new line - but when used as a re= placement for %s in an if..then..else clause within a printf statement, it = just writes out \n.

Add other email accounts to Hotmail in 3= easy steps. Find out how. ------------641671F721BAAB1A-- From MAILER-DAEMON Sun Sep 13 15:57:37 2009 Received: from mailman by lists.gnu.org with archive (Exim 4.43) id 1MmvCb-0000eA-Oz for mharc-bug-glpk@gnu.org; Sun, 13 Sep 2009 15:57:37 -0400 Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1MmvCa-0000c3-B1 for bug-glpk@gnu.org; Sun, 13 Sep 2009 15:57:36 -0400 Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1MmvCZ-0000aa-Bx for bug-glpk@gnu.org; Sun, 13 Sep 2009 15:57:35 -0400 Received: from [199.232.76.173] (port=49696 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1MmvCZ-0000aB-5n for bug-glpk@gnu.org; Sun, 13 Sep 2009 15:57:35 -0400 Received: from ppp85-141-153-61.pppoe.mtu-net.ru ([85.141.153.61]:14993 helo=localhost) by monty-python.gnu.org with esmtpsa (TLS-1.0:RSA_3DES_EDE_CBC_SHA1:24) (Exim 4.60) (envelope-from

I've been using the solver for a month or two now a= nd there are many things I really like about it, in particular the cleanlin= ess of the code, it is very easy to see what is going on and make experimen= tal changes.=A0 The main reason I'm writing is to ask if there is any b= uilt-in provision for avoiding degeneracy cycling and what people's pla= ns/thoughts are on the issue.=A0 I don't mean the problem of losing fea= sibility, re-entering phase 1 with consequent worsening of the objective fu= nction and thereby repeating a basis, I'm talking about when you perfor= m a number of consecutive degenerate pivots that don't improve the obje= ctive and eventually return to the same basis.

The manual and the code don't make any reference to this, so I assu= me there isn't any anti-cycling, for a while I was thinking that the he= ad[m+1..m+n] array of non-basic variables was maintaining an implicit order= ing somewhat like Bland's rule, but then I realized that there is no or= dering on the leaving variables, see chuzr in glpspx01.c for example, in ca= se of a tie between leaving variables it tries to choose the one with the l= argest coefficient in that column of the tableau.=A0 (Note:=A0 No tolerance= is used when making the test for a tie, I suggest adding one could enable = choosing a larger coefficient and thus a better conditioned matrix, does ev= eryone agree?).=A0 So I guess cycling can occur, has anybody tried entering= one of the textbook examples to see whether it really happens?

So anyway, I tried implementing Bland's rule, it was easy to do, I = just check if the previous pivot was degenerate, and if so, use Bland's= pivot selection instead of the normal one.=A0 Unfortunately this unreasona= bly hurt performance on the normal (non cycling) case, i.e. it led to lengt= hy stalls, as my problems contain a lot of degeneracy and the Bland pivot r= ule doesn't attempt to choose a row with a good reduced cost for entry.= =A0 So I also tried the Cacioppi & Schrage rule described by Richard Ki= pp Martin (Large Scale Linear & Integer Optimization, p171-172, you can= find this in Google Books).=A0 I don't know if I implemented it correc= tly though, because it's supposed to address this problem by forcing ve= ry few restrictions on the entering/leaving variables, but I observed much = stalling still.

Eventually what solved the problem for me was a perturbation of the rig= ht-hand sides, note that I hadn't actually observed cycling in practice= but I did observe lengthy stalls with the standard code, the perturbation = fixed this and led to a dramatic improvement.=A0 I did it by adding, to eac= h lb[1..m] and ub[1..m] pair, a random number in the range -1e-5..1e-5.=A0 = I didn't bother removing the perturbation afterwards, as the accuracy o= f the results was suitable for my purpose, but I would suggest that if doin= g e.g. primal simplex, then after reaching optimality we have a primal/dual= feasible solution, and removing the perturbation amounts to changing the d= ual objective, so we wouldn't lose dual feasibility and we could contin= ue to optimize with dual simplex until the true optimum is reached.

Another way of doing the perturbation is to note that the solver doesn&= #39;t normally work with a right-hand side, e.g. an equation like x+y+z<= =3D5 is changed to s-x-y-z=3D0 with s<=3D5, rather than x+y+z-s=3D5 with= s>=3D0 as in the textbook way of doing things.=A0 We could introduce a = right-hand side, containing only the small perturbations, so e.g. the calcu= lation of x_B (bbar) would be done as

=A0 x_B =3D A_B^{-1} (b - A_N x_N)

where b is the perturbation, rather t= han

=A0 x_B =3D -A_B^{-1} A_N x_N

as we are currently doing.=A0 This = kind of approach might be a bit more elegant and avoid having to save the l= b/ub arrays for when the perturbation is removed.

Some other suggestions:=A0 We maintain a copy of the row-representation= of N (as suggested by Bixby) for the cbar and gamma recurrences, but the c= ode to delete a column of N as it's pivoted into the basis doesn't = look particularly efficient, I made a version where the N is constructed on= ce at the start, really just a row-representation of the full coefficient m= atrix (I | -A), and extra columns are simply ignored when updating cbar and= gamma.=A0 I also made the cbar and gamma arrays a bit bigger so there is a= space for every variable rather than only the non-basic variables, so that= they correspond with the columns of (I | -A) and make the addressing a bit= easier.=A0 For the gamma array I put an inner-loop test to avoid updating = the basic variables, but for cbar I didn't bother with such a test.

I also think more diagnostic output would be good, I added a counter fo= r how many degenerate pivots have occurred (next to the iteration counter),= I'm also planning to output a count of how many nonzeros occur in the = basis factorization, as I'm keen to know the effect of different pivoti= ng strategies (including adding the tolerance in chuzr that I mentioned ear= lier) on the sparseness of the basis inverse.=A0 Does anyone have a good re= ference for a devex-like pivoting strategy that attempts to keep the basis = as sparse as possible?=A0 Because I think this would be really helpful for = my (very large) problems.=A0 Another change I was thinking of making, is th= at when we construct the pivot row, we should apply a tolerance in the test= for zero, improving the sparseness, but I haven't tried this yet.

Another thing I did was to implement a GLP-native format for storing th= e LP, I did this rather reluctantly as the world doesn't really need ye= t another competing format, but the problem with MPS is that it doesn't= save the minimization/maximization flag and with CPLEX LP format it doesn&= #39;t save the objective function coefficient.=A0 Also, at least with CPLEX= LP, the rows are loaded in a different order (they are entered as they are= encountered in the file), which wasn't acceptable for my purpose, in f= act it was very misleading and I wasted a fair bit of time wondering why my= post-solution analyzer wasn't working properly.=A0 The new format is v= ery similar to the solution files already output, I did it by modifying glp= _write_sol and glp_read_sol to create glp_write_glp and glp_read_glp.=A0 I = also added a new --basis option for glpsol, so that it can read (non-optima= l) a solution file written by glp_write_sol and use it as the starting basi= s.

One last comment, the current arrangements aren't very good for a c= aller that wishes to solve, make some changes in the model, resolve etc.=A0= In particular I'm talking about the init_csa routine e.g. in glpspx01.= c, which insists on making a copy of the entire problem every time it is en= tered, could we make this incremental and only merge in the changes to the = problem to its private data structures?

Sorry, this turned into a bit of an essay, but what does everyone think= ?=A0 Should I upload some of my code?=A0 It's not particularly clean at= the moment, but it would probably be a starting point.

cheers, Nick=

--0016e6d3e227aa40980474b187c8--