MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: FindInstance

  • To: mathgroup at smc.vnet.net
  • Subject: [mg63834] Re: FindInstance
  • From: Adam Strzebonski <adams at wolfram.com>
  • Date: Tue, 17 Jan 2006 04:33:28 -0500 (EST)
  • Sender: owner-wri-mathgroup at wolfram.com

Changing the inequalities from strict to weak changes the geometry of the problem. In this particular case the problem goes from being "well-oriented" to being not "well-oriented", which makes a huge difference for the cylindrical algebraic decomposition (CAD) algorithm used by FindInstance. 

With the default setup, Mathematica's CAD implementation uses Brown's projection operator. For well-oriented problems this operator gives the smallest projection size. The fact that a problem is not well-oriented is detected during the projection phase, and in this case a larger, but always applicable, Hong's projection is used.

Changing a system option

Developer`SetSystemOptions["InequalitySolvingOptions"->{"BrownProjection"->False}]

makes CAD use McCallum's projection operator. It gives a somewhat larger projection size than Brown's projection operator and the fact that a problem is not well-oriented is not detected during the projection phase. Instead, the algorithm runs the cell construction phase, and if it finds a cell which is not well-oriented it fails and restarts the computation with the full Hong's projection. If we want only one solution, and we are lucky, we may be able to find a solution before stumbling upon a not well-oriented cell. But if we are not lucky we may look at a few million cells, not find a solution, and then find a not well-oriented cell and have to compute the full projection anyway. Your example happens to be a "lucky" case, but there is no way of knowing it without running the algorithm.

In[1]:= Developer`SetSystemOptions["InequalitySolvingOptions"->{"BrownProjection"->False}];
In[2]:= FindInstance[{p[1] == 1, -p[1] + o[1] p[2] - p[4] == 0, -p[2] + o[2] p[3] - p[4] == 0, o[3] p[1] - p[3] - p[4] == 0, -p[1] + o[4] p[4] == 0, x[1] >= 0, x[2] >= 0, x[3] >= 0, x[4] >= 0, o[1] > 0, o[2] > 0, o[3] > 0, o[4] > 0, p[1] > 0, p[2] > 0, p[3] > 0, p[4] > 0, -x[1] + o[3] x[3] - x[4] >= 0, o[1] x[1] - x[2] >= 0, o[2] x[2] - x[3] >= 0, -x[1] - x[2] - x[3] + o[4] x[4] >= 0}, {p[1], p[2], p[3], p[4], o[1], o[2], o[3], o[4], x[1], x[2], x[3], x[4]}]//Timing//InputForm

Out[2]//InputForm=
{0.41*Second, {{p[1] -> 1, p[2] -> 23092/581,
   p[3] -> 325088/581, p[4] -> 4611/1162, o[1] -> 1/8, o[2] -> 5/64,
   o[3] -> 1127/2, o[4] -> 1162/4611, x[1] -> 1, x[2] -> 1/8, x[3] -> 5/512,
   x[4] -> 4611/1024}}}


  • Prev by Date: variable of integration not localized in Integrate and Sum?
  • Next by Date: Re: NDSolve useless?
  • Previous by thread: FindInstance
  • Next by thread: NDSolve useless?