Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

scipy.optimize.linprog failed to find a feasible starting point while solution exists #6139

Closed
cy18 opened this issue May 5, 2016 · 21 comments · Fixed by #9272
Closed

scipy.optimize.linprog failed to find a feasible starting point while solution exists #6139

cy18 opened this issue May 5, 2016 · 21 comments · Fixed by #9272
Labels
defect A clear bug or issue that prevents SciPy from being installed or used as expected scipy.optimize
Milestone
1.2.0

Comments

@cy18
Copy link

cy18 commented May 5, 2016

Following code will cause this problem

from scipy import array, vstack, hstack
from scipy.optimize import linprog
from scipy.linalg import solve

f1 = array([[1., 0., 0.], [-1000., 0., - 1000.]])
g1 = array([5.00000000e+00, -1.00000000e+04])
f2 = -array([[0., 1000000., 1010000.]])
g2 = -array([10000000.])

sol = solve(vstack([f1, f2]), hstack([g1, g2-1]))
assert (f1@sol == g1).all()
assert (f2@sol < g2).all()
ret = linprog([1]*3, f2, g2, f1, g1, bounds=[(None, None)]*3)
print(ret)

sol is obviously a feasible solution, but the result message is "Optimization failed. Unable to find a feasible starting point."

Is it a bug or I did something wrong?

I'm using scipy 0.17.0 from http://www.lfd.uci.edu/~gohlke/pythonlibs/#scipy under Windows 10/Python3.5.
@argriffing
Copy link
Contributor

argriffing commented May 5, 2016 •
edited
Loading

I'm not planning to look at this in detail, but I suspect it's a numerical issue like #5400. cc @robfalck

@cy18
Copy link
Author

cy18 commented May 5, 2016 •
edited
Loading

I don't think it's caused by floating error. There are three variables, and only two equations and one inequality. Solutions should always exists. I suspect it's related to bounds, since the issue do not exists for -f2 and -g2.

@argriffing
Copy link
Contributor

If you scale the whole system by 0.001 then the problem goes away, so I think it's caused by floating error at some level. But that doesn't mean it's not a bug. Maybe some part of the algorithm should be changed to use relative tolerances instead of absolute tolerances.

@robfalck
Copy link
Contributor

robfalck commented May 5, 2016

There are corner cases that cause stage one of the two stage linear
programming routine to fail to find a feasible starting point. This
appears to be one such case
On May 5, 2016 6:30 PM, "cy18" notifications@github.com wrote:

I don't think it's caused by floating error. There are three variables,
and only two equations and one inequality. Solutions should always exists.
I suspect it's related to bounds, since the issue do not exists for -f2 and
g2.

—
You are receiving this because you were mentioned.
Reply to this email directly or view it on GitHub
#6139 (comment)

@ev-br ev-br changed the title scipy.optimize.linalg failed to find a feasible starting point while solution exists scipy.optimize.linprog failed to find a feasible starting point while solution exists May 16, 2016
@ev-br ev-br added scipy.optimize defect A clear bug or issue that prevents SciPy from being installed or used as expected labels May 18, 2016
@mdhaber
Copy link
Contributor

mdhaber commented Feb 21, 2017 •
edited
Loading

Below is another example of this behavior.
The problem was randomly generated - and was actually the first such randomly generated problem of this form (Zionts 1 from "Performance evaluation of a family of criss-cross algorithms for linear programming") that I was trying.

