next up previous Next: Bibliography Up: benches Previous: Other problems: inequalities, parametric

  • La page de J-P. Merlet
  • J-P. Merlet home page
  • La page Présentation de HEPHAISTOS
  • HEPHAISTOS home page
  • La page "Présentation" de l'INRIA
  • INRIA home page

    Subsections


    Difficult problems

    The purpose of this section is to present problems for which interval analysis has failed or has experienced difficulties (large computation time for the total system or for a number of equations equal or greater than 10).

    A problem denoted with a "*" indicates that the problem in its initial formulation was difficult to solve but that a new formulation of the problem allows to solve it easily.

    Algebraic: Brent

    Origin: [8]
    n equations

    \begin{eqnarray*} &&i =1 ~~~3x_i(x_{i+1}-2x_i)+x^2_{i+1}/4\\ &&i =n ~~~3x_i(20-... ...\\ &&1<i<n~~~3x_i(x_{i+1}-2x_i+x_{i-1})+(x_{i+1}-x_{i-1})2/4\\ \end{eqnarray*}

    Ranges: [-1e8,1e8] for all unknowns

    Solving method: HessianSolve+HullConsistency+ 3B (April 2003)
    Solving method: HessianSolve+HullConsistency+ 3B+GlobalConsistencyTaylor (May 2007)
    Solutions:: 16 (n=5), exact, 32 (n=6), exact, 64, 63 certified (n=7), exact, 132, 124 certified (n=8)
    Computation time:

    Evo 410C, April 2003, (1.2Ghz) 2.55s (n=5), 8.01s (n=6), 58.15s (n=7), 1902.6s (n=8)
    Dell 620, May 2007, (1.7Ghz) 1.8s (n=5), 4.98s (n=6), 20.95s (n=7), 180s (n=8)

    Algebraic: Butcher8

    Origin: COCONUT
    8 equations defined by: 

     
b1 + b2 + b3 - (a+b)=0
b2*c2 + b3*c3 - (1/2 + 1/2*b + b^2 - a*b)=0
b2*c2^2 + b3*c3^2 - (a*(1/3+b^2) - 4/3*b - b^2 - b^3)=0
b3*a32*c2 - (a*(1/6 + 1/2*b + b^2) - 2/3*b - b^2 - b^3)=0
b2*c2*83 + b3*c3^3 - (1/4 + 1/4*b + 5/2*b^2 + 3/2*b^3 + b^4 - a*(b+b^3))=0
b3*c3*a32*c2 - (1/8 + 3/8*b + 7/4*b^2 + 3/2*b^3 + b^4 - a*(1/2*b + 1/2*b^2 + b^3))=0
b3*a32*c2^2 - (1/12 + 1/12*b + 7/6*b^2 + 3/2*b^3 + b^4- a*(2/3*b + b^2 + b^3))=0
1/24 + 7/24*b + 13/12*b^2 + 3/2*b^3 + b^4 - a*(1/3*b + b^2 + b^3)=0
    Ranges: for all unknowns [-50,50]

    If a = -1, b =-1,b1 =-2, b2=b3=0, then all equations are verified whatever are c2,c3,a32. Hence we check all solutions for a in [-50,-1.1] and [-0.9,50].

    Solving method: HessianSolve+HullConsistency+ 3B +GlobalConsistencyTaylor+ special 2B and IntervalNewton
    Solutions:: 3 for a in [-50,-1.1], 3 for a in [-0.9,50] (exact)
    Computation time (May 2007):

    Dell 620 (1.7Ghz) 58mn (a in [-50,-1.1]), 10 hours (a in [-0.9,50])

    Algebraic: Chebyquad

    Origin: [9]
    n equations defined by

    \begin{displaymath} \frac{1}{n}\sum_{j=1}^{j=n} T_i(x_j)+a_i \end{displaymath}

    where $T_i$ is the ith Chebyshev polynomial shifted to [0,1] and ai =0 if i is odd and $a_i = -1/(i^2-1)$ if i is even

    Ranges: for all unknowns [-100,100]

    Solving method: HessianSolve+HullConsistency+SimplexConsistency+ 3B (April 2003)
    Solving method: HessianSolve+HullConsistency+SimplexConsistency+ 3B +GlobalConsistencyTaylor+ IntervalNewton (May 2007)
    Solutions:: 24 for n=4 (exact), 0 for n=5,6
    Computation time :

    Evo 410C, (April 2003) (1.2Ghz) 9.47s (n=4), 279s (n=5), 11286s (n=6)
    Cluster, (April 2003) (11 PC's) 84s (n=5), 1523s (n=6)
    Dell 620 (May 2007) (1.7GHz) 2.31s (n=4), 155s (n=5), 11250s (n=6)

    Algebraic: Countercurrent reactors 2

    Origin: [8]
    n equations, a = 0.414214

    \begin{eqnarray*} &&i =1 ~~~x_1-(1-x_1) x_{i+2}-a (1+4 x_{i+1})\\ &&i =2 ~~~-(1... ...\\ &&i>3, i<n-1~~~x_1 x_{i-2}+(1-x_1) x_{i+2}-x_i (1+4 x_{i-1}) \end{eqnarray*}

    Ranges: [-1e8,1e8] for all unknowns

    Solving method: HessianSolve+HullConsistency+ 3B + GlobalConsistencyTaylor (May 2007)
    Solutions:: 2 (n=6), 7 (n=7,8), 15 (n=9), 24 (n=10) (exact)
    Computation time

    Evo 410C (April 2003) (1.2Ghz) 28.31s (n=6)
    DELL 620 (May 2007) (1.7Ghz) 2.07s (n=6), 1mn35s (n=7), 2mn47s (n=8), 11mn12s (n=9), 47mn16s (n=10)

    Algebraic: Dipole (*)

    Origin: COCONUT
    8 equations defined by: 

     
a+b=0.63254
 c+d =-1.34534
 t*a+u*b-v*c-w*d=-0.8365348
 v*a+w*b+t*c+u*d=1.7345334
 a*t**2-a*v**2-2*c*t*v+b*u**2-b*w**2-2*d*u*w=1.352352
 c*t**2-c*v**2+2*a*t*v+d*u**2-d*w**2+2*b*u*w=-0.843453
a*t**3-3*a*t*v**2+c*v**3-3*c*v*t**2+b*u**3-3*b*u*w**2+d*w**3-3*d*w*u**2= 
-0.9563453
c*t**3-3*c*t*v**2-a*v**3+3*a*v*t**2+ d*u**3-3*d*u*w**2-b*w**3+3*b*w*u**2=1.2342523
    Ranges: for all unknowns [-1e8,1e8]
    Solving method: HessianSolve+HullConsistency+ 3B + GlobalConsistencyTaylor +Simp2B
    Solutions:: 2 (exact)
    Computation time
    Cluster, (May 2007) (11 PC's) 3 days
    See section Dipole2 for another formulation of the problem that leads to a relatively easy solving.

    Algebraic: Dualc1

    Origin: COCONUT, A dual quadratic program from Antonio Frangioni (frangio@DI.UniPi.IT)
    Optimization problem with 215 constraints and 9 variables
    Minimize: 
     
14882.0*0.5*x1*x1+4496.0*x1*x2+5258.0*x1*x3+5204.0*x1*x4+
        8407.0*x1*x5+8092.0*x1*x6-42247.0*x1*x7-116455.0*x1*x8+
        51785.0*x1*x9+65963.0*0.5*x2*x2-17504.0*x2*x3-17864.0*x2*x4-
        15854.0*x2*x5-14818.0*x2*x6-100219.0*x2*x7-101506.0*x2*x8+
        25690.0*x2*x9+17582.0*0.5*x3*x3+17642.0*x3*x4+15837.0*x3*x5+
        17186.0*x3*x6+27045.0*x3*x7-53251.0*x3*x8+26765.0*x3*x9+
        17738.0*0.5*x4*x4+15435.0*x4*x5+16898.0*x4*x6+26625.0*x4*x7-
        56011.0*x4*x8+27419.0*x4*x9+35281.0*0.5*x5*x5+48397.0*x5*x6+
        48427.0*x5*x7+29317.0*x5*x8+12170.0*x5*x9+93500.0*0.5*x6*x6+
        5386.0*x6*x7-92344.0*x6*x8+112416.0*x6*x9+1027780.0*0.5*x7*x7+
        1744550.0*x7*x8-963140.0*x7*x9+5200790.0*0.5*x8*x8-2306625.0*x8*
        x9+1390020.0*0.5*x9*x9+5765.7624165*x2+3753.0154856*x3+
        3753.4216509*x4+11880.124847*x5+29548.987048*x6+423163.83666*x7+
        3369558.8652*x8+439695.6796*x9;
    submitted to the constraints: 
     
c1:=
        x1+x2+x3+x4+x5+x6+x7+x8+x9 = 1;
c2:=
        0 <= 680.0*x1+729.0*x2+680.0*x3+680.0*x4+729.0*x5+782.0*x6+648.0*x7 
       +317.0*x8+798.0*x9;
c3:=
        0 <= 304.0*x1+306.0*x2+304.0*x3+304.0*x4+293.0*x5+354.0*x6+204.0*x7 
       +72.0*x8+656.0*x9;
c4:=
        0 <= 50.0*x1+38.0*x2+50.0*x3+50.0*x4+43.0*x5+53.0*x6-83.0*x7-
        208.0*x8+402.0*x9;
c5:=
        0 <= 643.0*x1+688.0*x2+643.0*x3+643.0*x4+641.0*x5+659.0*x6+581.0*x7 
       +606.0*x8+748.0*x9;
c6:=
        0 <= 811.0*x1+845.0*x2+845.0*x3+845.0*x4+858.0*x5+860.0*x6+748.0*x7 
       +538.0*x8+870.0*x9;
c7:=
        0 <= 1325.0*x1+1329.0*x2+1329.0*x3+1329.0*x4+1329.0*x5+1329.0*x6+
        1305.0*x7+1316.0*x8+1323.0*x9;
c8:=
        0 <= 1108.0*x1+1127.0*x2+1130.0*x3+1129.0*x4+1142.0*x5+1141.0*x6+
        1147.0*x7+1143.0*x8+1115.0*x9;
c9:=
        0 <= 2026.0*x1+2026.0*x2+2026.0*x3+2026.0*x4+2026.0*x5+2027.0*x6+
        2027.0*x7+2059.0*x8+1969.0*x9;
c10:=
        0 <= 1481.0*x1+1481.0*x2+1481.0*x3+1481.0*x4+1453.0*x5+1474.0*x6+
        1440.0*x7+1375.0*x8+1469.0*x9;
c11:=
        0 <= 1570.0*x1+1555.0*x2+1553.0*x3+1570.0*x4+1570.0*x5+1526.0*x6+
        1497.0*x7+1516.0*x8+1692.0*x9;
c12:=
        0 <= 1442.0*x1+1442.0*x2+1442.0*x3+1442.0*x4+1442.0*x5+1442.0*x6+
        1413.0*x7+1398.0*x8+1439.0*x9;
c13:=
        0 <= 1694.0*x1+1694.0*x2+1669.0*x3+1669.0*x4+1648.0*x5+1645.0*x6+
        1652.0*x7+1738.0*x8+1748.0*x9;
c14:=
        0 <= 1610.0*x1+1633.0*x2+1600.0*x3+1600.0*x4+1619.0*x5+1612.0*x6+
        1612.0*x7+1636.0*x8+1612.0*x9;
c15:=
        0 <= 627.0*x1+627.0*x2+664.0*x3+664.0*x4+654.0*x5+654.0*x6+606.0*x7 
       +552.0*x8+761.0*x9;
c16:=
        0 <= 581.0*x1+596.0*x2+592.0*x3+579.0*x4+566.0*x5+556.0*x6+541.0*x7 
       +465.0*x8+618.0*x9;
c17:=
        0 <= 728.0*x1+726.0*x2+728.0*x3+728.0*x4+728.0*x5+726.0*x6+724.0*x7 
       +749.0*x8+717.0*x9;
c18:=
        0 <= 1469.0*x1+1450.0*x2+1454.0*x3+1467.0*x4+1491.0*x5+1491.0*x6+
        1470.0*x7+1545.0*x8+1466.0*x9;
c19:=
        0 <= 5.0*x1+5.0*x2+5.0*x3+5.0*x4+5.0*x5-10.0*x6-4.0*x7-57.0*x8+
        59.0*x9;
c20:=
        0 <= 466.0*x1+424.0*x2+401.0*x3+401.0*x4+401.0*x5+401.0*x6+397.0*x7 
       +359.0*x8+390.0*x9;
c21:=
        0 <= 1160.0*x1+1175.0*x2+1156.0*x3+1156.0*x4+1156.0*x5+1156.0*x6+
        1117.0*x7+1043.0*x8+1126.0*x9;
c22:=
        0 <= 485.0*x1+485.0*x2+484.0*x3+496.0*x4+474.0*x5+471.0*x6+479.0*x7 
       +479.0*x8+506.0*x9;
c23:=
        0 <= 783.0*x1+783.0*x2+783.0*x3+783.0*x4+783.0*x5+788.0*x6+647.0*x7 
       +475.0*x8+909.0*x9;
c24:=
        0 <= 1706.0*x1+1706.0*x2+1709.0*x3+1703.0*x4+1696.0*x5+1679.0*x6+
        1584.0*x7+1477.0*x8+1602.0*x9;
c25:=
        0 <= 278.0*x1+276.0*x2+273.0*x3+273.0*x4+273.0*x5+303.0*x6+242.0*x7 
       +113.0*x8+493.0*x9;
c26:=
        0 <= 500.0*x1+508.0*x2+505.0*x3+505.0*x4+505.0*x5+512.0*x6+494.0*x7 
       +457.0*x8+504.0*x9;
c27:=
        0 <= 520.0*x1+520.0*x2+509.0*x3+509.0*x4+509.0*x5+559.0*x6+234.0*x7 
       +163.0*x8+752.0*x9;
c28:=
        0 <= 1569.0*x1+1577.0*x2+1570.0*x3+1557.0*x4+1543.0*x5+1536.0*x6+
        1567.0*x7+1492.0*x8+1674.0*x9;
c29:=
        0 <= 40.0*x1+25.0*x2+25.0*x3+25.0*x4+25.0*x5+39.0*x6+4.0*x7+
        52.0*x8+36.0*x9;
c30:=
        0 <= 1627.0*x1+1627.0*x2+1627.0*x3+1627.0*x4+1627.0*x5+1625.0*x6+
        1628.0*x7+1667.0*x8+1548.0*x9;
c31:=
        0 <= 613.0*x1+613.0*x2+613.0*x3+613.0*x4+621.0*x5+621.0*x6+596.0*x7 
       +586.0*x8+628.0*x9;
c32:=
        0 <= 1617.0*x1+1617.0*x2+1634.0*x3+1617.0*x4+1615.0*x5+1627.0*x6+
        1636.0*x7+1667.0*x8+1570.0*x9;
c33:=
        0 <= 1000.0*x1+998.0*x2+1000.0*x3+1000.0*x4+1000.0*x5+1001.0*x6+
        1042.0*x7+987.0*x8+952.0*x9;
c34:=
        0 <= 1716.0*x1+1715.0*x2+1716.0*x3+1713.0*x4+1705.0*x5+1717.0*x6+
        1727.0*x7+1816.0*x8+1757.0*x9;
c35:=
        0 <= 1590.0*x1+1590.0*x2+1590.0*x3+1590.0*x4+1593.0*x5+1576.0*x6+
        1566.0*x7+1458.0*x8+1567.0*x9;
c36:=
        0 <= 187.0*x1+202.0*x2+202.0*x3+202.0*x4+210.0*x5+210.0*x6+210.0*x7 
       +230.0*x8+200.0*x9;
c37:=
        0 <= 504.0*x1+496.0*x2+505.0*x3+505.0*x4+507.0*x5+507.0*x6+497.0*x7 
       +392.0*x8+512.0*x9;
c38:=
        0 <= 364.0*x1+364.0*x2+341.0*x3+358.0*x4+358.0*x5+341.0*x6+333.0*x7 
       +334.0*x8+404.0*x9;
c39:=
        0 <= 1186.0*x1+1145.0*x2+1183.0*x3+1183.0*x4+1181.0*x5+1214.0*x6+
        1254.0*x7+1230.0*x8+1193.0*x9;
c40:=
        0 <= 1361.0*x1+1344.0*x2+1352.0*x3+1352.0*x4+1352.0*x5+1348.0*x6+
        1326.0*x7+1392.0*x8+1367.0*x9;
c41:=
        0 <= 601.0*x1+622.0*x2+611.0*x3+611.0*x4+621.0*x5+631.0*x6+636.0*x7 
       +540.0*x8+628.0*x9;
c42:=
        0 <= 1048.0*x1+1054.0*x2+1053.0*x3+1053.0*x4+1036.0*x5+1027.0*x6+
        1029.0*x7+1048.0*x8+1022.0*x9;
c43:=
        0 <= 1268.0*x1+1262.0*x2+1266.0*x3+1266.0*x4+1266.0*x5+1266.0*x6+
        1265.0*x7+1205.0*x8+1326.0*x9;
c44:=
        0 <= 570.0*x1+570.0*x2+552.0*x3+552.0*x4+533.0*x5+561.0*x6+561.0*x7 
       +622.0*x8+571.0*x9;
c45:=
        0 <= 1833.0*x1+1833.0*x2+1830.0*x3+1830.0*x4+1820.0*x5+1820.0*x6+
        1835.0*x7+1799.0*x8+1826.0*x9;
c46:=
        0 <= 1068.0*x1+1052.0*x2+1074.0*x3+1074.0*x4+1088.0*x5+1088.0*x6+
        1063.0*x7+954.0*x8+1096.0*x9;
c47:=
        0 <= 1508.0*x1+1508.0*x2+1545.0*x3+1545.0*x4+1545.0*x5+1539.0*x6+
        1581.0*x7+1547.0*x8+1517.0*x9;
c48:=
        0 <= 1074.0*x1+1059.0*x2+1061.0*x3+1061.0*x4+1059.0*x5+1059.0*x6+
        1030.0*x7+935.0*x8+1131.0*x9;
c49:=
        0 <= 1345.0*x1+1347.0*x2+1345.0*x3+1345.0*x4+1345.0*x5+1345.0*x6+
        1290.0*x7+1284.0*x8+1432.0*x9;
c50:=
        0 <= 889.0*x1+900.0*x2+881.0*x3+881.0*x4+886.0*x5+863.0*x6+835.0*x7 
       +931.0*x8+877.0*x9;
c51:=
        0 <= 104.0*x1+104.0*x2+104.0*x3+104.0*x4+104.0*x5+108.0*x6+120.0*x7 
       +120.0*x8+116.0*x9;
c52:=
        0 <= 1309.0*x1+1309.0*x2+1309.0*x3+1309.0*x4+1309.0*x5+1309.0*x6+
        1266.0*x7+1192.0*x8+1307.0*x9;
c53:=
        0 <= 197.0*x1+234.0*x2+234.0*x3+235.0*x4+235.0*x5+227.0*x6+226.0*x7 
       +312.0*x8+167.0*x9;
c54:=
        0 <= 1565.0*x1+1565.0*x2+1565.0*x3+1565.0*x4+1565.0*x5+1565.0*x6+
        1566.0*x7+1616.0*x8+1560.0*x9;
c55:=
        0 <= 299.0*x1+299.0*x2+299.0*x3+310.0*x4+311.0*x5+325.0*x6+246.0*x7 
       +211.0*x8+398.0*x9;
c56:=
        0 <= 575.0*x1+575.0*x2+575.0*x3+564.0*x4+563.0*x5+567.0*x6+529.0*x7 
       +553.0*x8+576.0*x9;
c57:=
        0 <= 709.0*x1+709.0*x2+710.0*x3+709.0*x4+709.0*x5+709.0*x6+703.0*x7 
       +704.0*x8+736.0*x9;
c58:=
        0 <= 1372.0*x1+1372.0*x2+1372.0*x3+1372.0*x4+1372.0*x5+1372.0*x6+
        1372.0*x7+1382.0*x8+1333.0*x9;
c59:=
        0 <= 1843.0*x1+1843.0*x2+1842.0*x3+1842.0*x4+1842.0*x5+1842.0*x6+
        1841.0*x7+1831.0*x8+1828.0*x9;
c60:=
        0 <= 1004.0*x1+1004.0*x2+1004.0*x3+1004.0*x4+1006.0*x5+1006.0*x6+
        1013.0*x7+916.0*x8+959.0*x9;
c61:=
        0 <= 704.0*x1+717.0*x2+717.0*x3+717.0*x4+717.0*x5+713.0*x6+725.0*x7 
       +772.0*x8+718.0*x9;
c62:=
        0 <= 1178.0*x1+1128.0*x2+1128.0*x3+1128.0*x4+1126.0*x5+1132.0*x6+
        1187.0*x7+1123.0*x8+1135.0*x9;
c63:=
        0 <= 925.0*x1+925.0*x2+925.0*x3+925.0*x4+933.0*x5+937.0*x6+943.0*x7 
       +916.0*x8+937.0*x9;
c64:=
        0 <= 1582.0*x1+1544.0*x2+1582.0*x3+1582.0*x4+1590.0*x5+1637.0*x6+
        1543.0*x7+1454.0*x8+1651.0*x9;
c65:=
        0 <= 64.0*x1+64.0*x2+64.0*x3+64.0*x4+56.0*x5-105.0*x6-89.0*x7-
        227.0*x8+14.0*x9;
c66:=
        0 <= 161.0*x1+111.0*x2+161.0*x3+161.0*x4-37.0*x5-24.0*x6-44.0*x7-
        301.0*x8+377.0*x9;
c67:=
        0 <= 1346.0*x1+1346.0*x2+1346.0*x3+1346.0*x4+1357.0*x5+1357.0*x6+
        1265.0*x7+1248.0*x8+1449.0*x9;
c68:=
        0 <= 1058.0*x1+1070.0*x2+1075.0*x3+1075.0*x4+1105.0*x5+1118.0*x6+
        1040.0*x7+1031.0*x8+1076.0*x9;
c69:=
        0 <= 1259.0*x1+1192.0*x2+1240.0*x3+1240.0*x4+1251.0*x5+1270.0*x6+
        1390.0*x7+1178.0*x8+1405.0*x9;
c70:=
        0 <= 350.0*x1+338.0*x2+376.0*x3+376.0*x4+376.0*x5+389.0*x6+397.0*x7 
       +176.0*x8+493.0*x9;
c71:=
        0 <= 593.0*x1+585.0*x2+588.0*x3+588.0*x4+600.0*x5+612.0*x6+626.0*x7 
       +600.0*x8+563.0*x9;
c72:=
        0 <= 844.0*x1+830.0*x2+844.0*x3+844.0*x4+828.0*x5+828.0*x6+849.0*x7 
       +811.0*x8+805.0*x9;
c73:=
        0 <= 1619.0*x1+1619.0*x2+1619.0*x3+1619.0*x4+1619.0*x5+1619.0*x6+
        1619.0*x7+1619.0*x8+1613.0*x9;
c74:=
        0 <= 232.0*x1+234.0*x2+271.0*x3+271.0*x4+260.0*x5+250.0*x6+250.0*x7 
       +271.0*x8+255.0*x9;
c75:=
        0 <= 1427.0*x1+1397.0*x2+1447.0*x3+1447.0*x4+1418.0*x5+1422.0*x6+
        1435.0*x7+1361.0*x8+1414.0*x9;
c76:=
        0 <= 492.0*x1+523.0*x2+473.0*x3+473.0*x4+495.0*x5+487.0*x6+491.0*x7 
       +505.0*x8+485.0*x9;
c77:=
        0 <= 820.0*x1+815.0*x2+815.0*x3+815.0*x4+815.0*x5+813.0*x6+797.0*x7 
       +902.0*x8+759.0*x9;
c78:=
        0 <= 1135.0*x1+1135.0*x2+1140.0*x3+1140.0*x4+1120.0*x5+1109.0*x6+
        1081.0*x7+1097.0*x8+1133.0*x9;
c79:=
        0 <= 1922.0*x1+1920.0*x2+1920.0*x3+1920.0*x4+1912.0*x5+1912.0*x6+
        1954.0*x7+1968.0*x8+1924.0*x9;
c80:=
        0 <= 1218.0*x1+1245.0*x2+1218.0*x3+1218.0*x4+1218.0*x5+1216.0*x6+
        1250.0*x7+1320.0*x8+1151.0*x9;
c81:=
        0 <= 1220.0*x1+1220.0*x2+1220.0*x3+1220.0*x4+1220.0*x5+1183.0*x6+
        1252.0*x7+1227.0*x8+1164.0*x9;
c82:=
        0 <= 2004.0*x1+1977.0*x2+2004.0*x3+2004.0*x4+2004.0*x5+2006.0*x6+
        1977.0*x7+1981.0*x8+2014.0*x9;
c83:=
        0 <= 762.0*x1+768.0*x2+757.0*x3+757.0*x4+757.0*x5+757.0*x6+776.0*x7 
       +744.0*x8+779.0*x9;
c84:=
        0 <= 680.0*x1+680.0*x2+680.0*x3+691.0*x4+687.0*x5+700.0*x6+700.0*x7 
       +709.0*x8+715.0*x9;
c85:=
        0 <= 445.0*x1+439.0*x2+440.0*x3+440.0*x4+462.0*x5+483.0*x6+527.0*x7 
       +593.0*x8+429.0*x9;
c86:=
        0 <= 558.0*x1+558.0*x2+558.0*x3+558.0*x4+469.0*x5+476.0*x6+629.0*x7 
       +613.0*x8+651.0*x9;
c87:=
        0 <= 1557.0*x1+1557.0*x2+1557.0*x3+1557.0*x4+1557.0*x5+1552.0*x6+
        1574.0*x7+1607.0*x8+1454.0*x9;
c88:=
        0 <= 305.0*x1+305.0*x2+305.0*x3+305.0*x4+305.0*x5+305.0*x6+305.0*x7 
       +322.0*x8+286.0*x9;
c89:=
        0 <= 1635.0*x1+1633.0*x2+1635.0*x3+1635.0*x4+1633.0*x5+1633.0*x6+
        1598.0*x7+1682.0*x8+1617.0*x9;
c90:=
        0 <= 1682.0*x1+1682.0*x2+1681.0*x3+1681.0*x4+1679.0*x5+1665.0*x6+
        1619.0*x7+1663.0*x8+1713.0*x9;
c91:=
        0 <= 605.0*x1+598.0*x2+604.0*x3+598.0*x4+604.0*x5+605.0*x6+585.0*x7 
       +490.0*x8+637.0*x9;
c92:=
        0 <= 1667.0*x1+1624.0*x2+1656.0*x3+1656.0*x4+1672.0*x5+1672.0*x6+
        1691.0*x7+1494.0*x8+1614.0*x9;
c93:=
        0 <= 1616.0*x1+1629.0*x2+1616.0*x3+1616.0*x4+1616.0*x5+1641.0*x6+
        1671.0*x7+1674.0*x8+1642.0*x9;
c94:=
        0 <= 1051.0*x1+1050.0*x2+1050.0*x3+1050.0*x4+1055.0*x5+1047.0*x6+
        1050.0*x7+1072.0*x8+1110.0*x9;
c95:=
        0 <= 1434.0*x1+1434.0*x2+1434.0*x3+1434.0*x4+1427.0*x5+1411.0*x6+
        1395.0*x7+1438.0*x8+1424.0*x9;
c96:=
        0 <= 1108.0*x1+1108.0*x2+1108.0*x3+1108.0*x4+1108.0*x5+1108.0*x6+
        1178.0*x7+1154.0*x8+1225.0*x9;
c97:=
        0 <= 554.0*x1+584.0*x2+540.0*x3+540.0*x4+540.0*x5+540.0*x6+567.0*x7 
       +575.0*x8+573.0*x9;
c98:=
        0 <= 1869.0*x1+1869.0*x2+1863.0*x3+1869.0*x4+1851.0*x5+1857.0*x6+
        1920.0*x7+1895.0*x8+1892.0*x9;
c99:=
        0 <= 368.0*x1+368.0*x2+373.0*x3+373.0*x4+373.0*x5+373.0*x6+382.0*x7 
       +382.0*x8+333.0*x9;
c100:=
        0 <= 1028.0*x1+1030.0*x2+1023.0*x3+1023.0*x4+1023.0*x5+1023.0*x6+
        964.0*x7+918.0*x8+1019.0*x9;
c101:=
        0 <= 801.0*x1+816.0*x2+819.0*x3+819.0*x4+816.0*x5+811.0*x6+803.0*x7 
       +668.0*x8+889.0*x9;
c102:=
        0 <= 349.0*x1+364.0*x2+364.0*x3+364.0*x4+392.0*x5+369.0*x6+371.0*x7 
       +280.0*x8+379.0*x9;
c103:=
        0 <= 1199.0*x1+1195.0*x2+1203.0*x3+1203.0*x4+1203.0*x5+1198.0*x6+
        1195.0*x7+1190.0*x8+1194.0*x9;
c104:=
        0 <= 776.0*x1+761.0*x2+772.0*x3+772.0*x4+786.0*x5+812.0*x6+810.0*x7 
       +766.0*x8+812.0*x9;
c105:=
        0 <= 37.0*x1+37.0*x2+37.0*x3+37.0*x4+37.0*x5+37.0*x6+30.0*x7+
        19.0*x8+46.0*x9;
c106:=
        0 <= 1265.0*x1+1265.0*x2+1266.0*x3+1239.0*x4+1328.0*x5+1354.0*x6+
        1209.0*x7+1100.0*x8+1329.0*x9;
c107:=
        0 <= 1131.0*x1+1086.0*x2+1090.0*x3+1090.0*x4+1068.0*x5+1073.0*x6+
        1037.0*x7+920.0*x8+1109.0*x9;
c108:=
        0 <= 930.0*x1+930.0*x2+930.0*x3+918.0*x4+967.0*x5+977.0*x6+956.0*x7 
       +926.0*x8+939.0*x9;
c109:=
        0 <= 390.0*x1+390.0*x2+390.0*x3+402.0*x4+342.0*x5+321.0*x6+386.0*x7 
       +359.0*x8+383.0*x9;
c110:=
        0 <= 1860.0*x1+1860.0*x2+1860.0*x3+1860.0*x4+1848.0*x5+1846.0*x6+
        1790.0*x7+1727.0*x8+1815.0*x9;
c111:=
        0 <= 309.0*x1+338.0*x2+332.0*x3+332.0*x4+239.0*x5+221.0*x6+301.0*x7 
       +140.0*x8+283.0*x9;
c112:=
        0 <= 950.0*x1+950.0*x2+950.0*x3+950.0*x4+950.0*x5+949.0*x6+996.0*x7 
       +1036.0*x8+969.0*x9;
c113:=
        0 <= 1734.0*x1+1734.0*x2+1734.0*x3+1734.0*x4+1734.0*x5+1734.0*x6+
        1733.0*x7+1667.0*x8+1703.0*x9;
c114:=
        0 <= 1449.0*x1+1449.0*x2+1449.0*x3+1449.0*x4+1449.0*x5+1445.0*x6+
        1457.0*x7+1435.0*x8+1534.0*x9;
c115:=
        0 <= 886.0*x1+878.0*x2+882.0*x3+869.0*x4+854.0*x5+873.0*x6+895.0*x7 
       +868.0*x8+837.0*x9;
c116:=
        0 <= 1497.0*x1+1497.0*x2+1523.0*x3+1523.0*x4+1532.0*x5+1531.0*x6+
        1566.0*x7+1578.0*x8+1479.0*x9;
c117:=
        0 <= 1157.0*x1+1200.0*x2+1150.0*x3+1150.0*x4+1163.0*x5+1195.0*x6+
        1158.0*x7+1223.0*x8+1356.0*x9;
c118:=
        0 <= 1006.0*x1+1039.0*x2+1010.0*x3+1010.0*x4+1012.0*x5+1002.0*x6+
        983.0*x7+755.0*x8+976.0*x9;
c119:=
        0 <= 1406.0*x1+1365.0*x2+1380.0*x3+1380.0*x4+1387.0*x5+1393.0*x6+
        1340.0*x7+1264.0*x8+1467.0*x9;
c120:=
        0 <= 1454.0*x1+1454.0*x2+1454.0*x3+1454.0*x4+1454.0*x5+1462.0*x6+
        1452.0*x7+1422.0*x8+1393.0*x9;
c121:=
        0 <= 778.0*x1+786.0*x2+778.0*x3+778.0*x4+754.0*x5+747.0*x6+727.0*x7 
       +774.0*x8+824.0*x9;
c122:=
        0 <= 798.0*x1+798.0*x2+798.0*x3+798.0*x4+793.0*x5+799.0*x6+797.0*x7 
       +797.0*x8+865.0*x9;
c123:=
        0 <= 1216.0*x1+1216.0*x2+1213.0*x3+1213.0*x4+1213.0*x5+1252.0*x6+
        1180.0*x7+1083.0*x8+1263.0*x9;
c124:=
        0 <= 661.0*x1+662.0*x2+680.0*x3+680.0*x4+661.0*x5+672.0*x6+708.0*x7 
       +650.0*x8+608.0*x9;
c125:=
        0 <= 985.0*x1+985.0*x2+1022.0*x3+1022.0*x4+1009.0*x5+1009.0*x6+
        984.0*x7+1082.0*x8+1091.0*x9;
c126:=
        0 <= 450.0*x1+450.0*x2+429.0*x3+429.0*x4+462.0*x5+448.0*x6+456.0*x7 
       +470.0*x8+468.0*x9;
c127:=
        0 <= 1140.0*x1+1140.0*x2+1102.0*x3+1102.0*x4+1102.0*x5+1098.0*x6+
        1078.0*x7+916.0*x8+1128.0*x9;
c128:=
        0 <= 1729.0*x1+1717.0*x2+1722.0*x3+1734.0*x4+1734.0*x5+1730.0*x6+
        1717.0*x7+1694.0*x8+1663.0*x9;
c129:=
        0 <= 1233.0*x1+1233.0*x2+1238.0*x3+1235.0*x4+1244.0*x5+1244.0*x6+
        1203.0*x7+1242.0*x8+1209.0*x9;
c130:=
        0 <= 1710.0*x1+1710.0*x2+1706.0*x3+1706.0*x4+1706.0*x5+1706.0*x6+
        1706.0*x7+1683.0*x8+1755.0*x9;
c131:=
        0 <= 744.0*x1+768.0*x2+781.0*x3+781.0*x4+781.0*x5+784.0*x6+755.0*x7 
       +679.0*x8+769.0*x9;
c132:=
        0 <= 1594.0*x1+1594.0*x2+1591.0*x3+1594.0*x4+1594.0*x5+1603.0*x6+
        1590.0*x7+1595.0*x8+1618.0*x9;
c133:=
        0 <= 111.0*x1+113.0*x2+113.0*x3+113.0*x4+113.0*x5+113.0*x6+144.0*x7 
       +219.0*x8+78.0*x9;
c134:=
        0 <= 1447.0*x1+1447.0*x2+1439.0*x3+1439.0*x4+1439.0*x5+1441.0*x6+
        1473.0*x7+1504.0*x8+1475.0*x9;
c135:=
        0 <= 1180.0*x1+1200.0*x2+1184.0*x3+1184.0*x4+1190.0*x5+1207.0*x6+
        1243.0*x7+1189.0*x8+1191.0*x9;
c136:=
        0 <= 767.0*x1+762.0*x2+765.0*x3+765.0*x4+768.0*x5+760.0*x6+753.0*x7 
       +644.0*x8+675.0*x9;
c137:=
        0 <= 1582.0*x1+1582.0*x2+1563.0*x3+1563.0*x4+1582.0*x5+1543.0*x6+
        1578.0*x7+1615.0*x8+1572.0*x9;
c138:=
        0 <= 833.0*x1+832.0*x2+832.0*x3+832.0*x4+832.0*x5+843.0*x6+881.0*x7 
       +906.0*x8+919.0*x9;
c139:=
        0 <= 1738.0*x1+1718.0*x2+1739.0*x3+1739.0*x4+1749.0*x5+1750.0*x6+
        1686.0*x7+1711.0*x8+1753.0*x9;
c140:=
        0 <= 1810.0*x1+1817.0*x2+1817.0*x3+1817.0*x4+1817.0*x5+1807.0*x6+
        1818.0*x7+1831.0*x8+1759.0*x9;
c141:=
        0 <= 747.0*x1+747.0*x2+747.0*x3+747.0*x4+759.0*x5+736.0*x6+726.0*x7 
       +670.0*x8+747.0*x9;
c142:=
        0 <= 836.0*x1+799.0*x2+799.0*x3+799.0*x4+799.0*x5+805.0*x6+797.0*x7 
       +738.0*x8+814.0*x9;
c143:=
        0 <= 1622.0*x1+1622.0*x2+1628.0*x3+1622.0*x4+1622.0*x5+1595.0*x6+
        1629.0*x7+1646.0*x8+1644.0*x9;
c144:=
        0 <= 1084.0*x1+1083.0*x2+1078.0*x3+1084.0*x4+1060.0*x5+1040.0*x6+
        1065.0*x7+1073.0*x8+1040.0*x9;
c145:=
        0 <= 72.0*x1+64.0*x2+61.0*x3+61.0*x4+74.0*x5+55.0*x6-41.0*x7-
        96.0*x8+51.0*x9;
c146:=
        0 <= 122.0*x1+122.0*x2+122.0*x3+122.0*x4+120.0*x5+127.0*x6+91.0*x7 
       +107.0*x8+262.0*x9;
c147:=
        0 <= 486.0*x1+486.0*x2+486.0*x3+486.0*x4+451.0*x5+459.0*x6+455.0*x7 
       -17.0*x8+655.0*x9;
c148:=
        0 <= 183.0*x1+194.0*x2+194.0*x3+194.0*x4+181.0*x5+146.0*x6+121.0*x7 
       -562.0*x8+488.0*x9;
c149:=
        0 <= 1401.0*x1+1360.0*x2+1421.0*x3+1421.0*x4+1445.0*x5+1468.0*x6+
        1383.0*x7+1076.0*x8+1432.0*x9;
c150:=
        0 <= 1276.0*x1+1276.0*x2+1277.0*x3+1277.0*x4+1280.0*x5+1307.0*x6+
        1268.0*x7+1228.0*x8+1439.0*x9;
c151:=
        0 <= 151.0*x1+131.0*x2+131.0*x3+131.0*x4+131.0*x5+131.0*x6+176.0*x7 
       +56.0*x8+200.0*x9;
c152:=
        0 <= 678.0*x1+612.0*x2+708.0*x3+708.0*x4+691.0*x5+715.0*x6+764.0*x7 
       +583.0*x8+774.0*x9;
c153:=
        0 <= 134.0*x1+134.0*x2+179.0*x3+179.0*x4+179.0*x5+155.0*x6+145.0*x7 
       +121.0*x8+136.0*x9;
c154:=
        0 <= 1354.0*x1+1347.0*x2+1347.0*x3+1344.0*x4+1345.0*x5+1345.0*x6+
        1396.0*x7+1388.0*x8+1292.0*x9;
c155:=
        0 <= 686.0*x1+727.0*x2+689.0*x3+692.0*x4+678.0*x5+678.0*x6+619.0*x7 
       +616.0*x8+898.0*x9;
c156:=
        0 <= 434.0*x1+434.0*x2+434.0*x3+434.0*x4+438.0*x5+433.0*x6+404.0*x7 
       +294.0*x8+484.0*x9;
c157:=
        0 <= 1538.0*x1+1538.0*x2+1555.0*x3+1538.0*x4+1538.0*x5+1555.0*x6+
        1590.0*x7+1483.0*x8+1523.0*x9;
c158:=
        0 <= 492.0*x1+492.0*x2+490.0*x3+490.0*x4+502.0*x5+502.0*x6+506.0*x7 
       +422.0*x8+553.0*x9;
c159:=
        0 <= 317.0*x1+317.0*x2+298.0*x3+298.0*x4+305.0*x5+267.0*x6+282.0*x7 
       +306.0*x8+300.0*x9;
c160:=
        0 <= 1564.0*x1+1564.0*x2+1549.0*x3+1549.0*x4+1477.0*x5+1459.0*x6+
        1602.0*x7+1594.0*x8+1522.0*x9;
c161:=
        0 <= 468.0*x1+483.0*x2+468.0*x3+468.0*x4+457.0*x5+446.0*x6+476.0*x7 
       +427.0*x8+455.0*x9;
c162:=
        0 <= 1674.0*x1+1665.0*x2+1632.0*x3+1632.0*x4+1617.0*x5+1617.0*x6+
        1532.0*x7+1512.0*x8+1674.0*x9;
c163:=
        0 <= 1270.0*x1+1312.0*x2+1298.0*x3+1298.0*x4+1298.0*x5+1308.0*x6+
        1317.0*x7+1301.0*x8+1265.0*x9;
c164:=
        0 <= 1710.0*x1+1710.0*x2+1710.0*x3+1710.0*x4+1708.0*x5+1697.0*x6+
        1685.0*x7+1568.0*x8+1699.0*x9;
c165:=
        0 <= 1133.0*x1+1133.0*x2+1116.0*x3+1133.0*x4+1133.0*x5+1110.0*x6+
        1034.0*x7+1113.0*x8+1146.0*x9;
c166:=
        0 <= 1500.0*x1+1500.0*x2+1500.0*x3+1500.0*x4+1496.0*x5+1482.0*x6+
        1491.0*x7+1462.0*x8+1486.0*x9;
c167:=
        0 <= 1828.0*x1+1828.0*x2+1828.0*x3+1828.0*x4+1828.0*x5+1840.0*x6+
        1775.0*x7+1785.0*x8+1821.0*x9;
c168:=
        0 <= 1715.0*x1+1715.0*x2+1712.0*x3+1712.0*x4+1723.0*x5+1708.0*x6+
        1777.0*x7+1716.0*x8+1712.0*x9;
c169:=
        0 <= 1018.0*x1+1018.0*x2+1019.0*x3+1019.0*x4+1033.0*x5+1031.0*x6+
        983.0*x7+987.0*x8+1050.0*x9;
c170:=
        0 <= 1091.0*x1+1091.0*x2+1080.0*x3+1080.0*x4+1067.0*x5+1069.0*x6+
        1098.0*x7+1021.0*x8+1088.0*x9;
c171:=
        0 <= 1062.0*x1+1077.0*x2+1079.0*x3+1062.0*x4+1048.0*x5+1067.0*x6+
        1014.0*x7+909.0*x8+1153.0*x9;
c172:=
        0 <= 74.0*x1+23.0*x2+71.0*x3+71.0*x4+20.0*x5-14.0*x6-5.0*x7-
        122.0*x8+17.0*x9;
c173:=
        0 <= 574.0*x1+570.0*x2+576.0*x3+582.0*x4+582.0*x5+601.0*x6+571.0*x7 
       +566.0*x8+672.0*x9;
c174:=
        0 <= 1266.0*x1+1266.0*x2+1249.0*x3+1266.0*x4+1266.0*x5+1250.0*x6+
        1264.0*x7+1144.0*x8+1268.0*x9;
c175:=
        0 <= 1525.0*x1+1517.0*x2+1553.0*x3+1553.0*x4+1553.0*x5+1551.0*x6+
        1599.0*x7+1628.0*x8+1486.0*x9;
c176:=
        0 <= 1545.0*x1+1545.0*x2+1519.0*x3+1519.0*x4+1519.0*x5+1519.0*x6+
        1508.0*x7+1480.0*x8+1486.0*x9;
c177:=
        0 <= 853.0*x1+853.0*x2+853.0*x3+853.0*x4+856.0*x5+856.0*x6+841.0*x7 
       +841.0*x8+843.0*x9;
c178:=
        0 <= 1477.0*x1+1477.0*x2+1481.0*x3+1494.0*x4+1509.0*x5+1521.0*x6+
        1528.0*x7+1529.0*x8+1456.0*x9;
c179:=
        0 <= 37.0*x1+43.0*x2+39.0*x3+39.0*x4+39.0*x5+38.0*x6-6.0*x7+
        45.0*x8+16.0*x9;
c180:=
        0 <= 1387.0*x1+1374.0*x2+1374.0*x3+1368.0*x4+1373.0*x5+1371.0*x6+
        1390.0*x7+1277.0*x8+1386.0*x9;
c181:=
        0 <= 1240.0*x1+1236.0*x2+1240.0*x3+1240.0*x4+1238.0*x5+1242.0*x6+
        1230.0*x7+1237.0*x8+1283.0*x9;
c182:=
        0 <= 263.0*x1+262.0*x2+258.0*x3+251.0*x4+245.0*x5+245.0*x6+265.0*x7 
       +343.0*x8+346.0*x9;
c183:=
        0 <= 1179.0*x1+1177.0*x2+1177.0*x3+1177.0*x4+1174.0*x5+1182.0*x6+
        1181.0*x7+1154.0*x8+1262.0*x9;
c184:=
        0 <= 1109.0*x1+1109.0*x2+1109.0*x3+1109.0*x4+1106.0*x5+1111.0*x6+
        1118.0*x7+1035.0*x8+1192.0*x9;
c185:=
        0 <= 616.0*x1+616.0*x2+616.0*x3+616.0*x4+644.0*x5+607.0*x6+643.0*x7 
       +633.0*x8+581.0*x9;
c186:=
        0 <= 989.0*x1+976.0*x2+1002.0*x3+1002.0*x4+1004.0*x5+1023.0*x6+
        995.0*x7+946.0*x8+994.0*x9;
c187:=
        0 <= 779.0*x1+792.0*x2+786.0*x3+786.0*x4+786.0*x5+763.0*x6+789.0*x7 
       +757.0*x8+816.0*x9;
c188:=
        0 <= 30.0*x1+19.0*x2+11.0*x3+11.0*x4+18.0*x5-41.0*x6-180.0*x7-
        315.0*x8+7.0*x9;
c189:=
        0 <= 1246.0*x1+1247.0*x2+1246.0*x3+1247.0*x4+1247.0*x5+1241.0*x6+
        1243.0*x7+1215.0*x8+1291.0*x9;
c190:=
        0 <= 1970.0*x1+1957.0*x2+1952.0*x3+1952.0*x4+1954.0*x5+1955.0*x6+
        1893.0*x7+1857.0*x8+1932.0*x9;
c191:=
        0 <= 1169.0*x1+1171.0*x2+1173.0*x3+1172.0*x4+1207.0*x5+1201.0*x6+
        1225.0*x7+1114.0*x8+1191.0*x9;
c192:=
        0 <= 925.0*x1+925.0*x2+922.0*x3+922.0*x4+900.0*x5+886.0*x6+961.0*x7 
       +973.0*x8+914.0*x9;
c193:=
        0 <= 195.0*x1+195.0*x2+195.0*x3+195.0*x4+195.0*x5+209.0*x6+85.0*x7 
       +38.0*x8+282.0*x9;
c194:=
        0 <= 1998.0*x1+1998.0*x2+1998.0*x3+1998.0*x4+2006.0*x5+2006.0*x6+
        1933.0*x7+1941.0*x8+2011.0*x9;
c195:=
        0 <= 781.0*x1+774.0*x2+781.0*x3+781.0*x4+783.0*x5+763.0*x6+696.0*x7 
       +309.0*x8+798.0*x9;
c196:=
        0 <= 870.0*x1+870.0*x2+870.0*x3+870.0*x4+870.0*x5+870.0*x6+853.0*x7 
       +773.0*x8+877.0*x9;
c197:=
        0 <= 1583.0*x1+1583.0*x2+1583.0*x3+1583.0*x4+1583.0*x5+1583.0*x6+
        1574.0*x7+1550.0*x8+1558.0*x9;
c198:=
        0 <= 1919.0*x1+1919.0*x2+1919.0*x3+1919.0*x4+1919.0*x5+1915.0*x6+
        1892.0*x7+1885.0*x8+1946.0*x9;
c199:=
        0 <= 924.0*x1+924.0*x2+924.0*x3+903.0*x4+903.0*x5+903.0*x6+903.0*x7 
       +881.0*x8+900.0*x9;
c200:=
        0 <= 292.0*x1+310.0*x2+301.0*x3+304.0*x4+293.0*x5+303.0*x6+298.0*x7 
       +311.0*x8+267.0*x9;
c201:=
        0 <= 382.0*x1+388.0*x2+382.0*x3+403.0*x4+403.0*x5+400.0*x6+394.0*x7 
       +415.0*x8+367.0*x9;
c202:=
        0 <= 1392.0*x1+1392.0*x2+1392.0*x3+1392.0*x4+1392.0*x5+1393.0*x6+
        1397.0*x7+1422.0*x8+1326.0*x9;
c203:=
        0 <= 258.0*x1+258.0*x2+260.0*x3+260.0*x4+265.0*x5+250.0*x6+243.0*x7 
       +210.0*x8+280.0*x9;
c204:=
        0 <= 867.0*x1+867.0*x2+867.0*x3+867.0*x4+869.0*x5+869.0*x6+886.0*x7 
       +891.0*x8+850.0*x9;
c205:=
        0 <= 657.0*x1+657.0*x2+657.0*x3+657.0*x4+657.0*x5+653.0*x6+742.0*x7 
       +748.0*x8+646.0*x9;
c206:=
        0 <= 1981.0*x1+1981.0*x2+1981.0*x3+1981.0*x4+1968.0*x5+1965.0*x6+
        1974.0*x7+2025.0*x8+2025.0*x9;
c207:=
        0 <= 1288.0*x1+1280.0*x2+1316.0*x3+1316.0*x4+1365.0*x5+1387.0*x6+
        1398.0*x7+1393.0*x8+1401.0*x9;
c208:=
        0 <= 1043.0*x1+1025.0*x2+1025.0*x3+1025.0*x4+1024.0*x5+1027.0*x6+
        1041.0*x7+1142.0*x8+1038.0*x9;
c209:=
        0 <= 1437.0*x1+1437.0*x2+1437.0*x3+1437.0*x4+1437.0*x5+1437.0*x6+
        1428.0*x7+1270.0*x8+1447.0*x9;
c210:=
        0 <= 1035.0*x1+985.0*x2+1000.0*x3+1000.0*x4+1000.0*x5+1004.0*x6+
        1022.0*x7+1056.0*x8+1012.0*x9;
c211:=
        0 <= 349.0*x1+354.0*x2+354.0*x3+354.0*x4+354.0*x5+360.0*x6+362.0*x7 
       +303.0*x8+370.0*x9;
c212:=
        0 <= 920.0*x1+938.0*x2+921.0*x3+921.0*x4+932.0*x5+932.0*x6+952.0*x7 
       +969.0*x8+909.0*x9;
c213:=
        0 <= 1699.0*x1+1709.0*x2+1694.0*x3+1694.0*x4+1694.0*x5+1698.0*x6+
        1684.0*x7+1609.0*x8+1683.0*x9;
c214:=
        0 >= -12.0*x1+19.0*x2+4.0*x3+4.0*x4+4.0*x5+33.0*x6+38.0*x7+
        67.0*x8-9.0*x9;
c215:=
        0 <= -10.0*x1+12.0*x2+12.0*x3+43.0*x4+89.0*x5+91.0*x6+133.0*x7+
        568.0*x8-156.0*x9;
    Ranges: [0,1] for all x
    Solving method: MinimizeGradient+HullIConsistency+ 3B
    Solutions:: 1 (approximate, accuracy=1e-4)
    Computation time (September 2004):
    DELL D400 (1.7Ghz) 28mn

    Algebraic: Fredtest (*)

    Origin: COCONUT
    6 equations and 2 inequalities defined by: 

     
delta:=1./30.:
cons1 := a1 + a2 + a3 + 1 =0
cons2 := a1 + 2*a2*x1 + 3*a3*x1^2 + 4*x1^3 =0
cons3 := a1 + 2*a2*x2 + 3*a3*x2^2 + 4*x2^3 =0
cons4 := a1 + 2*a2*x3 + 3*a3*x3^2 + 4*x3^3 =0
cons5 := a1*(x1+x2) + a2*(x1^2 + x2^2) + a3*(x1^3 + x2^3) + x1^4 + x2^4 =0
cons6 := a1*(x2+x3) + a2*(x2^2 + x3^2) + a3*(x2^3 + x3^3) + x2^4 + x3^4 =0
cons7 := x1 + delta -x2<= 0
cons8 := x2 + delta -x3<= 0
    with the a in [-10,10] and the x in [0,1].

    Solving method: HessianSolve+HullConsistency+3B (August 2004)+ Simp2B+IntervalNewton (May 2007)
    Solutions:: 1 (exact)
    Computation time :

    DELL D400 (1.7GHz) (August 2004) over 60 mn
    DELL D620 (1.7GHz) (May 2007) 33mn38s
    If we add equations such as cons2-cons1, cons3-cons2 etc.. that involves a1 the computation time is 90 seconds.

    Algebraic: Jermann chair (*)

    Origin: COPRIN
    Physical meaning: a set of geometrical constraints
    147 equations with 147 unknowns defined by: 

     
H_x^2-36
D8_c*(H_x-D8_x)+D8_a*D8_z
D8_a^2+D8_b^2+D8_c^2-1
-D8_c*D8_x+D8_a*D8_z
-D8_a*D8_y+D8_b*D8_x
D8_a*D8_x+D8_b*D8_y+D8_c*D8_z
-D8_a*D8_y-D8_b*(H_x-D8_x)
D5_a*D8_a+D5_b*D8_b+D5_c*D8_c
D5_a^2+D5_b^2+D5_c^2-1
D5_a*D5_x+D5_b*D5_y+D5_c*D5_z
-D5_b*D5_z+D5_c*D5_y
D5_a*(F_y-D5_y)-D5_b*(F_x-D5_x)
-D5_a*D5_y+D5_b*D5_x
F_x^2+F_y^2-49
-D5_b*D5_z-D5_c*(F_y-D5_y)
D5_a^2+D5_b^2+D3_c^2-1
F_y*Pl4_b
-1+Pl4_b^2+Pl2_c^2
(Pl1_b*Pl4_b+Pl1_c*Pl2_c)^2-.66987298107737597297e-1
F_x*Pl1_a+F_y*Pl1_b
Pl1_a^2+Pl1_b^2+Pl1_c^2-1
D_x*Pl1_a+D_y*Pl1_b+D_z*Pl1_c
D4_a*(D_y-D4_y)-D4_b*(D_x-D4_x)
D4_c*(D_x-D4_x)-D4_a*(D_z-D4_z)
D4_a*D4_x+D4_b*D4_y+D4_c*D4_z
D4_a^2+D4_b^2+D4_c^2-1
D5_a*D4_a+D5_b*D4_b+D5_c*D4_c
-D4_c*D4_x+D4_a*D4_z
-D4_b*D4_z+D4_c*D4_y
D_x^2+D_y^2+D_z^2-4
D4_a^2+D4_b^2+D2_c^2-1
(A_x-D_x)^2+(A_y-D_y)^2+(A_z-D_z)^2-9
D4_c*(A_x-D4_x)-D4_a*(A_z-D4_z)
D4_a*(A_y-D4_y)-D4_b*(A_x-D4_x)
D5_a*(D_y-D3_y)-D5_b*(D_x-D3_x)
D5_a*(C_y-D3_y)-D5_b*(C_x-D3_x)
D4_a*(C_y-D2_y)-D4_b*(C_x-D2_x)
D4_a*(F_y-D2_y)-D4_b*(F_x-D2_x)
D4_a*D2_x+D4_b*D2_y+D2_c*D2_z
D2_c*(C_x-D2_x)-D4_a*(C_z-D2_z)
C_x*Pl1_a+C_y*Pl1_b+C_z*Pl1_c
D5_b*(C_z-D3_z)-D3_c*(C_y-D3_y)
D5_a*D3_x+D5_b*D3_y+D3_c*D3_z
D2_c*(B_x-D2_x)-D4_a*(B_z-D2_z)
D5_a*(B_y-D1_y)-D1_b*(B_x-D1_x)
D5_a*(A_y-D1_y)-D1_b*(A_x-D1_x)
D5_a*D1_x+D1_b*D1_y+D1_c*D1_z
D1_b*(A_z-D1_z)-D1_c*(A_y-D1_y)
D1_b*(B_z-D1_z)-D1_c*(B_y-D1_y)
D4_b*(B_z-D2_z)-D2_c*(B_y-D2_y)
D5_a^2+D1_b^2+D1_c^2-1
D4_c*(I_x-D4_x)-D4_a*(I_z-D4_z)
(A_x-I_x)^2+(A_y-I_y)^2+(A_z-I_z)^2-1
D4_a*(I_y-D4_y)-D4_b*(I_x-D4_x)
D9_b*(I_z-D9_z)-D9_c*(I_y-D9_y)
D5_a*(J_y-D9_y)-D9_b*(J_x-D9_x)
D5_a*(I_y-D9_y)-D9_b*(I_x-D9_x)
D5_a^2+D9_b^2+D9_c^2-1
D5_a*D9_x+D9_b*D9_y+D9_c*D9_z
D2_c*(J_x-D2_x)-D4_a*(J_z-D2_z)
D4_b*(J_z-D2_z)-D2_c*(J_y-D2_y)
D9_b*(J_z-D9_z)-D9_c*(J_y-D9_y)
G_y*Pl4_b+G_z*Pl2_c
D6_a*(G_y-D6_y)-D6_b*(G_x-D6_x)
D6_c*(G_x-D6_x)-D6_a*(G_z-D6_z)
D6_a*D6_x+D6_b*D6_y+D6_c*D6_z
D5_a*D6_a+D5_b*D6_b+D5_c*D6_c
D6_a^2+D6_b^2+D6_c^2-1
D6_c*(F_x-D6_x)+D6_a*D6_z
D6_a*(F_y-D6_y)-D6_b*(F_x-D6_x)
D7_a*(G_y-D7_y)-D7_b*(G_x-D7_x)
-D7_a*D7_y-D7_b*(H_x-D7_x)
D6_a*D7_a+D6_b*D7_b+D6_c*D7_c
D7_a^2+D7_b^2+D7_c^2-1
D7_a*D7_x+D7_b*D7_y+D7_c*D7_z
D7_b*(G_z-D7_z)-D7_c*(G_y-D7_y)
-D7_b*D7_z+D7_c*D7_y
J_y*Pl3_b+J_z*Pl3_c-Pl3_d
I_y*Pl3_b+I_z*Pl3_c-Pl3_d
-1+Pl3_b^2+Pl3_c^2
D6_a^2+D6_b^2+D10_c^2-1
D6_a*D10_x+D6_b*D10_y+D10_c*D10_z
D6_a*(J_y-D10_y)-D6_b*(J_x-D10_x)
D10_c*(K_x-D10_x)-D6_a*(K_z-D10_z)
(J_x-K_x)^2+(J_y-K_y)^2+(J_z-K_z)^2-9
D6_a*(K_y-D10_y)-D6_b*(K_x-D10_x)
K_y*Pl3_b+K_z*Pl3_c-Pl3_d
D6_a*D11_a+D5_b*D6_b+D10_c*D11_c
D11_a^2+D5_b^2+D11_c^2-1
D11_a*D11_x+D5_b*D11_y+D11_c*D11_z
D5_b*(K_z-D11_z)-D11_c*(K_y-D11_y)
D11_a*(K_y-D11_y)-D5_b*(K_x-D11_x)
D6_a^2+D6_b^2+D12_c^2-1
D6_a*D12_x+D6_b*D12_y+D12_c*D12_z
D6_a*(L_y-D12_y)-D6_b*(L_x-D12_x)
D6_a*(I_y-D12_y)-D6_b*(I_x-D12_x)
L_y*Pl3_b+L_z*Pl3_c-Pl3_d
D12_c*(L_x-D12_x)-D6_a*(L_z-D12_z)
D11_a*(L_y-D11_y)-D5_b*(L_x-D11_x)
D17_a*D17_x+D17_b*D17_y+D17_c*D17_z
-D17_c*D17_x+D17_a*D17_z
-D17_a*D17_y+D17_b*D17_x
D17_c*(G_x-D17_x)-D17_a*(G_z-D17_z)
D17_a^2+D17_b^2+D17_c^2-1
D17_a*(G_y-D17_y)-D17_b*(G_x-D17_x)
D17_a*(M_y-D17_y)-D17_b*(M_x-D17_x)
D17_c*(M_x-D17_x)-D17_a*(M_z-D17_z)
(M_x-G_x)^2+(M_y-G_y)^2+(M_z-G_z)^2-M_x^2-M_y^2-M_z^2
-1+Pl4_b^2+D13_c^2
-Pl4_b*D13_z+D13_c*D13_y
Pl4_b*D13_y+D13_c*D13_z
-D13_c*D13_x
-1+Pl4_b^2+D14_c^2
-Pl4_b*D14_z-D14_c*(F_y-D14_y)
D14_c*(F_x-D14_x)
Pl4_b*D14_y+D14_c*D14_z
-1+Pl4_b^2+D15_c^2
Pl4_b*(G_z-D15_z)-D15_c*(G_y-D15_y)
Pl4_b*D15_y+D15_c*D15_z
D15_c*(G_x-D15_x)
Pl4_b*(Q_z-D15_z)-D15_c*(Q_y-D15_y)
D15_c*(Q_x-D15_x)
(G_x-Q_x)^2+(G_y-Q_y)^2+(G_z-Q_z)^2-25
-1+Pl4_b^2+D16_c^2
-Pl4_b*D16_z+D16_c*D16_y
D16_c*(H_x-D16_x)
Pl4_b*D16_y+D16_c*D16_z
-1+Pl4_b^2+Pl4_c^2
Q_y*Pl4_b+Q_z*Pl4_c-Pl4_d
O_y*Pl4_b+O_z*Pl4_c-Pl4_d
Pl4_b*(O_z-D13_z)-D13_c*(O_y-D13_y)
D13_c*(O_x-D13_x)
D18_c*(O_x-D18_x)-D18_a*(O_z-D18_z)
D18_a*(O_y-D18_y)-D18_b*(O_x-D18_x)
D18_c*(Q_x-D18_x)-D18_a*(Q_z-D18_z)
D18_a^2+D18_b^2+D18_c^2-1
D18_a*(Q_y-D18_y)-D18_b*(Q_x-D18_x)
D18_a*D18_x+D18_b*D18_y+D18_c*D18_z
D18_a*(N_y-D18_y)-D18_b*(N_x-D18_x)
(N_x-Q_x)^2+(N_y-Q_y)^2+(N_z-Q_z)^2-(O_x-N_x)^2-(O_y-N_y)^2-(O_z-N_z)^2
D18_c*(N_x-D18_x)-D18_a*(N_z-D18_z)
P_y*Pl4_b+P_z*Pl4_c-Pl4_d
Pl4_b*(P_z-D14_z)-D14_c*(P_y-D14_y)
D14_c*(P_x-D14_x)
R_y*Pl4_b+R_z*Pl4_c-Pl4_d
D16_c*(R_x-D16_x)
Pl4_b*(R_z-D16_z)-D16_c*(R_y-D16_y)
    with the following ranges for the variable: 
     
D8_z,[-100, 100]
D8_a,[-.99999899999999997124, 1]
D8_c,[0, 1]
D8_x,[-100, 100]
D8_b,[-.99999899999999997124, 1]
D8_y,[-100, 100]
D5_c,[0, 1]
D5_b,[-.99999899999999997124, 1]
D5_a,[-.99999899999999997124, 1]
D5_z,[-100, 100]
D5_y,[-100, 100]
D5_x,[-100, 100]
D3_c,[0, 1]
Pl2_c,[0, 1]
Pl1_a,[-1, 1]
Pl1_c,[0, 1]
Pl1_b,[-1, 1]
D4_x,[-100, 100]
D4_z,[-100, 100]
D4_c,[0, 1]
D4_b,[-.99999899999999997124, 1]
D4_a,[-.99999899999999997124, 1]
D4_y,[-100, 100]
H_x,[.10000000000000000364e-9, 56]
F_x,[-50, 50]
F_y,[.10000000000000000364e-9, 57]
D_z,[0, 51.930999999999997385]
D_y,[-.99999999999999995475e-6, 1]
D_x,[-50.517000000000003013, 49.482999999999996987]
A_y,[-.99999999999999995475e-6, 50]
A_z,[0, 54.829000000000000625]
A_x,[-51.29399999999999693, 48.70600000000000307]
C_x,[-50.517000000000003013, 49.482999999999996987]
C_z,[1, 51.930999999999997385]
C_y,[-.99999999999999995475e-6, 57]
B_z,[0, 54.829000000000000625]
B_x,[-51.29399999999999693, 48.70600000000000307]
B_y,[-.99999999999999995475e-6, 57]
I_x,[-51.551999999999999602, 48.448000000000000398]
I_z,[0, 55.795000000000001705]
I_y,[-.99999999999999995475e-6, 50]
J_x,[-51.551999999999999602, 48.448000000000000398]
J_z,[0, 55.795000000000001705]
J_y,[-.99999999999999995475e-6, 57]
G_z,[-50, 50]
G_y,[-43, 57]
G_x,[1, 56]
K_z,[0, 55.795000000000001705]
K_y,[-43, 57]
K_x,[-54.551999999999999602, 45.448000000000000398]
L_x,[-54.551999999999999602, 45.448000000000000398]
L_z,[0, 55.795000000000001705]
L_y,[-50, 6]
M_y,[-46.5, 53.5]
M_x,[-47, 53]
M_z,[-50, 0]
Q_y,[-43, 57]
Q_z,[-55, 0]
Q_x,[-44, 56]
O_z,[-55, 0]
O_y,[-50, 50]
O_x,[-50, 50]
N_x,[-47, 53]
N_y,[-46.5, 53.5]
D2_c,[0, 1]
D3_y,[-100, 100]
D3_x,[-100, 100]
D2_x,[-100, 100]
D2_y,[-100, 100]
D2_z,[-100, 100]
D3_z,[-100, 100]
D1_x,[-100, 100]
D1_b,[-.99999899999999997124, 1]
D1_z,[-100, 100]
D1_y,[-100, 100]
D1_c,[0, 1]
D9_z,[-100, 100]
D9_y,[-100, 100]
D9_x,[-100, 100]
D9_b,[-.99999899999999997124, 1]
D9_c,[0, 1]
D6_x,[-100, 100]
D6_z,[-100, 100]
D6_c,[0, 1]
D6_b,[-.99999899999999997124, 1]
D6_a,[-.99999899999999997124, 1]
D6_y,[-100, 100]
D7_x,[-100, 100]
D7_b,[-.99999899999999997124, 1]
D7_c,[0, 1]
D7_a,[-.99999899999999997124, 1]
D7_z,[-100, 100]
D7_y,[-100, 100]
Pl3_d,[-100, 100]
Pl3_c,[0, 1]
Pl3_b,[-1, 1]
D10_c,[0, 1]
D10_z,[-100, 100]
D10_y,[-100, 100]
D10_x,[-100, 100]
D11_c,[0, 1]
D11_a,[-.99999899999999997124, 1]
D11_z,[-100, 100]
D11_y,[-100, 100]
D11_x,[-100, 100]
D12_c,[0, 1]
D12_z,[-100, 100]
D12_y,[-100, 100]
D12_x,[-100, 100]
D17_z,[-100, 100]
D17_c,[0, 1]
D17_a,[-.99999899999999997124, 1]
D17_x,[-100, 100]
D17_b,[0, 1]
D17_y,[-100, 100]
Pl4_b,[-1, 1]
D13_c,[0, 1]
D13_y,[-100, 100]
D13_z,[-100, 100]
D13_x,[-100, 100]
D14_c,[0, 1]
D14_y,[-100, 100]
D14_z,[-100, 100]
D14_x,[-100, 100]
D15_c,[0, 1]
D15_y,[-100, 100]
D15_z,[-100, 100]
D15_x,[-100, 100]
D16_c,[0, 1]
D16_y,[-100, 100]
D16_z,[-100, 100]
D16_x,[-100, 100]
Pl4_c,[0, 1]
Pl4_d,[-100, 100]
D18_z,[-100, 100]
D18_a,[-.99999899999999997124, 1]
D18_x,[-100, 100]
D18_c,[0, 1]
D18_b,[0, 1]
D18_y,[-100, 100]
N_z,[-55, 0]
P_z,[-55, 0]
P_y,[-43, 57]
P_x,[-50, 50]
R_x,[-44, 56]
R_z,[-55, 0]
R_y,[-50, 50]
    Solving method: GradientSolve+HullConsistency+3B + an adapted splitting strategy (we alternatively split the variable among all variables that has the largest interval width and then the largest variable among the variable whose initial range has a width lower than 5)
    Solutions:: 8 (exact)
    Computation time (April 2007):
    DELL D620 (1.7GHz) 60 mn
    Note that the decomposition method proposed in the COPRIN project allows a much lower solving time (after the decomposition the solving time is less than one second).

    Algebraic: Synthesis problem

    Origin: COPRIN
    Physical meaning: determine the geometrical parameters of a parallel robot so that its "hand" may reach 3 given poses

    33 equations with 33 unknowns defined by: 

     
xc^2+yc^2+zc^2-168.=0
 
218.+xl^2+yl^2-10*xc-13.702*xl-1.3942*yl-10*yc+2*xc*(.82181*xl-.54841*yl)+
2*yc*(.54841*xl+.68784*yl)+2*zc*(.15451*xl+.47553*yl)-ro2=0

 293.+xl1^2+yl1^2+20*xc+10.952*xl1-17.847*yl1-10*yc+
2*xc*(.82181*xl1-.54841*yl1)+2*yc*(.54841*xl1+.68784*yl1)+2*zc*(.15451*xl1+.47553*yl1)-1.*ro3=0

 (x1+7.)^2+(y1-15.)^2+z1^2-25.=0

 44.148+(-2*x1-21.013)*(xc-3.5064)+(-2*y1+8.6653)*(yc-10.667)+
(-1.5819-2*z1)*(zc-.79094)=0
 
(x2-7.)^2+(y2-15.)^2+z2^2-140.63=0

 230.51+(-2*x2+1.9566)*(xc-6.0217)+(20.319-2*y2)*(yc-4.8403)+
(-2*z2+6.9226)*(zc+3.4613)=0
 
(-4*yc+42.669)*z1+(4*y1-60)*(zc-.79094)=0

(-14.026+4.*xc)*z1+(-4*x1-28)*(zc-.79094)=0

(-4*yc+19.361)*z2+(4*y2-60)*(zc+3.4613)=0

(-24.087+4.*xc)*z2+(-4*x2+28)*(zc+3.4613)=0

 xcn^2+ycn^2+zcn^2-168.=0

 218.+xl^2+yl^2-10*xcn-13.415*xl+4.0849*yl-10*ycn+
2*xcn*(.53349*xl-.80801*yl)+2*ycn*(.80801*xl+.39952*yl)+
2*zcn*(0.25*xl+.43301*yl)-1.*ro2=0

 293.+xl1^2+yl1^2+20*xcn+2.5897*xl1-20.155*yl1-10*ycn+
2*xcn*(.53349*xl1-.80801*yl1)+2*ycn*(.80801*xl1+.39952*yl1)+
2*zcn*(0.25*xl1+.43301*yl1)-1.*ro3=0
 
(x1n+7.)^2+(y1n-15.)^2+z1n^2-25.=0

 -72.985+(-22.512-2*x1n)*(xcn-4.2558)+(.15703-2*y1n)*(ycn-14.921)+
(-3.5118-2*z1n)*(zcn-1.7559)=0
 
(x2n-7.)^2+(y2n-15.)^2+z2n^2-140.63=0

 152.57+(-6.5539-2*x2n)*(xcn-10.277)+(19.095-2*y2n)*(ycn-5.4526)+
(-2*z2n+7.5539)*(zcn+3.7769)=0

 (-4*ycn+59.686)*z1n+(4*y1n-60)*(zcn-1.7559)=0

(-17.023+4*xcn)*z1n+(-4*x1n-28)*(zcn-1.7559)=0

(-4*ycn+21.810)*z2n+(4*y2n-60)*(zcn+3.7769)=0

(-41.108+4*xcn)*z2n+(-4*x2n+28)*(zcn+3.7769)=0

 xcns^2+ycns^2+zcns^2-168.=0

 218.+xl^2+yl^2-10*xcns-13.8*xl-1.2648*yl-10*ycns+
2*xcns*(.80097*xl-.58856*yl)+2*ycns*(.57907*xl+.71504*yl)+
2*zcns*(.15205*xl+.37725*yl)-1.*ro2=0

 293.+xl1^2+yl1^2+20*xcns+10.229*xl1-18.922*yl1-10*ycns+
2*xcns*(.80097*xl1-.58856*yl1)+2*ycns*(.57907*xl1+.71504*yl1)+
2*zcns*(.15205*xl1+.37725*yl1)-1.*ro3=0

 (x1ns+7.)^2+(y1ns-15.)^2+z1ns^2-25.=0

 34.217+(-21.028-2*x1ns)*(xcns-3.5138)+(-2*y1ns+7.9964)*(ycns-11.002)+
(-3.61-2*z1ns)*(zcns-1.805)=0

 (x2ns-7.)^2+(y2ns-15.)^2+z2ns^2-140.63=0

 233.73+(-2*x2ns+1.169)*(xcns-6.4155)+(-2*y2ns+20.901)*(ycns-4.5493)+
(-2*z2ns+5.1370)*(zcns+2.5685)=0

 108.30+(-4*ycns+44.007)*z1ns-60*zcns+(-7.2200+4*zcns)*y1ns=0

 50.540+(-14.055+4*xcns)*z1ns-28*zcns+(-4*zcns+7.22)*x1ns=0

 -154.11+10.274*y2ns+(-60+4*y2ns)*zcns+(-4*ycns+18.197)*z2ns=0
 
-10.274*x2ns+71.918+(-4*x2ns+28)*zcns+(-25.662+4*xcns)*z2ns=0
    Unknowns: 
     
[xc, yc, zc, x1, y1, z1, x2, y2, z2, xcn, ycn, zcn, x1n, y1n, z1n, x2n, y2n, 
z2n, xcns, ycns, zcns, x1ns, y1ns, z1ns, x2ns, y2ns, z2ns, ro2, ro3, xl, yl, 
xl1, yl1]
    Ranges: 
     
[-12.9614813968157204619319348722, 12.9614813968157204619319348722]
 [-12.9614813968157204619319348722, 12.9614813968157204619319348722]
 [0, 12.9614813968157204619319348722]
 [-12., -2.]
 [10., 20.]
 [0, 5.]
 [-4.8589569167276084735123948492, 18.8589569167276084735123948492]
 [3.1410430832723915264876051508,26.8589569167276084735123948492]
 [0, 11.8589569167276084735123948492]
 [-12.9614813968157204619319348722, 12.9614813968157204619319348722]
 [-12.9614813968157204619319348722, 12.9614813968157204619319348722]
 [0, 12.9614813968157204619319348722]
 [-12., -2.]
 [10., 20.]
 [0, 5.]
 [-4.8589569167276084735123948492, 18.8589569167276084735123948492]
 [3.1410430832723915264876051508, 26.8589569167276084735123948492]
 [0, 11.8589569167276084735123948492]
 [-12.9614813968157204619319348722, 12.9614813968157204619319348722]
 [-12.9614813968157204619319348722, 12.9614813968157204619319348722]
 [0, 12.9614813968157204619319348722]
 [-12., -2.]
 [10., 20.]
 [0, 5.]
 [-4.8589569167276084735123948492, 18.8589569167276084735123948492]
 [3.1410430832723915264876051508, 26.8589569167276084735123948492]
 [0, 11.8589569167276084735123948492]
 [49, 529]
 [49, 529]
 [8, 16]
 [2, 10]
 [-16, -8]
 [2, 10]
    Solving method: GradientSolve+HullConsistencyStrong+ 3B
    Solutions:: 2 (exact)
    Computation time (May 2004):
    Cluster (15 PC's) 38 hours

    Algebraic: Virasoro

    Origin: Faugère, http://www-calfor.lip6.fr
    8 equations 

    8*x1^2+8*x1*x2+8*x1*x3+2*x1*x4+2*x1*x5+2*x1*x6+2*x1*x7-8*x2*x3-2*x4*x7-2*x5*x6-x1
 8*x1*x2-8*x1*x3+8*x2^2+8*x2*x3+2*x2*x4+2*x2*x5+2*x2*x6+2*x2*x7-2*x4*x6-2*x5*x7-x2
 -8*x1*x2+8*x1*x3+8*x2*x3+8*x3^2+2*x3*x4+2*x3*x5+2*x3*x6+2*x3*x7-2*x4*x5-2*x6*x7-x3
 2*x1*x4-2*x1*x7+2*x2*x4-2*x2*x6+2*x3*x4-2*x3*x5+8*x4^2+8*x4*x5+2*x4*x6+2*x4*x7+6*x4*x8-6*x5*x8-x4
 2*x1*x5-2*x1*x6+2*x2*x5-2*x2*x7-2*x3*x4+2*x3*x5+8*x4*x5-6*x4*x8+8*x5^2+2*x5*x6+2*x5*x7+6*x5*x8-x5
 -2*x1*x5+2*x1*x6-2*x2*x4+2*x2*x6+2*x3*x6-2*x3*x7+2*x4*x6+2*x5*x6+8*x6^2+8*x6*x7+6*x6*x8-6*x7*x8-x6
 -2*x1*x4+2*x1*x7-2*x2*x5+2*x2*x7-2*x3*x6+2*x3*x7+2*x4*x7+2*x5*x7+8*x6*x7-6*x6*x8+8*x7^2+6*x7*x8-x7
 -6*x4*x5+6*x4*x8+6*x5*x8-6*x6*x7+6*x6*x8+6*x7*x8+8*x8^2-x8

    Ranges: [-1,1]

    Solving method: HessianSolve+HullConsistency+3B
    Solutions:: 224 (exact)
    Computation time (April 2003):

    Cluster (11 PC's) 35 mn

    Algebraic: Watson

    Origin: [8]
    31 equations with n variables and ti =i/29

    \begin{eqnarray*} &&i =1 ~~~~x_1\\ &&i =2 ~~~~x_2-x_1^2-1\\ &&i=1,\ldots,29~~~... ...=2}^{j=n}(j-1)t^{j-2}_ix_j-(\sum_{j=1}^{j=n}t^{j-1}_ix_j)^2-1\\ \end{eqnarray*}

    Ranges: [-1e8,1e8] for all unknowns

    Solving method: HessianSolve+HullConsistency+ SimplexConsistency+3B
    Solutions:: 0 (n=6,7,8,9)
    Computation time

    Evo 410C (1.2Ghz)(April 2003): 1.52s (n=6), 41.87s (n=7), 120mn (n=8)
    Cluster (11 PC's)(April 2003): 21mn (n=8) 3h14mn (n=9)
    DELL D620 (1.7Ghz) (May 2007): 50mn (n=8)

    Non algebraic: Biggs EXP6 (*)

    Origin: [9]
    Let $t_i =0.1 i$ and $y_i = e^{-t_i}-5 e^{-10t_i}+3 e^{-4t_i}$

    \begin{displaymath} x_3 e^{-t_i x_1}-x_4 e^{-t_i x_2}+x _6 e^{-t_i x_5}-y_i \end{displaymath}

    for i = 1..6
    Ranges:[-20,20] for all variables

    These equations are linear in the variables $x_3, x_4, x_6$. Three of them are used to solve in these variables. The remaining equations has 4 solutions

    Non Algebraic: Direct kinematics

    Origin: COPRIN
    Physical meaning: determine the pose parameters of the platform of a parallel robot

    11 equations with 11 unknowns defined by: 

     
xc^2+yc^2+zc^2-164=0

304.0192-20*xc-300*cos(p)+100*sin(p)*cos(t)-10*yc-150*sin(p)
-50*cos(p)*cos(t)+30*xc*cos(p)-10*xc*sin(p)*cos(t)+30*yc*sin(p)
+10*yc*cos(p)*cos(t)+10*zc*sin(t)=0

304.0192+20*xc-300*cos(p)-100*sin(p)*cos(t)-10*yc+150*sin(p)
-50*cos(p)*cos(t)-30*xc*cos(p)-10*xc*sin(p)*cos(t)-30*yc*sin(p)
+10*yc*cos(p)*cos(t)+10*zc*sin(t)=0

(x1+7)^2+(y1-15)^2+z1^2-25=0

(cos(p)*(x1-xc)+sin(p)*(y1-yc)+7.000000)^2+(-sin(p)*cos(t)*(x1-xc)
+cos(p)*cos(t)*(y1-yc)+sin(t)*(z1-zc)-7.011678)^2+(sin(p)*sin(t)*(x1-xc)
-cos(p)*sin(t)*(y1-yc)+cos(t)*(z1-zc)+4.065716)^2-25.46010=0

(x2-7)^2+(y2-15)^2+z2^2-25=0

(cos(p)*(x2-xc)+sin(p)*(y2-yc)-7.000000)^2+(-sin(p)*cos(t)*(x2-xc)
+cos(p)*cos(t)*(y2-yc)+sin(t)*(z2-zc)-7.011678)^2+(sin(p)*sin(t)*(x2-xc)
-cos(p)*sin(t)*(y2-yc)+cos(t)*(z2-zc)+4.065716)^2-25.46010=0

60.*z1-4.*z1*yc+(28.04672*y1-420.7008)*sin(t)+(243.9430-16.26286*y1)*cos(t)
+28.*z1*sin(p)+(-16.26286*sin(t)*z1-28.04672*cos(t)*z1)*cos(p)
+(-60.+4.*y1)*zc=0

28.*z1+4.*z1*xc+(-196.3270-28.04672*x1)*sin(t)+(113.8400+16.26286*x1)*cos(t)
+(-16.26286*sin(t)*z1-28.04672*cos(t)*z1)*sin(p)-28.*z1*cos(p)
+(-4.*x1-28.)*zc=0

60.*z2-4.*z2*yc+(-420.7008+28.04672*y2)*sin(t)+(243.9430-16.26286*y2)*cos(t)
-28.*z2*sin(p)+(-28.04672*cos(t)*z2-16.26286*sin(t)*z2)*cos(p)+(4.*y2-60.)*zc=0

-28.*z2+4.*z2*xc+(196.3270-28.04672*x2)*sin(t)+(-113.8400+16.26286*x2)*cos(t)
+(-28.04672*cos(t)*z2-16.26286*sin(t)*z2)*sin(p)+28.*z2*cos(p)+(-4.*x2+28.)*zc=0
    Unknowns: 
     
[xc, yc, zc, p, t, x1, y1, z1, x2, y2, z2]
    Ranges: 
     
[-12.80624847, 12.80624847]
[-12.80624847, 12.80624847]
[0, 12.80624847]
[-1.570796327, 1.570796327]
[-1.570796327, 1.570796327]
[-12., -2.]
[10., 20.]
[-5., 5.]
[2., 12.]
[10., 20.]
[-5., 5.]
    Solving method: GradientSolve or HessianSolve+HullConsistency+ 3B
    Solutions:: 2 (exact with HessianSolve, approximate with GradientSolve))
    Computation time (May 2004):
    DELL D400 (1.7GHz) 48mn (GradientSolve)
    DELL D400 (1.7GHz) 2h17mn (HessianSolve)
    Cluster (15 PC's) 38mn (HessianSolve)

    Non algebraic: ex14-2-3

    Origin: COPRIN, modified from Floudas, C A, Pardalos, P M, Adjiman, C S, Esposito, W R, Gumus, Z H, Harding, S T, Klepeis, J L, Meyer, C A, and Schweiger, C A, Handbook of Test Problems in Local and Global Optimization. Kluwer Academic Publishers, 1999.
    9 equations in 6 variables (x1,x2,x3,x4,x5,x7):
    Ranges for the variables:[1e-6,1],[1e-6,1],[1e-6,1],[1e-6,1],[20,80],[-10,10] 

    e2:=log(x1 + 1.2689544013438*x2 + 0.696334182309743*x3 + 0.590071729272002*x4)
      + x1/(x1 + 1.2689544013438*x2 + 0.696334182309743*x3 + 0.590071729272002*
     x4) + 1.55190688128384*x2/(1.55190688128384*x1 + x2 + 0.696676834276998*x3
      + 1.27289874839144*x4) + 0.767395887387844*x3/(0.767395887387844*x1 + 
     0.176307940228365*x2 + x3 + 0.187999658986436*x4) + 0.989870205661735*x4/(
     0.989870205661735*x1 + 0.928335072476283*x2 + 0.308103094315467*x3 + x4)
      + 2787.49800065313/(229.664 + x5) - x7 -10.7545020354713:

e3:= log(1.55190688128384*x1 + x2 + 0.696676834276998*x3 + 1.27289874839144*x4)
      + 1.2689544013438*x1/(x1 + 1.2689544013438*x2 + 0.696334182309743*x3 + 
     0.590071729272002*x4) + x2/(1.55190688128384*x1 + x2 + 0.696676834276998*
     x3 + 1.27289874839144*x4) + 0.176307940228365*x3/(0.767395887387844*x1 + 
     0.176307940228365*x2 + x3 + 0.187999658986436*x4) + 0.928335072476283*x4/(
     0.989870205661735*x1 + 0.928335072476283*x2 + 0.308103094315467*x3 + x4)
      + 2696.24885600287/(226.232 + x5) - x7 -10.3803549837107:

e4:= log(0.767395887387844*x1 + 0.176307940228365*x2 + x3 + 0.187999658986436*
     x4) + 0.696334182309743*x1/(x1 + 1.2689544013438*x2 + 0.696334182309743*x3
      + 0.590071729272002*x4) + 0.696676834276998*x2/(1.55190688128384*x1 + x2
      + 0.696676834276998*x3 + 1.27289874839144*x4) + x3/(0.767395887387844*x1
      + 0.176307940228365*x2 + x3 + 0.187999658986436*x4) + 0.308103094315467*
     x4/(0.989870205661735*x1 + 0.928335072476283*x2 + 0.308103094315467*x3 + 
     x4) + 3643.31361767678/(239.726 + x5) - x7 -12.9738026256517:

e5:= log(0.989870205661735*x1 + 0.928335072476283*x2 + 0.308103094315467*x3 + 
     x4) + 0.590071729272002*x1/(x1 + 1.2689544013438*x2 + 0.696334182309743*x3
      + 0.590071729272002*x4) + 1.27289874839144*x2/(1.55190688128384*x1 + x2
      + 0.696676834276998*x3 + 1.27289874839144*x4) + 0.187999658986436*x3/(
     0.767395887387844*x1 + 0.176307940228365*x2 + x3 + 0.187999658986436*x4)
      + x4/(0.989870205661735*x1 + 0.928335072476283*x2 + 0.308103094315467*x3
      + x4) + 2755.64173589155/(219.161 + x5) - x7 -10.2081676704566:

e6:= (-log(x1 + 1.2689544013438*x2 + 0.696334182309743*x3 + 0.590071729272002*
     x4)) - (x1/(x1 + 1.2689544013438*x2 + 0.696334182309743*x3 + 
     0.590071729272002*x4) + 1.55190688128384*x2/(1.55190688128384*x1 + x2 + 
     0.696676834276998*x3 + 1.27289874839144*x4) + 0.767395887387844*x3/(
     0.767395887387844*x1 + 0.176307940228365*x2 + x3 + 0.187999658986436*x4)
      + 0.989870205661735*x4/(0.989870205661735*x1 + 0.928335072476283*x2 + 
     0.308103094315467*x3 + x4)) - 2787.49800065313/(229.664 + x5) - x7
      +10.7545020354713:

e7:= (-log(1.55190688128384*x1 + x2 + 0.696676834276998*x3 + 1.27289874839144*
     x4)) - (1.2689544013438*x1/(x1 + 1.2689544013438*x2 + 0.696334182309743*x3
      + 0.590071729272002*x4) + x2/(1.55190688128384*x1 + x2 + 
     0.696676834276998*x3 + 1.27289874839144*x4) + 0.176307940228365*x3/(
     0.767395887387844*x1 + 0.176307940228365*x2 + x3 + 0.187999658986436*x4)
      + 0.928335072476283*x4/(0.989870205661735*x1 + 0.928335072476283*x2 + 
     0.308103094315467*x3 + x4)) - 2696.24885600287/(226.232 + x5) - x7
      +10.3803549837107:

e8:= (-log(0.767395887387844*x1 + 0.176307940228365*x2 + x3 + 0.187999658986436
     *x4)) - (0.696334182309743*x1/(x1 + 1.2689544013438*x2 + 0.696334182309743
     *x3 + 0.590071729272002*x4) + 0.696676834276998*x2/(1.55190688128384*x1 + 
     x2 + 0.696676834276998*x3 + 1.27289874839144*x4) + x3/(0.767395887387844*
     x1 + 0.176307940228365*x2 + x3 + 0.187999658986436*x4) + 0.308103094315467
     *x4/(0.989870205661735*x1 + 0.928335072476283*x2 + 0.308103094315467*x3 + 
     x4)) - 3643.31361767678/(239.726 + x5) - x7 +12.9738026256517:

e9:= (-log(0.989870205661735*x1 + 0.928335072476283*x2 + 0.308103094315467*x3
      + x4)) - (0.590071729272002*x1/(x1 + 1.2689544013438*x2 + 
     0.696334182309743*x3 + 0.590071729272002*x4) + 1.27289874839144*x2/(
     1.55190688128384*x1 + x2 + 0.696676834276998*x3 + 1.27289874839144*x4) + 
     0.187999658986436*x3/(0.767395887387844*x1 + 0.176307940228365*x2 + x3 + 
     0.187999658986436*x4) + x4/(0.989870205661735*x1 + 0.928335072476283*x2 + 
     0.308103094315467*x3 + x4)) - 2755.64173589155/(219.161 + x5) - x7
      +10.2081676704566:

e10:=    x1 + x2 + x3 + x4 -1:
    Solving method: GradientSolve +HullConsistency+ 3B (September 2004) Simp2B (May 2007)
    Solutions:: 1, approximate
    Computation time :
    DELL D400 (September 2004),(1.7GHz) 52mn
    Cluster (20 PC/Sun), (September 2004) 3mn
    DELL D620 (May 2007),(1.7GHz) 25mn

    Non algebraic: Osborne 1

    Origin: [9]
    Let $t_i =10(i-1)$ and y1=0.844, y2=0.908, y3=0.932, y4= 0.936, y5=0.925

    \begin{displaymath} f_i = y_i-(x_1+x_2e^{-t_ix_4}+x_3e^{-t_i x_5}) \end{displaymath}

    for i = 1..5
    Ranges:[-10,10] for all variables

    Non algebraic: Trigonometric (*)

    Origin: [8]
    n equations with l being the maximum integer not greater than (i-1)/5

    \begin{displaymath} f_i = 5-(l+1)(1+\cos(x_i))-\sin(x_i)-\sum_{j=5l+1}^{j=5l+5}\cos(x_j) \end{displaymath}

    for n=10,20
    Ranges: [$0,2\pi-0.001$]

    Solving method: GradientSolve+HullConsistencyStrong+3B
    Solutions:: 2 for n=5, 24 for n=10 (exact)
    Computation time :

    Evo 410C (1.2GHz) 11.8s (April 2003) n=5
    DELL D400 (1.7GHz) 6.25s (May 2004) n=5
    DELL D400 (1.7GHz) 1h17mn (May 2004) n=10
    We may add the following equations $f_i-f_{i+2}, f_i-f_{i+3}$ for i from 1 to n-3

    Solutions:: 2 for n=5, 21 (n=10), 288 (n=15) (exact)
    Computation time :

    Evo 410C (1.2Ghz) 2.58s (n=5), 87.77s (n=10) (April 2003)
    Cluster (11 PC's) 14mn (n=15) (April 2003)

    next up previous Next: Bibliography Up: benches Previous: Other problems: inequalities, parametric
  • J-P. Merlet home page
  • La page Présentation de HEPHAISTOS
  • HEPHAISTOS home page
  • La page "Présentation" de l'INRIA
  • INRIA home page

    jean-pierre merlet