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