Re: [Help-glpk] Re: Counting solutions rather than optimizing solutions

[Michael Hennebry]

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