|
»
»
Is GLPK the software that I have been looking for?
|
View:
New views
5 Messages
—
Rating Filter:
Alert me
|
 |
Is GLPK the software that I have been looking for?
by odalman
::
Rate this Message:
I have been searching around for a program to find solutions to little
problems like this: An item of meat costs 160. An item of fish costs 30. An item of milk costs 15. Someone spent 700 and bought at most 6 items. What did he buy? What I want is to just input some constraints: k * 160 + m * 30 + n * 15 = 700 k + m + n ≤ 6 and then get all solutions: k = 4, m = 2, n = 0 Is GLPK the right tool for this kind of problem? I started to read the documentation, but GLPK seems more about finding an optimal solution than finding all solutions. That might be a problem. First I looked at logilab-constraint and PuLP, that are supposed to be able to solve it. But I read about them, and they seem to be Python frontends for GLPK (or some other solver), and since I do not know Python so well, I might just try to use GLPK directly. _______________________________________________ Help-glpk mailing list Help-glpk@... http://lists.gnu.org/mailman/listinfo/help-glpk |
|
|
Re: Is GLPK the software that I have been looking for?
by Andrew Makhorin
::
Rate this Message:
> I have been searching around for a program to find solutions to little
> problems like this: An item of meat costs 160. An item of fish costs 30. > An item of milk costs 15. Someone spent 700 and bought at most 6 items. > What did he buy? > What I want is to just input some constraints: > k * 160 + m * 30 + n * 15 = 700 > k + m + n ? 6 > and then get all solutions: > k = 4, m = 2, n = 0 > Is GLPK the right tool for this kind of problem? I started to read > the documentation, but GLPK seems more about finding an optimal > solution than finding all solutions. That might be a problem. > First I looked at logilab-constraint and PuLP, that are supposed to be > able to solve it. But I read about them, and they seem to be Python > frontends for GLPK (or some other solver), and since I do not know > Python so well, I might just try to use GLPK directly. Glpk is able to solve problems like yours. You need to formulate your problem as MIP, write it, say, in CPLEX LP format or in GNU MathProg modeling language, and then run the solver glpsol. The glpk mip solver is not intended to find all optimal or integer feasible solutions. However, once you have found one solution, you may add an additional constraint to cut off corresponding point; this allows you to find an alternate solution, if it exists. _______________________________________________ Help-glpk mailing list Help-glpk@... http://lists.gnu.org/mailman/listinfo/help-glpk |
|
|
Re: Is GLPK the software that I have been looking for?
by odalman
::
Rate this Message:
Andrew Makhorin skrev:
> The glpk mip solver is not intended to find all optimal or integer > feasible solutions. However, once you have found one solution, you may > add an additional constraint to cut off corresponding point; this > allows you to find an alternate solution, if it exists. > Good idea! Then the program can for example be used to prove that there are no more solutions to the example than the one that I gave. A bit tedious when there are many solutions though. When I read about logilab-constraint at [http://www.logilab.org/card/eid/3441], I noticed that the solver was said to provide 64 solutions to the sample problem described there. Maybe they use a very different kind of solver. _______________________________________________ Help-glpk mailing list Help-glpk@... http://lists.gnu.org/mailman/listinfo/help-glpk |
|
|
Re: Is GLPK the software that I have been looking for?
by Yaron Kretchmer-2
::
Rate this Message:
Try scip, which can give you all solutions. It's free for academic or
personal use,as far as I know Sent from my iPhone On Nov 3, 2009, at 10:10 AM, Erik <esigra@...> wrote: > I have been searching around for a program to find solutions to little > problems like this: An item of meat costs 160. An item of fish costs > 30. > An item of milk costs 15. Someone spent 700 and bought at most 6 > items. > What did he buy? > > What I want is to just input some constraints: > > k * 160 + m * 30 + n * 15 = 700 > k + m + n ≤ 6 > > and then get all solutions: > k = 4, m = 2, n = 0 > > Is GLPK the right tool for this kind of problem? I started to read > the documentation, but GLPK seems more about finding an optimal > solution than finding all solutions. That might be a problem. > > > First I looked at logilab-constraint and PuLP, that are supposed to be > able to solve it. But I read about them, and they seem to be Python > frontends for GLPK (or some other solver), and since I do not know > Python so well, I might just try to use GLPK directly. > > > _______________________________________________ > Help-glpk mailing list > Help-glpk@... > http://lists.gnu.org/mailman/listinfo/help-glpk _______________________________________________ Help-glpk mailing list Help-glpk@... http://lists.gnu.org/mailman/listinfo/help-glpk |
|
|
Re: Is GLPK the software that I have been looking for?
by Andrew Makhorin
::
Rate this Message:
> A bit tedious when there are many solutions though. When I read about
> logilab-constraint at [http://www.logilab.org/card/eid/3441], I noticed > that the solver was said to provide 64 solutions to the sample problem > described there. Maybe they use a very different kind of solver. Looks like they use a CP solver, which is able to enumerate all solutions. Note, however, that finding all integer feasible solutions is impractical, because the number of such solutions may grow exponentially. _______________________________________________ Help-glpk mailing list Help-glpk@... http://lists.gnu.org/mailman/listinfo/help-glpk |
| Free embeddable forum powered by Nabble | Forum Help |