import json
from scipy.optimize import linprog
import numpy as np
s = '{"c": [-1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1], "b_ub": [-100, 10000, -100, 10000, -100, 10000, -100, 10000, -100, 10000, -100, 10000, -100, 10000, -100, 10000, -100, 10000, -100, 10000, -100, 10000, -100, 10000, -100, 10000, -100, 10000, -100, 10000, -100, 10000, -100, 10000, -100, 10000, -100, 10000, -100, 10000], "A_ub": [[-549.2646904233974, -715.4741770060471, -603.1606126955722, -545.3382998139, -424.2311445395658, -646.2482189535895, -438.14962405142984, -891.8812277812976, -963.6990977405283, -384.05807730695193, -791.933313044582, -529.3660248331515, -568.4765165328383, -925.6710416543684, -71.96502213968905, -88.04217040183917, -21.198179042885393, -832.7872257023901, -778.3785941989006, -870.1421360985723, -978.6397238905313, -799.3594056525069, -462.0178828906789, -780.748647110169, -119.15615144306429, -640.2811003061963, -144.20993412163736, -944.7242481325343, -522.3264734283216, -415.24727805053305, -265.29105649252233, -774.4594557447824, -456.694181884332, -568.8655149197799, -19.77101063591879, -618.0178615788012, -612.483626999699, -617.3170628778821, -943.8043304361096, -682.1384788043799, -360.14839267321224, -437.5949218455421, -697.9335647313376, -61.16524615764057, -667.099948730222, -670.9672317485413, -211.17217851276706, -129.79737135719844, -316.11292257325965, -364.34706017167997, -570.6265736474618, -439.16291194885804, -988.385464221167, -102.94276593728004, -209.66787933873985, -162.14820836711127, -653.455217139933, -254.03831093724233, -466.84446208344997, -245.18116640960113], [159.8106140618742, 111.26476602314084, 656.6732598758082, 139.0447683972652, 197.38577931837344, 369.35644549030314, 821.1722366180871, 98.00417451726821, 838.1069625913051, 97.00230948606911, 976.4830055483824, 469.1825504460539, 976.7843271021468, 605.240674225301, 739.5243158189033, 40.14860446206635, 283.52415561383316, 121.07636465195574, 296.8440573246228, 119.6089912352898, 318.66519621458207, 414.8487315201553, 65.08334885243558, 692.7796472506499, 567.0348527523686, 266.124101448506, 523.724805413233, 94.84657024768323, 576.3705490606231, 929.3669013786379, 319.25038349887234, 667.742969583718, 132.6660645419878, 716.610876914447, 290.1166868542539, 184.00817064510971, 586.926421875273, 21.087438641306058, 829.1110891881457, 5.690780716354519, 678.1387202594339, 270.7379652189727, 735.4588281004723, 962.2263565723208, 249.50439037643807, 576.5811770834191, 592.4498893405672, 572.6796538850825, 223.8585510079777, 952.796262505468, 447.67825323900973, 846.5622637986567, 699.7797960421868, 298.13951390427854, 813.9840218827748, 397.10923510613765, 881.2220939140504, 581.6915997632228, 881.8536264929979, 692.8390584876881], [-725.5290255398209, -501.82305754477557, -956.1275510885007, -644.3462090304077, -424.4311935096215, -606.7868209137964, -20.174005111024194, -302.2732418578748, -660.5133639551924, -290.7875296032336, -618.3974135698427, -429.3399322448204, -136.3385901582278, -298.9840436300747, -570.3949457905636, -591.281888486925, -574.7509236007293, -653.5476190372765, -652.4511667316872, -431.98701699853996, -896.6500492552119, -368.19430817784865, -436.42906034036116, -892.0314316606564, -806.3877950570396, -704.184694956826, -101.12666042498881, -919.5631311309289, -714.5270582495623, -998.8481595612986, -150.29885635333576, -868.2579313108461, -163.33044174169845, -615.9440047195603, -124.69616286659208, -848.1602210929121, -807.5116397662857, -569.5316378759787, -407.77611392877367, -70.09782845968292, -697.731344371419, -454.0891399953908, -722.3335438708775, -866.5159436027005, -975.545983497883, -855.9475390502184, -12.70237010081697, -360.6180864138855, -730.2605718616339, -172.45804758417907, -521.5155695979252, -55.28365035091438, -200.79652837150368, -19.503272666153357, -793.9040056540632, -224.70076337231976, -346.00632901620577, -928.1532121721253, -704.7099875216093, -32.80709060177654], [165.52946234141484, 621.8569230982638, 577.6513600155635, 238.6549285531341, 934.279783926869, 614.3519900099301, 536.0971702219333, 590.3200663782164, 730.3919074872529, 312.63305048412224, 398.8228411538758, 210.63390522614702, 187.00681287445582, 944.4280175939497, 739.8112442542383, 490.9683498089495, 228.1872133453499, 255.10212528862255, 58.97113116355174, 434.9822089325626, 312.48408611210846, 696.647145326644, 378.37408745318845, 180.42407388207516, 25.654049662939897, 68.18238183178534, 679.7133807250688, 454.24314771148926, 537.0426318976134, 896.7746217473018, 990.3486084493077, 217.68008741407547, 663.4151248970007, 264.0590543604135, 21.63034846626295, 758.6202751823052, 320.69713367164536, 384.08043027772607, 588.7287964400521, 831.2174067809542, 629.3528617475575, 872.7780047919479, 274.2684927808201, 798.2487870786512, 186.45030836164625, 952.8388653149726, 687.8007881114274, 216.29216943644488, 947.4232198984354, 731.1249509633876, 254.68770095243082, 214.0986653901145, 518.6825132167326, 26.637055336477044, 208.2626053656683, 425.26078328275474, 374.79581035389134, 464.1118489404459, 278.3510775884372, 587.1975621117106], [-863.9917503173082, -118.41432410607105, -517.86172804696, -132.93603823880815, -717.142821511401, -396.6636431044864, -565.8558905466505, -184.09655637786454, -145.70291158403387, -488.5682243683056, -356.25712511210565, -940.4915133075602, -765.5599285531583, -748.9149562306967, -903.8160200061875, -84.33901300657654, -552.6402774524842, -584.8915928868131, -961.9744421686818, -292.8553792657563, -241.58795113553137, -101.19364832323232, -17.41319996188273, -929.5997874753983, -670.2466300443191, -785.3677591111147, -282.4483756481951, -586.8237560201403, -64.89131085486014, -486.1419683386883, -977.5176446047024, -876.6287400712743, -338.8207928850088, -961.608584386957, -232.4699248447333, -949.3695035932658, -941.4363270017922, -799.4033847650393, -630.8174889299244, -874.413678658322, -293.7272642232889, -849.0946117576053, -618.2588152256063, -14.22362090114059, -347.88628441428733, -148.99272008721687, -981.8475604284349, -478.89193673294807, -497.893974133164, -639.8330438823249, -369.2160215234879, -137.76337141391332, -822.2956154610513, -190.6580639908552, -511.80766356390956, -225.09271194576453, -98.74664000954002, -862.3293259042616, -972.9465695341072, -960.8738234049372], [906.6489437219577, 774.2732853659402, 333.8120068766133, 82.02028859800876, 407.83393024239354, 233.0019080287718, 133.35514712322498, 54.373754605038435, 725.8687698463682, 12.416031166405997, 770.8101677542735, 147.79969875497468, 80.442560504169, 90.51343120436678, 672.3757595465605, 246.12184264299194, 421.1189272134184, 557.811422532593, 860.690622654965, 727.3172184486169, 271.05757733347593, 132.35131649183649, 56.31894610077674, 302.29703584646154, 262.8560310904386, 456.6844262336792, 683.5980542121328, 695.9298201932183, 284.23532773558446, 380.54702894422036, 181.96981077516614, 788.7569667942122, 57.79122835680706, 697.3002444832623, 778.9167005451623, 777.6301542869044, 260.1631417810096, 374.4393247946289, 588.0120355611926, 273.5490805220426, 371.4819464186708, 197.85722590545402, 460.3960278722514, 45.56768895285997, 799.9960886860474, 77.8794905396461, 519.3163136826945, 307.5032894456509, 577.9654058825441, 959.4739074925917, 645.9246742115479, 36.327073319735426, 430.97203706855316, 510.506835465932, 536.6413172087485, 681.7111180932341, 278.3185016340343, 129.73170490085386, 393.28300087054726, 956.4493170731529], [-187.94376085909389, -904.0799709733088, -544.262144127249, -457.45451022412004, -882.1593688196597, -459.1453578068173, -724.4434689749318, -399.6262963813989, -904.1403485080567, -690.3349951710361, -699.9224321962662, -328.3926811555618, -757.0218640941523, -636.4249943916942, -240.78025310632984, -161.37828366277117, -796.5950830428144, -959.2074364321873, -458.6806884327828, -591.3931811583612, -857.864921549361, -457.7662299005032, -951.9226023559035, -576.1754108828276, -820.9463535806136, -908.9348746943256, -815.7082949498002, -160.255048985507, -629.2695406226387, -399.0358243610574, -63.65023907132236, -424.6082196379521, -259.4253828225183, -849.1892701200823, -34.2713219201495, -959.0237391416101, -356.01347962345767, -357.35018351214035, -17.312174181024183, -186.04709291094775, -401.85824130280514, -929.3621258854112, -100.51531529105006, -945.3562319456005, -869.6190420160856, -454.7082345106442, -327.3741808864918, -233.5113851497778, -614.8502417703975, -34.041516884030116, -16.59045838238139, -429.3669267757396, -69.00599990074548, -252.6890472578468, -221.93975443073776, -253.93800252912908, -131.9241759840425, -13.024186674756615, -116.36881284160934, -618.8617792532351], [974.2819566052323, 990.354656559333, 409.6450412776885, 163.79147162055875, 639.1229956091628, 490.8150412021884, 989.420367507147, 66.23890294462842, 783.4512038754993, 289.11009883416244, 242.17720145649741, 662.8420669611432, 246.8171218059735, 666.1932584416285, 517.7912086850865, 424.66489944741346, 555.1331208527575, 287.7644683997101, 706.868131566706, 415.44201246423046, 361.1850149254064, 828.8282576411821, 925.0419450412389, 46.96130357640963, 233.39436583693575, 349.1708501230707, 815.1515128908771, 985.5059362156543, 969.0027329656814, 905.0433972043769, 297.25970879896585, 992.0192321710597, 250.17062101539477, 106.80024872734998, 951.0016584443387, 234.1868352126282, 690.0784968126727, 59.29800262160808, 730.9783900283487, 881.8384921215059, 273.16445857049655, 379.6778391813511, 374.92188713759515, 749.039469282593, 238.5694352964998, 172.68124594859538, 449.84235703905034, 305.1639389699422, 839.3499331363937, 238.50408418962311, 502.8870680317722, 942.6410160982324, 634.363700046916, 867.4221160570023, 940.2694796654125, 751.0140970244656, 699.8754851645266, 967.9976010376229, 994.4063888580317, 452.36986098708985], [-71.79890840602415, -293.5012374090783, -153.20235098204273, -418.0688884212158, -132.15803914478278, -604.5136862168611, -383.42525109869626, -895.4904984039217, -967.8268771267034, -547.3380167677527, -275.548746297729, -592.638188343075, -896.8643970661855, -407.3266124899125, -552.5261984152788, -272.3811148385397, -455.98870530057695, -402.311821844219, -249.16505161788805, -506.36051744148307, -311.0704451538316, -373.6618290168667, -525.4454718120099, -750.8444279060585, -334.173958325484, -924.2346078541428, -862.4562282890664, -49.64160567955301, -254.38888173256595, -446.6893771465427, -105.52326085373161, -349.12751304446357, -740.3574280920648, -680.833966661683, -622.7620441374388, -710.8178743196232, -205.71876327274205, -342.3564167498674, -676.5662397951854, -879.3555282682958, -544.1343757742671, -283.41695129459106, -31.205022747976606, -710.6264921452391, -8.876219404931936, -373.30639075117455, -531.006677348219, -922.1893503054258, -90.40505048786721, -406.5363796463154, -25.288886510447615, -343.2683733572487, -622.6088277809552, -279.78888028036977, -210.54019970597946, -116.58753009376655, -577.5631037763214, -695.5747358987813, -672.2851834552265, -948.9121596997869], [3.7005106796091956, 647.549457240142, 600.7918448605419, 589.1508703603179, 962.8075495204022, 17.854801696669657, 696.7859482707487, 813.8649710521615, 510.29738942496255, 334.63090472721234, 791.0493230641775, 98.14568270679223, 442.59360209219534, 520.4324221962673, 694.262454523613, 91.79484630037705, 228.5317420363231, 410.8912611274355, 623.6713783471105, 887.0738204362001, 619.2073420731351, 134.3280094639995, 980.5995526544951, 871.9139490207374, 503.2180403841787, 922.4256338148364, 541.8394129633787, 923.382761821274, 830.0674712347399, 968.318123884003, 919.8630279673802, 36.99778361114091, 175.59723215677903, 389.7455424240846, 952.1905545981253, 300.7288905564536, 161.30717624371343, 886.4183614204733, 446.9480210677197, 907.9677187599717, 161.0702358538231, 661.4563939965914, 440.8234890766623, 77.4102822612551, 696.766681507848, 248.15135678361455, 40.575907056938206, 60.88435395132368, 62.01745852972056, 907.8252245275544, 740.1440339112719, 898.1642948565213, 672.9097289852248, 529.4109891018522, 305.1419179830309, 997.9642890773448, 362.82686988045, 471.1783002646956, 378.8669297485383, 979.5474024061232], [-175.48372700961076, -328.66001290717156, -680.6683173489865, -64.14441072029202, -607.6421246375295, -478.16885637353965, -284.71597678533897, -239.17486764313395, -514.998230555458, -368.5596529565043, -457.0633713713927, -338.13990438247566, -970.5231999023816, -134.3059923138584, -97.70714922519583, -344.04833706212514, -591.4358739696207, -659.5172953781782, -397.859490420874, -999.278715928249, -352.5411031968496, -721.6852612919924, -637.9451118362621, -813.2408093842132, -976.2494377903662, -889.9038627890947, -764.7974123833509, -698.5502293404722, -336.1626715062237, -148.53789262850066, -63.57336705674995, -242.65980249728335, -432.8491997001173, -522.4742773563524, -773.3104705008168, -958.7821821335364, -118.20315990442622, -107.89713605359778, -590.1050282905372, -745.6526758733456, -848.3022299666379, -935.8962481365718, -983.4428160183813, -400.40189053230137, -380.95484834404556, -148.6608680205751, -685.2495042448759, -657.1051964823962, -862.200533255356, -98.16073679285299, -498.27913091751645, -581.500847742391, -242.3154829998785, -169.85638072303212, -859.7212555832018, -59.47638731332322, -471.1502830141548, -116.7181672995844, -457.60170257003597, -979.9823640159669], [424.28264710201734, 857.2677925870628, 118.1982486190107, 271.9808246851023, 404.3889479266672, 400.4123278693214, 671.712095191483, 345.37340924813213, 714.0531015416063, 639.5477123261671, 399.7619841095183, 432.3283675266649, 614.9131721105105, 70.97214795449999, 822.5843316173347, 653.7677399525232, 726.6161219534174, 537.386078081308, 111.36663388075299, 405.630577683653, 405.9682092657075, 321.72194705317366, 30.92037457984461, 737.5169883538808, 110.6746736044382, 606.70182491204, 703.5142789707486, 635.151536610761, 959.183109725997, 104.19485693005348, 867.299991946094, 30.16104461406434, 535.3819380721569, 404.8393743213195, 524.6596765333644, 365.73477718294976, 191.37634802512798, 20.10377455124109, 518.6316639773831, 842.9340858221575, 373.84273978904935, 223.64095419696525, 81.45147146837223, 86.22561219558466, 222.17504984647945, 100.91404686063363, 265.77465866611755, 67.08331265483775, 66.53926234271572, 856.4199034431591, 162.9581404481244, 560.1227234176246, 773.6820889045815, 456.95315577372753, 154.21550898148638, 200.39654597799424, 433.55122207489956, 528.7058550893572, 350.09085175648636, 781.6981206344267], [-751.270627207542, -927.2845955657448, -29.92359647793358, -895.7955999189932, -393.1762196736889, -878.4941228846141, -691.093991380373, -987.3614083168942, -759.5231692649514, -365.1800813707898, -501.56210966191736, -377.0127660391569, -365.5469241852169, -261.64359488167867, -496.4743250780961, -682.0582051242918, -278.0629310339383, -524.8554312661428, -118.26291387638662, -160.6854415673371, -47.75954835747656, -970.7607113278622, -4.856491158750834, -179.40138808959864, -613.2538863638754, -82.28822925445199, -882.0146065937355, -719.9005376844459, -966.4235814664555, -508.1279116935241, -301.1032794753287, -549.9510722224761, -930.8878985806751, -521.2406758046187, -267.9398248304563, -877.5213903849454, -372.54682976394884, -2.38196664900014, -248.43733746982363, -318.91527566788534, -858.9186907636703, -459.0446638993786, -445.14270052348945, -336.7661641334875, -880.7974449240326, -945.081750163451, -991.8984388254747, -377.36452569402576, -966.1812981815442, -792.0876900612705, -676.0134584966225, -245.6445899406793, -217.2408036832656, -166.88177669672442, -922.83385361514, -294.78258572078295, -453.64115120342956, -494.46387615323624, -778.3934238548039, -844.3907265914711], [139.9336284474642, 427.4774558508626, 843.0120329476217, 818.2152724500826, 103.31134469396399, 157.22696551909505, 304.8944929078084, 76.283710014257, 425.2383398377523, 108.51008744443233, 568.6493760761751, 247.31038287134496, 596.836632284273, 118.40811726073402, 975.9079845501149, 932.6286426534831, 392.4051416261011, 242.93641553195937, 251.1478146407192, 483.91014166718963, 40.95280909881625, 640.0654009690519, 408.89460543140507, 378.02916601629846, 809.5556065177092, 709.3264247231067, 954.3794815772993, 352.58430425519504, 897.6452218847561, 770.1972190638388, 358.0672269431183, 622.0437710168045, 289.2813876940439, 874.5255171577675, 113.31488989509894, 213.22192693274698, 183.85025878784123, 403.6229764018844, 745.487727072097, 527.3805416031281, 488.18864721466934, 1.5454189320986587, 425.97632362969966, 64.49022106132227, 209.04499886936233, 932.4615450215339, 216.18280613889496, 858.4793009956283, 803.0904781897729, 159.9870907053006, 606.1062453130086, 116.5462100331083, 728.160270211142, 637.8248150948344, 812.1266231293283, 479.9051648397989, 914.9482247455495, 50.29959784165127, 293.59567646198764, 715.3375448677018], [-418.69110253625286, -173.77840291688523, -108.10353468311749, -817.5217723501598, -473.6698354871786, -882.4013882471883, -733.5558451824094, -410.31647942511285, -374.137503141528, -516.1227083046005, -889.1708932365389, -737.5413011344538, -6.147811304754207, -694.4636935177564, -919.5878994989148, -710.745303744987, -177.82877578592843, -484.03460930003126, -141.175701905496, -359.63628306129243, -937.1799248985772, -923.3820022511496, -283.5540153239068, -340.29141312203296, -600.6126552631627, -963.2340979651196, -148.65353273132504, -257.65972704298247, -873.6832704634807, -492.4003394766362, -899.0621311348046, -186.3323796256531, -533.1359188838893, -326.94336301672297, -317.2260173325836, -447.43008698225293, -433.6443716521672, -357.98953279827646, -915.055799545303, -732.0124412474598, -727.8194443401982, -290.6235361423635, -578.1317148925235, -779.4002538685322, -795.7947781746699, -345.18593029355793, -771.1018838120792, -736.1580029109252, -142.36497913627838, -866.0795230979107, -441.8801487102304, -486.9240384397768, -448.92080971909934, -568.2781554760301, -621.5480781196876, -498.6813861971805, -866.9217547158365, -628.1070214390891, -402.0265213562144, -417.27506515180227], [811.0277765138225, 348.84375080377356, 212.24334098663113, 60.32380481778345, 876.1508210726536, 918.6279047391596, 121.0000619813125, 335.13926775461874, 176.19669744572863, 116.78257035705386, 899.9668762570302, 57.82038188621011, 980.5051778055378, 97.3544098366868, 863.6071785443921, 566.9396008821735, 368.5495703300555, 343.0000342485327, 757.606779094471, 315.25872170928295, 657.6615977005247, 517.808757432564, 485.48067951291245, 901.2610084785124, 555.0904135616394, 827.0347414456462, 725.8479605673879, 39.51868881293935, 773.3369424529138, 217.6533798409496, 903.24649720472, 43.881266418223184, 333.73896243984444, 100.63321428751925, 476.1135279677589, 820.202413433882, 298.88917230340104, 151.78396241373056, 330.9367686612023, 814.0662617787153, 141.24357384154752, 228.1350866284243, 69.78311252888057, 706.0043339456181, 395.8380102928005, 311.5291371661727, 718.9077639508108, 336.64156479791495, 728.0435019412037, 815.3841959189992, 218.4451806142807, 973.8448781491373, 163.1955899647541, 291.5500657500858, 180.6154955427081, 346.16015069997815, 480.5808269329349, 522.653693133117, 853.7524362539757, 889.5584609070506], [-220.88375692012548, -623.2711381535667, -112.38456124141688, -459.5108903218862, -323.0112045085715, -317.1842447081528, -483.1016574703889, -730.0978078937383, -70.1134761335971, -879.2941643497171, -735.0789608559305, -177.32288950017107, -939.221748178283, -506.8059117993652, -999.8087695388483, -198.0622148264369, -535.3732901848182, -290.9577945173685, -304.8693838318573, -591.4743154531562, -921.7973478039625, -805.4585917235959, -724.2174571028246, -559.6146083196005, -922.3762051637802, -492.86904528419325, -873.9583461563834, -834.1476622327551, -214.62151145478498, -771.4542375029444, -13.158985786315506, -323.50670801053946, -230.33787724725784, -507.35609552882613, -737.1163085191047, -98.5786910802764, -515.4072797348316, -938.4736096726913, -229.41790443196257, -677.4640029673127, -593.2873905103764, -11.053631960437237, -476.3503696613655, -709.0616205501076, -44.93145659206651, -879.6419615407063, -520.5613352190375, -31.630387277392202, -225.18919830891934, -953.7220207308857, -582.7374133190033, -108.36509520103573, -288.25695777828093, -457.2469222346237, -21.929119198462732, -412.20389810014507, -489.96917679926344, -244.43419740595095, -589.0503612916946, -753.4868794725846], [236.59838988152984, 620.8794003797077, 639.9826207207778, 948.5917608277122, 778.4978911291473, 848.496924520216, 490.9294885278389, 186.16323839240346, 995.8194776666753, 130.22640527766092, 471.9858620349111, 69.0250061428645, 943.9070064934687, 964.9600159075911, 719.6696729419696, 350.64285078653876, 255.12801871650672, 266.0380212125104, 128.16673139465468, 526.2831441236463, 142.67545842577604, 317.41393588690283, 627.0797694831458, 727.8160659811591, 25.248431917439152, 430.6858683923632, 652.4724702472969, 853.3927301823543, 475.8494574298703, 969.2366658459675, 266.3669149939058, 14.495197920092162, 484.2691118370344, 256.8576812249979, 823.8939543511462, 233.53989950893097, 311.318589073015, 791.4362035880932, 715.4281087733347, 558.4931854206053, 705.2431138608367, 419.21822670645645, 6.304737567053134, 12.343773383680366, 511.71056578611297, 84.20768873928024, 52.024404689087525, 965.5511224983359, 859.1436370184005, 152.87519998235996, 1.663554371614286, 941.7261275943666, 279.0469730217942, 186.711705252642, 691.8165997237037, 109.79483510248488, 265.3849484047975, 975.1195855318344, 639.8233116995362, 521.157113691071], [-398.5206962201028, -774.7264539293178, -141.81651904717003, -967.3704642349452, -861.2618850577209, -618.0393255866741, -43.863284212155605, -701.1547937982899, -913.3710565445954, -525.0524904111473, -354.8705970054355, -121.15706763449016, -755.1462030334308, -885.1368293605944, -101.15149233177273, -759.2255701975896, -18.04342577283841, -967.0878631591423, -615.4429626144611, -552.8866199326416, -296.6538837553389, -929.3623798982136, -266.63972170945425, -828.3184666034782, -985.1235706577949, -783.613248869291, -519.4709304660454, -67.00818958782025, -472.94137538190193, -438.81769102473186, -203.59324514580825, -424.1640490775901, -358.4001261962584, -164.5205768904968, -441.93276918915365, -263.5371563681646, -522.5403582615821, -36.124899656477986, -906.3251883674969, -816.5479412143362, -553.0287511779941, -851.9567741744859, -962.4326787369897, -111.4117717586079, -631.200976601394, -997.9960069347229, -987.9012801641926, -603.7196692984538, -128.89284958036586, -583.6096381595377, -3.062570938847292, -199.71242333219277, -956.1670364004, -331.110132030241, -638.7517156711716, -281.57863513761043, -947.8740652244779, -728.8301712195373, -330.3215064238312, -791.9696597591904], [109.05735895186132, 392.926621125394, 221.99690960386073, 684.0427208287703, 103.34383549015845, 397.6288064503914, 277.3730804789804, 506.83657640448035, 350.54778282337503, 706.704167089344, 25.552447282659102, 634.3529343846016, 231.3407184041262, 269.44031972809245, 800.45534797994, 955.6128255864404, 317.2336598170595, 826.9784650987066, 104.88684713326187, 634.3476713543758, 751.2812672353839, 156.8219501064221, 426.576385281891, 892.8144570847326, 104.4748849849238, 19.078261843273673, 590.9947936688858, 436.09600899040254, 798.8905596350188, 923.5320826659025, 299.85449089927226, 389.0157130519362, 486.7858142429855, 588.563308974864, 983.8699758519351, 697.6329205792215, 390.1589588382232, 264.50391876401164, 944.6810927037019, 136.4128846753979, 720.5455866522533, 925.4696302671482, 665.0009209479042, 423.631385725955, 199.79194898555852, 368.1078469296753, 707.1649376107019, 649.8846899511216, 928.0481904317595, 866.9940527457155, 816.334601514102, 911.5394244754116, 277.06081558431237, 370.1540165995099, 380.5140098822314, 560.8901381210704, 668.5500113132282, 287.4299663573539, 20.443004841991048, 399.8231612742514], [-309.21943159484607, -942.2425342990299, -888.3767755034995, -860.4503676650761, -653.3467611842977, -344.94487553423994, -549.3004181319054, -815.4098156756563, -99.51175835408823, -801.2738053750494, -42.13861153679354, -816.6046101831414, -807.7562403557137, -51.95630151992706, -627.5335507503964, -502.9506212385843, -170.64968366854296, -149.23055873969827, -773.4858669409562, -568.1250560880072, -983.016135781616, -982.2655295110558, -992.674326470802, -119.49690284740012, -938.3178808269982, -245.32503941154224, -458.7540474988534, -757.6491492659042, -204.41731114515474, -566.7452939487756, -186.6309314777697, -105.631370574612, -117.44205381716893, -358.2813958133706, -5.650182000346302, -425.42906728048786, -664.5329079760679, -402.28649681898474, -86.70880591931528, -63.626173161616904, -278.83839625209686, -170.14337785305716, -965.1298782447515, -152.0789947491109, -805.6569749675916, -586.5218337994037, -569.7176330643101, -512.5686352078608, -971.7913130378371, -364.48093031654616, -788.1278352029224, -555.7388133594926, -396.23803395810046, -955.5104673724751, -598.7176533953225, -119.79802520386755, -418.1216617958597, -781.800145953926, -694.0532762159746, -916.4239895067376], [260.1180067573787, 758.43552263747, 460.4153321871264, 574.0361372198486, 955.0916343252767, 979.3070336691882, 861.729372961638, 359.73799064256593, 887.8131348915925, 638.9705684637715, 430.5667836902424, 36.706939817983255, 770.3579960673906, 502.60347514338895, 786.4023109655957, 748.2747765439266, 793.7738006803036, 301.3505075380701, 800.9978004685634, 549.2974821377012, 473.85287424869404, 675.4507879069362, 22.337324255409957, 103.21449907170663, 292.8851878023545, 983.0071198478818, 140.60603308609004, 331.2657044584511, 52.00201162723169, 331.93761141243357, 321.0059602243208, 946.8603637735777, 845.3089329087246, 383.3814550235287, 25.744288981209422, 831.2000828813829, 660.8756409673956, 153.21211916765841, 996.075199739177, 101.13320398669893, 867.2474270520692, 294.97189796555926, 435.9181128588319, 795.6610702495383, 677.8308476380163, 937.9265100695951, 621.5191851349229, 98.71235131757369, 884.4760028787084, 769.3863694636025, 712.1585804424287, 54.67981380638163, 396.8265219170823, 168.2683836400797, 822.0820044994612, 700.8280941950449, 883.1945197218162, 966.6085318172397, 774.9728665783061, 994.2388501375414], [-615.1551162581545, -38.09247428755637, -15.237263635145583, -342.7617713285849, -823.6482473484696, -866.2685716184062, -960.8517162938552, -66.05634708026957, -45.52653987667642, -913.3703127706667, -305.7416516644987, -558.4294132090231, -982.4624381177092, -401.0480862011874, -666.20552691153, -401.4786840683533, -768.4264697983169, -528.187010847293, -238.28561484836337, -272.0347951572077, -258.8011533258688, -532.7880079303022, -703.4858269996487, -949.3306201430989, -694.3932877078969, -781.4116511184283, -169.75718974870105, -374.68856238231837, -414.3664396384078, -686.6938497704725, -296.5960844004967, -303.98862949824644, -356.53326548622726, -810.491779461689, -578.0124999533053, -76.20200255290173, -79.16785359077834, -371.9156573382168, -766.8244595555522, -688.9947430522019, -708.2743722965355, -767.4428559880428, -287.86556017344304, -548.7080256601458, -543.8092876764528, -739.8928686787693, -956.9136985365408, -278.71195485067045, -793.4883910842912, -660.3105779747392, -580.6576329925966, -775.1048995680545, -944.0884339616713, -37.654726451543574, -148.25270241070746, -756.5309442696147, -84.70756155717446, -516.607577040352, -220.64091586496536, -275.0214081389087], [702.1386424614718, 31.162580495442903, 873.4461084740018, 445.03447639691774, 502.890900613194, 540.5079157299982, 645.8987502849144, 345.51173003612536, 102.00638307292785, 319.0605577295104, 168.9739759047975, 556.5770462710234, 318.7106023294261, 958.1091108154415, 965.7685437023003, 620.5057546876732, 617.8797703996187, 985.3931860025389, 887.3958680839507, 765.3048792089818, 314.2770211309585, 366.1734890899583, 202.06549899510458, 487.66097879045725, 990.37815361744, 912.2388020585772, 119.2310845854496, 26.165099001215644, 898.739030739858, 537.6329578207587, 200.98969832024773, 673.9796163150507, 644.5789547518901, 122.96352122963071, 260.3406332641219, 61.0178863489447, 210.6506133962718, 133.1733691782098, 194.04305618208153, 685.7816787672039, 50.45024451680667, 102.75276063296826, 135.03946444020934, 317.2245798371759, 299.451560541089, 255.8087215313228, 750.7861167789838, 998.0247649703425, 534.443945705167, 944.2585151960282, 397.21350201393864, 107.57576435591072, 409.3650556403675, 296.8316456412786, 493.91355532688897, 657.3866332395068, 461.5891689332558, 935.2253515657477, 884.8800574770805, 702.275617571031], [-490.1952274521846, -132.55559453264243, -397.61665311085574, -704.6971378617725, -285.60063503317747, -104.88408946587701, -907.9905590531175, -709.341759005729, -615.6611502084621, -792.7064067033076, -835.8103915458922, -483.97553917285234, -881.3070631580306, -916.5025916904043, -272.2795443293566, -607.9378144310035, -527.0574447916487, -538.4078333727506, -937.7254308705975, -305.883513990336, -983.4505442563417, -902.2290835894279, -459.26416572488915, -817.635810354548, -769.2779473258204, -678.2170746489028, -320.51405549377114, -197.254540829133, -671.8561690689925, -843.1303231046832, -17.23653588869231, -643.1605719332035, -443.4301515975902, -898.1896673718566, -322.1514579233511, -474.7106274513581, -515.2523369311511, -141.29908184968193, -713.1794103962075, -830.6458687758386, -58.851367619363984, -292.09743171636586, -39.006636853522856, -956.5875605835541, -667.5016518831197, -964.2362190353267, -531.9627840529765, -802.2664553717183, -375.03956989586027, -354.46521354006825, -378.8895492880276, -658.2042715927017, -360.09369787063054, -900.4670841526214, -983.2915901851051, -31.396088821668904, -194.429667112094, -113.13774259479861, -43.321683044351815, -228.51325235393918], [447.34652704871206, 837.1533749233951, 222.6022064794861, 494.45131040653905, 929.6891207073077, 667.5474920798882, 798.2809407362415, 551.4429762153007, 980.4859923817894, 589.0734925267927, 46.46520324862895, 198.78481713985505, 405.3688553281908, 601.6758954012025, 772.1589365415509, 413.6730397779824, 710.348246710673, 790.0796336060158, 317.9429370527328, 979.2909697957828, 650.0068387405997, 881.117062725345, 556.3817511197981, 741.8615040451714, 770.773517554749, 908.3401308553445, 151.19940711449894, 558.7251407450792, 428.95013459275043, 923.2358621525665, 105.9895995547502, 982.5913147922319, 875.575872769203, 74.75245528268428, 491.475419154934, 717.8419407123134, 738.4133941453654, 906.5876311126829, 800.0655701467286, 311.6194499637454, 498.9363510765899, 702.0839771729181, 139.29840452298706, 194.79680680259713, 481.56140566176276, 298.9475529068072, 862.6966905343108, 586.6910441990973, 349.31653252064933, 848.9841925788057, 805.0735701056846, 998.3565222221703, 847.4603806454011, 415.042078270874, 128.37138288821848, 840.8002672922775, 60.698160042433585, 350.92093613750933, 919.8182427905025, 960.8057069716556], [-640.9240289276972, -688.9596686667298, -43.41203423679696, -514.9658607484583, -547.3213106275349, -340.76064537798703, -69.52823791913046, -229.67869212466962, -358.62595292433514, -435.7068445298133, -591.3357988080356, -722.6691271795381, -318.3142414006722, -329.6248061590641, -20.671951080980012, -41.83398523392429, -258.5638726142279, -740.5047526772817, -628.6855165435383, -770.0192316571569, -769.1505167786069, -856.710900201632, -720.5989467208967, -979.031908081822, -898.9263940825156, -587.130449057011, -588.5695128206805, -35.23277331187727, -998.528051130646, -132.44442136877564, -740.6068494349604, -821.1941799291845, -373.68147477589804, -197.65520261064844, -99.66112690376447, -748.8573998237482, -453.20087567649, -714.0040412421345, -915.4922412029488, -147.43715241490563, -919.2518297230758, -412.21483304892826, -305.9617428873918, -943.1191983421763, -990.661040913793, -199.6933255496807, -657.1815086050314, -107.3888184572893, -651.2630898536482, -827.4859145480739, -684.8140479775435, -417.91580892053315, -383.68329320420577, -393.72929280819363, -590.1221061749302, -881.6857028024231, -929.1370911114991, -54.47609058711079, -182.4407722510426, -113.11209151246022], [194.14130612614707, 347.26120279856264, 507.0251509400012, 629.8317657821431, 732.4100769205618, 890.2214298444212, 989.099348792561, 663.1936220785627, 845.5191541490952, 778.2608080777742, 308.2245071794933, 875.8165779646881, 43.720374809851045, 1.3669764077064026, 274.45889675907574, 462.63543209782245, 638.7245321056766, 102.66849627800025, 673.3371237010051, 802.0140511926348, 186.12760665978743, 415.71012957696206, 520.4650049633565, 452.3552110663962, 800.0301009575821, 960.5618757212114, 799.1542108441718, 78.91482505794875, 805.130636586968, 67.52973590331563, 236.7344148563284, 153.94379993888708, 198.32158773923933, 528.7868119302933, 672.0181677532428, 470.85096105370496, 959.7359433902144, 241.05202771013649, 763.3770900245381, 870.3119963286414, 562.5040446439644, 456.76627945959154, 596.5882623324644, 429.3809603901826, 555.638688441046, 417.51701817667276, 401.06924058383987, 695.6511216713903, 93.75836185489999, 167.375530656092, 851.347273243289, 771.3062694683729, 282.17227356709935, 377.89166373309445, 926.100480121852, 818.2591479486874, 614.7319536796513, 222.26868862415478, 45.20771934395432, 431.8265889950563], [-672.9545121182044, -828.6520100273337, -852.8363167365271, -33.74312539207002, -244.91287680304248, -339.7554938889256, -189.54347874842648, -803.1724029854739, -767.6982973218576, -517.3162073405898, -982.9435515178596, -144.91448254975143, -899.7520516243412, -117.34679090775424, -164.01852380860657, -696.5229810503681, -110.46012234964762, -566.2792503232921, -420.81330293618095, -728.7454915754738, -900.7745635700562, -770.1016431543862, -849.8401865447671, -33.91250308270115, -310.88530274595894, -515.9176535996461, -416.53736131514967, -232.02369802670876, -308.5662238620633, -945.4855394212141, -294.8866989914802, -354.55020606960596, -4.706063976268667, -845.2325496505966, -155.68586269817504, -204.94013123821233, -256.00925257493356, -884.7374347879978, -207.2449598350684, -797.728834507072, -808.2412909825816, -927.0935482176094, -116.44575228671366, -218.0616933654935, -743.1553937886406, -196.8047535264583, -287.0432173265756, -167.5748385312513, -173.52398946889426, -482.0718012735775, -110.57337905084557, -322.3759208451586, -427.16731568928014, -25.523568407453613, -388.9448333079781, -95.02831364943144, -494.0849526150305, -825.9124503685392, -818.6037400196054, -81.36806702186311], [601.6265299168457, 834.7517955892653, 238.7345703917007, 762.1645849381495, 890.8735821036432, 806.3180272890037, 108.19373048398901, 10.050939522862514, 192.53238581192377, 271.20686360567663, 616.5668076253436, 384.8889020670761, 703.703623630812, 353.721885561087, 155.2709992299457, 313.3771536425491, 884.4399021627459, 958.5738119008198, 208.30522133330112, 788.6799186374169, 274.07538780333084, 887.2444118879762, 166.3800671834592, 666.2939587753629, 85.12705344846934, 973.9194306498956, 700.9327112959023, 841.9739236656802, 567.1026700236715, 477.32456256493134, 622.2605090029707, 529.2127701877486, 469.9149707900078, 759.6908012061851, 179.02275398432886, 172.00087610700336, 432.4108079990565, 321.4271681289011, 75.05039339511107, 844.6260219263156, 771.8312038876554, 544.3775783031817, 979.3452127271046, 73.5274664810577, 766.9026317268472, 267.10402121748774, 369.23032102363186, 220.0601058178645, 789.2488535704033, 145.09586191954443, 840.1766810375427, 661.916070581604, 59.964222023845615, 811.1707498685532, 628.1279604468165, 905.0773372587631, 748.9735841022296, 561.559806502345, 836.7106334385785, 278.77218806292086], [-547.4031117827191, -294.32320298360673, -968.2361866994182, -226.97010454116437, -16.722501430792043, -326.52898716179243, -503.0068875728349, -29.334571295845002, -559.6890517338735, -874.408492176279, -705.0274622222535, -623.345354655326, -956.005788957543, -958.3210545082637, -824.4422032335253, -608.1341055384652, -488.276794938209, -14.302797133220842, -606.6556443203149, -989.0989872814969, -818.282948974005, -341.26403924046764, -152.8949780193776, -784.274555852687, -744.1938828111098, -967.0797451873437, -874.9675195773995, -556.106962647135, -102.1829627177774, -484.0171577255761, -314.3813589682947, -512.896073542815, -302.39987306501354, -861.9611689836202, -844.4826869688394, -316.14969200988884, -599.981765027621, -430.75067678141505, -909.1836642715347, -188.17354052489645, -698.0306733831743, -970.4049525093793, -176.10024404352708, -202.764461995779, -694.0296153335556, -779.3747706003891, -491.0585057391388, -610.0767786819742, -213.46972640301692, -477.13761433875874, -112.95980899404024, -322.10050335038903, -285.49492532592336, -445.1807347423176, -930.1962358814533, -182.08639448569457, -401.9868583780958, -615.981621890535, -946.6105289879276, -134.01504334423242], [917.9587403761204, 81.97273484542748, 481.2606557631042, 455.13527736325227, 210.39312614831834, 348.11220844773163, 454.7111030800497, 865.3462514477186, 955.1090812281863, 519.406752958528, 870.2296905041275, 608.5634140911027, 349.7382546456878, 195.00001340585558, 413.721637010982, 523.3014586409239, 45.39894487129663, 146.69532470497987, 600.5842395574585, 225.7765930824849, 837.4890497052162, 327.61530752441644, 105.72937304599763, 84.44705796676172, 937.1858975112478, 118.90229093063729, 141.76885439789797, 862.8033918748202, 255.03384214706665, 666.2854593436617, 816.9089613428614, 607.573459490062, 957.5310549044016, 709.1740163615805, 113.63875839375469, 558.851616519334, 718.4683395630947, 802.1552831330717, 27.295013948807437, 719.160036356153, 825.85514019843, 747.0869771244212, 512.8367965099425, 458.56294212571413, 549.869164716516, 704.9390551277754, 922.991376341853, 617.4181754304839, 887.9464719771861, 701.5555905982816, 69.26804106140872, 501.3273618116202, 287.1998619669271, 285.8897532044397, 356.5716236647682, 315.4180392284753, 579.0313701369831, 683.9178988532035, 269.48063768965875, 130.63285994581295], [-59.74991221352764, -576.1770921855217, -186.94403616666938, -10.238746229475675, -927.8253262443804, -537.6032786641574, -93.35573206672579, -843.0781910153578, -983.2195355518279, -449.15206135569946, -43.44711862992001, -118.42839481530744, -382.27209289878675, -885.6371148114282, -148.89064059848428, -824.1661039086928, -15.961283958800413, -457.9313100870252, -644.7527438096175, -61.3191025435708, -615.1479878658702, -944.4597173480865, -161.09966021645846, -729.8817716523174, -609.4848040455998, -185.93127249035132, -7.197211294656663, -10.27516605542115, -532.5603167628566, -942.8366301516323, -644.6543288381467, -714.5855464474499, -494.37162143361655, -582.3070536919353, -127.24115780527286, -876.9437997802302, -761.0318360381351, -998.200753891765, -298.4252246080657, -227.79075402426182, -126.03649630338158, -964.2455468594287, -781.1042994433956, -167.15828910591907, -553.1337846371057, -414.3544398592095, -152.33452179838662, -162.91091204493551, -963.5065247504405, -305.6592187747645, -941.4978523922593, -76.53506239201931, -461.34223925089736, -130.48942946824334, -5.782597855930998, -554.2123076323704, -114.78021070655205, -722.302506402746, -698.4182593311926, -177.15657455702467], [941.8004011222512, 721.3223650240571, 298.67229389277304, 709.5245301868398, 732.1983474038544, 342.8841049197096, 376.21297389899775, 359.7474011456468, 617.001825108522, 900.5097363936392, 174.02004299235904, 875.3244102264821, 28.62550334883716, 660.6782573822442, 415.0244343165045, 791.4902706802612, 721.4769148179721, 480.6276993380388, 644.2201726858741, 502.27135756924525, 811.7069521512614, 476.60790198226374, 523.6328340020838, 251.27006583076138, 605.4379737936619, 303.6019038611652, 577.706730528439, 170.5084374584958, 160.30962324881764, 417.61271145080156, 427.39269559543027, 268.8411556476265, 132.46525351632332, 40.17132867468316, 26.206595460528327, 272.2787397164692, 462.3915887197752, 726.5170380248209, 475.39682901329496, 904.1467686158464, 36.18458477083167, 181.4799609190937, 339.1759782773725, 577.9186918770573, 852.8834217360485, 350.8517500046199, 268.7206938219157, 62.82727967405285, 821.482174220406, 380.2867767634723, 571.9786452215174, 983.5718627530491, 2.592976033690282, 146.3046905581671, 779.3318830253361, 805.32235772263, 769.4778719137227, 537.4618921517864, 978.878124042033, 396.78837543532524], [-602.3417544149992, -64.30563554429946, -410.4475924574314, -722.7775874224121, -239.5001019299286, -943.8837614840753, -687.0965842756458, -288.2878074747139, -769.2299237831505, -84.081607036301, -974.7996480879461, -50.23597381448496, -933.5224352575696, -253.60102387051293, -758.0662835831996, -1.073625733672983, -254.98584909042012, -749.3515060430701, -532.8037348264249, -115.83719748747775, -394.236116091438, -376.173805729458, -568.5940819367689, -668.3090953877576, -840.9894121698378, -497.73416558039526, -392.62969558786494, -144.8325575612863, -805.0181420247326, -713.6570350091454, -409.26872005723067, -518.9138776327268, -665.5176615674769, -165.64078425769026, -28.17059661351233, -318.1861954874987, -595.9894346165269, -487.1194851901773, -692.862072236264, -819.8701157689607, -488.95402426354565, -135.132756694107, -850.7773717991669, -575.4153369468403, -740.1975433020879, -704.9599889546832, -968.2435595599104, -296.0120150134781, -705.6014660064827, -366.3106567927924, -396.01531019772307, -231.36404202206276, -344.66616547520306, -948.3484549066048, -293.27827610065333, -246.74461535063014, -583.5548404953481, -258.77792078501284, -473.91233986870077, -834.3420802996807], [231.16991399286837, 427.2647207717361, 610.8792452850118, 546.083295648912, 974.748514177822, 680.6898841407999, 740.2062958063914, 966.9889920187665, 415.0235872032925, 356.02443524599016, 44.81856733661617, 185.0201022123083, 237.9524424196242, 184.32096260426715, 755.0291093033679, 536.3470982948355, 667.9661676570088, 820.6416986785342, 231.54316734460878, 326.59801588167767, 708.6519067695602, 393.36618695856833, 30.241669160943097, 435.52026380785105, 908.3648133289988, 409.6124900812818, 332.91666752630425, 989.5355578620821, 644.7711486727761, 366.63202844470965, 102.91751183244357, 788.0615955014747, 708.3668585542699, 921.9938834493164, 218.0583543979803, 115.80942563824375, 724.3484538826546, 204.19244615669695, 176.9277339517066, 320.487528060676, 817.0083163369592, 539.9970685045212, 46.80450474717869, 464.4307799846579, 684.2956317551087, 538.8300700305467, 572.8777679383994, 225.55255106427197, 847.8915922637527, 561.837318873533, 713.5327670276359, 981.8823527962892, 428.7704590168576, 881.185546063832, 8.27373292718389, 34.373885322504975, 590.6896418070882, 312.1379461466584, 249.02829045268055, 278.65742185174963], [-319.08453167597696, -729.2187484472795, -569.6267762587136, -789.2469365867742, -830.3663832552169, -843.0919244419808, -415.2295050257127, -421.8521229200944, -926.3396142604433, -662.1018310098061, -81.38671679515963, -542.6447671383759, -356.65125237527207, -987.4475547266468, -14.641751055830282, -612.5686921974875, -723.8994713044592, -289.61786458599784, -973.6678767382756, -859.6770903946896, -915.7371881448266, -20.21282729219693, -570.3022791634942, -295.3555917125922, -849.1796063007273, -633.2168072580474, -539.3381273167886, -115.4735815059301, -540.6825819814046, -632.2722422100702, -955.9563970008943, -585.4659594134457, -967.4332011439088, -961.6445094910555, -650.5501354977639, -506.4020761339706, -466.55572208222327, -890.4881825546669, -29.228426288785005, -114.69438982554799, -102.96965739003271, -757.1783897959338, -340.31137282868224, -638.3305761959602, -604.179120938723, -386.4421417727891, -532.0361545201562, -645.4933950380884, -941.0093795482602, -576.0584387881205, -614.753144256546, -68.7879618860717, -952.2635989453519, -528.5538459814768, -801.4721464400619, -51.240772084241684, -421.48922560135395, -257.7184836935489, -267.70892278990135, -791.6622762309685], [624.2428585435847, 440.3055665310052, 11.575153846807023, 964.9630150025844, 962.0612301023681, 218.33465806975843, 42.305025944240136, 530.6691636488903, 951.4594038017912, 910.48544991917, 585.0782010255072, 304.24530180305345, 330.6309228854268, 898.0156379345416, 492.2922515999414, 131.98511273817843, 249.1770504976337, 277.5181065660316, 124.42313824697743, 463.5813371397701, 916.134857366716, 669.1137604492686, 73.40145032460727, 6.489322991353559, 276.9714198017851, 363.33024185914644, 776.972919377729, 967.0385184064363, 388.1796062501201, 687.0033397870443, 994.9070054456103, 745.9209172911394, 636.5533595367586, 78.99677932412598, 323.8919859935355, 913.4787662986997, 201.8044761992248, 843.746768913935, 696.6273613954249, 366.9580464599239, 529.6450954429439, 543.2636622840607, 714.3397312888123, 517.0393851580969, 133.9429141939821, 773.6812168503907, 406.86622440921263, 963.1307963217154, 284.2302685107413, 263.815701516288, 334.1738882795074, 572.7446989426669, 894.9748704607813, 177.10535849987477, 280.399118801621, 582.0981633047139, 454.87990791935357, 447.8755643684696, 820.9135278343101, 923.9544242088498], [-481.825659103812, -687.6644436518264, -801.2576523163665, -518.8480439767767, -295.02209254478163, -638.4465131245615, -585.5239912057532, -901.6612569198708, -53.35462973308618, -910.2212557463333, -534.8975961371942, -16.660439933864012, -345.3574765890203, -724.6092303114444, -488.94465484789714, -980.1788784035514, -423.1874637572175, -327.30859439638175, -821.8502624951385, -548.3587926586733, -682.6442524834963, -805.8966357006389, -671.7561185794947, -422.9850872738959, -125.67165144640637, -580.6679184047292, -897.5358934025303, -419.47353409189657, -910.8145096079977, -504.0242919626196, -621.220720880034, -833.1554875795872, -565.0325125310808, -91.87836995626793, -980.9984213995947, -246.6034526109209, -710.7948233015684, -505.608325179121, -479.2938641808904, -244.69687804802456, -722.428614934404, -113.67547656615626, -990.4628560521237, -845.5281635700967, -534.9744310657862, -425.12840310195145, -287.1781678274078, -502.0898794698267, -879.5380445621439, -275.7313942999829, -501.0369213443328, -235.31535216496383, -337.8119645512865, -191.07024841440912, -990.5486547272667, -571.9259490159932, -733.0823089126587, -99.15166353858467, -366.75143252424147, -892.7471632442741], [85.35388809752394, 166.31774511127355, 625.7921927408174, 623.1662051101209, 838.3888174094757, 935.55727110755, 142.8444889498385, 260.1144447084725, 428.0339442875626, 1.9023822357283808, 70.74448865673523, 227.26478666308063, 481.62086205179594, 252.27121543044422, 876.805210330825, 324.9486026664691, 924.698189330486, 974.8124734739753, 450.4116723736712, 227.9016880824243, 292.3744672895803, 776.5573479777867, 274.07635808479847, 381.20228505236435, 479.09728262336796, 575.5360053535142, 996.1043398609369, 232.97754540842874, 354.0702795449207, 263.6282858335005, 361.7523232070666, 101.70371237772594, 360.44995747380614, 887.977166432924, 299.2912579986026, 372.5628450692198, 944.5296902734967, 728.6506173305413, 517.2219761032303, 777.4155356750371, 124.05646920564944, 465.02586286762147, 119.11789260713044, 234.38452687456044, 142.72539248051834, 362.43943792997015, 382.25768107552994, 947.3612732514076, 264.8616054563417, 472.9564164712003, 811.5680245595232, 815.8019688502251, 750.5928438479853, 288.54592837793285, 495.47664779194565, 187.02538359153652, 189.21112326002145, 436.40537192517263, 738.8536290216981, 527.05767573784]]}'
d = json.loads(s)
c = np.array(d["c"])
A_ub = np.array(d["A_ub"])
b_ub = np.array(d["b_ub"])
res = linprog(c, A_ub, b_ub)
print res.message
#res2 = linprog_ip(c, A_ub, b_ub)
#print json.dumps(res2.x.tolist())
x = np.array(json.loads('[2.399258925624789e-09, 7.222080720748526e-11, 4.078182502684987, 6.693386380621786e-11, 3.597054848576818e-10, 1.1139512318772213e-10, 4.2784022954643514e-10, 7.50613690567392e-11, 5.311660191687251e-10, 1.1881966487725603e-10, 1.1243114486071154e-09, 1.0237882004201583e-10, 1.7672268090054188, 7.422405473463711e-11, 8.005011351338168e-10, 9.571907093744658e-11, 2.071384120066141, 8.189148742249369e-11, 8.083223899047802e-10, 7.232718955423651e-11, 2.332778329154235, 8.035196438064155e-11, 2.5742618872656764, 8.332892847019005e-11, 0.2274212721192163, 5.914638541061239e-11, 1.529509648902658, 7.121431910427833e-11, 6.029479702610815e-10, 6.023227841519799e-11, 7.932993233026978e-09, 8.926181275186726e-11, 1.5907197262683208, 8.065655531617564e-11, 4.193606019871893e-09, 8.685201979750348e-11, 2.4952168209064513e-09, 9.622600833024025e-11, 5.864373235407751e-09, 6.750289017153847e-11, 2.286103129228396e-07, 8.238628910151717e-11, 2.3063520858354982, 9.93913785773475e-11, 2.4268329069241805e-09, 8.761665740974184e-11, 2.1272739799356106, 9.924696156144069e-11, 6.677224338899702e-10, 7.353800149506495e-11, 9.141893128272225e-10, 5.080243688592909e-11, 6.202892960714917e-09, 9.746115457987274e-11, 6.141396618203684e-10, 5.899987292928757e-11, 5.637862718528342e-10, 8.067872452415561e-11, 2.8886572316129376e-10, 7.764310085470918e-11]'))
print np.all(x >= 0)
print np.all(A_ub.dot(x) <= b_ub)

