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
>
- References:
- FindInstance over Integers
- From: "zac.ernst" <zac.ernst@gmail.com>
- FindInstance over Integers