[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Re: Counting solutions rather than optimizing solutions
From: |
Michael Hennebry |
Subject: |
Re: [Help-glpk] Re: Counting solutions rather than optimizing solutions |
Date: |
Sun, 25 Feb 2007 14:42:29 -0600 (CST) |
On Sun, 25 Feb 2007, Andrew Makhorin wrote:
> >> The issue is unclear. Counting the number of integer feasible solutions
> >> (as well as generating them) for your problem is a trivial task. Since
> >> the problem has no objective, what does "a better solution" mean?
> >
> > I guess he mean more efficient or "elegant" way of solving the problem.
> >
> > It would be nice to see that code counting the 47067239986 solutions.
>
> Here you are. ("Brute force" sometimes is an "elegant" way.)
>
> int main(void)
> { int a, b, c, d, e, f, g, h;
> double count = 0;
> for (a = 0; a <= 1000; a += 200)
> { for (b = a; b <= 1000; b += 100)
> { for (c = b; c <= 1000; c += 50)
> { for (d = c; d <= 1000; d += 20)
> { for (e = d; e <= 1000; e += 10)
> { for (f = e; f <= 1000; f += 5)
> { for (g = f; g <= 1000; g += 2)
> #if 0
> { for (h = g; h <= 1000; h += 1)
> count++;
> }
> #else
> count += 1000 - g + 1;
> #endif
> }
> }
> }
> }
> }
> }
> printf("%20f\n", count);
> return 0;
> }
About the best that can be said for
this code is that it works, eventually.
47 billion is small enough that it's not too time-consuming.
The time required is roughly proportional to the size of the answer.
Better code can be O((r**2)dM), where r is the right hand side,
d is the dimensionality and M is the time required to multiply
large enough numbers.
In this case, r=1000, d=8 and M is at most the time required
to multiply a 10-bit number by a 36-bit number.
With r=10000, the above code might take awhile.
--
Mike address@hidden
"Finally, mount the partition, not the virgin." -- Charles Curley