Output:

Optimization failed. Unable to find a feasible starting point.
True
True

indicating that while linprog fails, the provided x (which I believe is actually the optimal solution) is non-negative and satisfies the upper bound constraints.

@mdhaber
Copy link
Contributor

mdhaber commented Feb 22, 2017

And linprog doesn't fare very well with the Ziontz2 problems from that same reference, "Performance evaluation of a family of criss-cross algorithms for linear programming" unless the problems are small (< 100 constraints / variables).

@mdhaber mdhaber mentioned this issue Jul 18, 2017
Closed
@jacksonloper
Copy link

FWIW, method=interior-point seems to fair better in many cases.

@mdhaber
Copy link
Contributor

mdhaber commented Apr 9, 2018

@jacksonloper Thanks : ) I wrote the interior point method to address these issues.

@GuillaumeLeclerc
Copy link

GuillaumeLeclerc commented May 12, 2018 •
edited
Loading

Stumbled on the same problem with this when unit-testing a specialized solver:

obj = [1, 0]
U_A = array([[ 1.5018e+04,  1.0000e+00],
       [-1.5028e+04, -1.0000e+00],
       [ 1.5029e+04,  1.0000e+00],
       [-1.5041e+04, -1.0000e+00],
       [ 1.5042e+04,  1.0000e+00],
       [-1.5058e+04, -1.0000e+00],
       [ 1.5060e+04,  1.0000e+00],
       [-1.5070e+04, -1.0000e+00],
       [ 1.5072e+04,  1.0000e+00],
       [-1.5080e+04, -1.0000e+00],
       [ 1.5081e+04,  1.0000e+00],
       [-1.5107e+04, -1.0000e+00]])
