[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] The "good enough" set covering problem

From: Andrew Makhorin
Subject: Re: [Help-glpk] The "good enough" set covering problem
Date: Mon, 9 Feb 2009 23:17:56 +0300

> Got it.
> What influences the runtime - the number of sets, or the size of the
> domain?

The number of binary variables and the structure of subsets to be
included in a cover.

> The reason I #39;m asking is that it #39;s pretty easy to break the
> domain up into smaller domains, find good coverages for each of the
> smaller domains, then take a union of all the resulting minimum sets.
> Optimality is not a requirement here, just a "good enough" solution.

If only a suboptimal solution is needed, such decomposition may
significantly reduce the total solution time.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]