Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2009

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

Search the Archive

Re: FindInstance over Integers

  • To: mathgroup at smc.vnet.net
  • Subject: [mg101129] Re: [mg101077] FindInstance over Integers
  • From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
  • Date: Wed, 24 Jun 2009 06:36:45 -0400 (EDT)
  • References: <200906231107.HAA08314@smc.vnet.net>

I hope you realize that as there are no general algorithms for solving  
such problems you really have to rely on luck and hope. However, if  
you have to rely on luck and hope your best bet is probably NMinimize,  
which at least will try to solve almost any problem that can be  
formulated as one of "minimalization", that is, it will never tell you  
that "the methods available to it are insufficient " (even though they  
probably are ;-))

Actually, in this particular case they are sufficient:

NMinimize[{1, x == 2^y && x > 2 && Element[x | y, Integers]}, {x, y}]
{1., {x -> 4, y -> 2}}


Andrzej Kozlowski


On 23 Jun 2009, at 20:07, zac.ernst wrote:

> Hello --
>
> I'm working on a project which requires the program to determine
> whether a given set of equalities and inequalities is satisfiable over
> the integers.  Of course, this problem is not decidable in general.
> But I just need a "good enough" function that will at least report
> that a set of constraints is satisfiable only if it actually is, and
> work across some fairly easy cases.  FindInstance is the obvious
> function to use, but it seems to fail for constraints that are very
> easy to satisfy.  The simplest example I can come up with is this:
>
> FindInstance[x == 2^y && x > 2, {x, y}, Integers]
>
> Clearly, {x->4, y->2} would satisfy these constraints, but Mathematica
> reports that "the methods available to FindInstance are
> insufficient...".
>
> It may be relevant that if I change "x > 2" to "x > 1", then
> Mathematica has no problem finding a solution.
>
> Are there any workarounds or alternatives to this approach?
>
> Thanks very much,
> -Zac
>



  • Prev by Date: Re: Matrix construction
  • Next by Date: Re: For loops with mathematica....
  • Previous by thread: Re: FindInstance over Integers
  • Next by thread: Re: FindInstance over Integers