U_b = array([  0.,  -1.,   2.,  -3.,   4.,  -5.,   6.,  -7.,   8.,  -9.,  10., -11.])

The problem is now I have no reference to test my solver because it seems that scipy is not really reliable. Is interior-point always correct ?

EDIT: after updating scipy to the newest version it seems that interior-point is always correct but has a much worse numerical precision :/

@mdhaber
Copy link
Contributor

mdhaber commented May 13, 2018

@GuillaumeLeclerc You can use the tol option to improve the accuracy. If you can't get what you need that way, please let me know.

@mdhaber mdhaber mentioned this issue Jun 6, 2018
Merged
@Kai-Striega
Copy link
Member

I've found the "bug". At the end of phase one the pseudo-objective function evaluates to 1.7e-12. As 1.7e-12 > 1e-12 simplex fails to find a feasible solution. Increasing the tol value to 1e-11 fixes this.

@mdhaber
Copy link
Contributor

mdhaber commented Jun 21, 2018

On my machine it's 5.065432517881163e-10 for the first problem posted by @cy18 , but same idea.
For the problem I posted in February 2017, -1.310556140948139e-12. Also same idea.
Re: @GuillaumeLeclerc , if obj is c, U_A is A_ub, and U_b is b_ub, then I think the problem is infeasible. Please post complete code if that is not correct.

This is not a "bug", as we cannot expect the default tolerance to work for all possible problems.
And the documentation does state that tol is "The tolerance which determines when a solution is “close enough” to zero in Phase 1 to be considered a basic feasible solution...".
Nonetheless, this seems like a common enough issue - and tricky enough to those unfamiliar with the simplex method that it took us two years to get to the bottom of it - that something needs to change.

I'd suggest that the error message Optimization failed. Unable to find a feasible starting point. be made much more descriptive, like:
Phase I of the simplex method was unable to find a feasible starting point given the desired tolerance tol = 1-e12. Consider setting the feasibility tolerance option to 6e-10; if this tolerance is unacceptable, then the problem may be infeasible.
(Of course the first number should be whatever the current tolerance is, and the second number should be the objective function value rounded up.)

It would be nice to educate the user a little more about interpreting the results of the Phase I problem, but I can't find anything in the SciPy documentation already written about the two-phase approach, and I think that adding something is beyond the scope of resolving this issue.

@Kai-Striega let me know if you're willing to make this fix; if not I can pull out the old mac and do it. Thanks for finding this!

@Kai-Striega
Copy link
Member

@mdhaber I've submitted a PR #8958. Let me know if you think that is OK.

@mdhaber mdhaber mentioned this issue Jun 25, 2018
Merged
@mdhaber
Copy link
Contributor

mdhaber commented Jun 28, 2018

Closed via #8958

@mdhaber mdhaber closed this as completed Jun 28, 2018
@rgommers rgommers added this to the 1.2.0 milestone Jun 28, 2018
@Kai-Striega Kai-Striega mentioned this issue Jul 26, 2018
Closed
@jiangzhongshi
Copy link

jiangzhongshi commented Sep 2, 2018 •
edited
Loading

I stumbled upon a similar issue today, with a three variable system. Scaling don't seem to work here and the solution of phase 1 far exceeds the tolerance.

The values are printed as follows

A_ub: [[ 1.         -0.19507086 -4.20204673]
 [ 1.          0.4680441   1.46199951]
 [ 1.         -0.27297324  2.74004722]]
b_ub: [ 2.23954238  0.25140597 -0.80939868]
x: [ 0.          2.57538006 -0.65252106]

For exact reproducing the problem, I am using pickle bytestream.

import pickle
import scipy.optimize
import numpy as np
A_ub = pickle.loads(b'\x80\x03cnumpy.core.multiarray\n_reconstruct\nq\x00cnumpy\nndarray\nq\x01K\x00\x85q\x02C\x01bq\x03\x87q\x04Rq\x05(K\x01K\x03K\x03\x86q\x06cnumpy\ndtype\nq\x07X\x02\x00\x00\x00f8q\x08K\x00K\x01\x87q\tRq\n(K\x03X\x01\x00\x00\x00<q\x0bNNNJ\xff\xff\xff\xffJ\xff\xff\xff\xffK\x00tq\x0cb\x89CH\x00\x00\x00\x00\x00\x00\xf0?X1\xe5\xf2\x14\xf8\xc8\xbfKMtV\xe5\xce\x10\xc0\x00\x00\x00\x00\x00\x00\xf0?b\x0e\xd5:o\xf4\xdd?2|\xf9\x99Yd\xf7?\x00\x00\x00\x00\x00\x00\xf0?\xb6ub\xc1dx\xd1\xbf~\xdc\xeb\xdf\x9d\xeb\x05@q\rtq\x0eb.')
b_ub = pickle.loads(b'\x80\x03cnumpy.core.multiarray\n_reconstruct\nq\x00cnumpy\nndarray\nq\x01K\x00\x85q\x02C\x01bq\x03\x87q\x04Rq\x05(K\x01K\x03\x85q\x06cnumpy\ndtype\nq\x07X\x02\x00\x00\x00f8q\x08K\x00K\x01\x87q\tRq\n(K\x03X\x01\x00\x00\x00<q\x0bNNNJ\xff\xff\xff\xffJ\xff\xff\xff\xffK\x00tq\x0cb\x89C\x18\xe4\x1c\xb21\x95\xea\x01@D\x81\xdd\x10\t\x17\xd0?\x12}\xd0\r\x98\xe6\xe9\xbfq\rtq\x0eb.')
x = pickle.loads(b'\x80\x03cnumpy.core.multiarray\n_reconstruct\nq\x00cnumpy\nndarray\nq\x01K\x00\x85q\x02C\x01bq\x03\x87q\x04Rq\x05(K\x01K\x03\x85q\x06cnumpy\ndtype\nq\x07X\x02\x00\x00\x00f8q\x08K\x00K\x01\x87q\tRq\n(K\x03X\x01\x00\x00\x00<q\x0bNNNJ\xff\xff\xff\xffJ\xff\xff\xff\xffK\x00tq\x0cb\x89C\x18\x00\x00\x00\x00\x00\x00\x00\x006\x95\xfe\xdc`\x9a\x04@\x0e\xa0\xf8\xd6s\xe1\xe4\xbfq\rtq\x0eb.')
print('A_ub', A_ub)
print('b_ub', b_ub)
print('x', x)
assert np.all(A_ub @ x <= b_ub)
res= scipy.optimize.linprog([-1,0,0], A_ub=A_ub, b_ub = b_ub)
print(res)

Update This is mostly my fault, as I ignored that I have to set bound as (None,None) for the problem. It is mentioned in the notes of the documentation, but might be worth to explicitly state that the default is x >=0 in the main entry.

@mdhaber
Copy link
Contributor

mdhaber commented Sep 2, 2018 •
edited
Loading

@jiangzhongshi I think these will be fixed in the next release.
@Kai-Striega Can you add this as a test in #9145? Update: never mind.

@mdhaber
Copy link
Contributor

mdhaber commented Sep 3, 2018

@jiangzhongshi the default bounds are in the bounds section of the documentation. Where would you like to see it?

(BTW these default bounds are common among linear programming codes because of the way the algorithms work. It's fine to make variables unbounded if you need to, but under the hood this is typically accomplished by adding additional non-negative variables.)

@jiangzhongshi
Copy link

jiangzhongshi commented Sep 3, 2018 •
edited
Loading

@mdhaber Thanks for the prompt help and information. I was suggesting the information on the top section:

Minimize:     c^T * x

Subject to:   A_ub * x <= b_ub
              A_eq * x == b_eq
              x >= 0

@Kai-Striega
Copy link
Member

Kai-Striega commented Sep 12, 2018 •
edited
Loading

Sorry I completely missed this with everything else happening!

I'm not sure if x >= 0 is the appropriate as the passed bounds may lead to negative x variables being feasible. @jiangzhongshi, do you think having a message in the Notes section would be useful? An example message:

Standard form linear programs constrain all x variables to be non-negative. Therefore the default bounds also constrains all x to be non-negative. It's fine to change variable bounds or make variables unbounded, they are handled internally.

@mdhaber

@mdhaber
Copy link
Contributor

mdhaber commented Sep 12, 2018

@Kai-Striega is right that x >= 0 is not correct because that is not the form of the general problem linprog solves, which is what the documentation is stating here.

I think the way to fix this is by making it:

Minimize:     c^T * x

Subject to:   A_ub * x <= b_ub
              A_eq * x == b_eq
              lb <= x <= ub

And immediately stating that the default bounds lb = 0 and ub = np.inf can be changed as described below.

We should also consider using @ instead of * here. I think @ilayn suggested that?

@ilayn
Copy link
Member

ilayn commented Sep 12, 2018

Yes we can (and I think "should") use Python3 constructs in the documentation. In this particular case it is just matlab notation.

@mdhaber mdhaber mentioned this issue Sep 14, 2018
Closed
22 tasks
@Kai-Striega Kai-Striega mentioned this issue Sep 15, 2018
Merged
@mdhaber mdhaber mentioned this issue Jan 8, 2020
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
defect A clear bug or issue that prevents SciPy from being installed or used as expected scipy.optimize
Projects
None yet
Milestone
1.2.0
Development

Successfully merging a pull request may close this issue.

DOC: Add description of default bounds to linprog Kai-Striega/scipy