"The conflict graph is either empty or too big"
|
View:
New views
11 Messages
—
Rating Filter:
Alert me
|
 |
"The conflict graph is either empty or too big"
by spiritfire
::
Rate this Message:
Hi,
I'm running a simulation and it's taking quite a while... I'm running on Gusek, which is the only way I found to use GLPK (couldn't figure out how to install on win) The program seems to found a solution : OPTIMAL SOLUTION FOUND Integer optimization begins... Gomory's cuts enabled MIR cuts enabled Cover cuts enabled Clique cuts enabled Creating the conflict graph... The conflict graph is either empty or too big But then it goes on searching for quite a while :simul.mod Time used: 1294.0 secs. Memory used: 55.1 Mb. +176120: mip = not found yet >= 5.813433080e+004 (195; 6) +176321: mip = not found yet >= 5.813433080e+004 (196; 6) I have no clue if it's close to the solution, if it's taking too long or if I should wait or ... ? Does anybody know if it is normal ? my code is attached. Thank you. |
|
|
Re: "The conflict graph is either empty or too big"
by Haroldo Gambini Santos
::
Rate this Message:
On Mon, May 14, 2012 at 11:40 AM, spiritfire <bmattlet@...> wrote:
Perfectly normal. Integer programming is hard and solvers can take enormous amount of time to solve it. You could try: - use another solver
- improve your formulation - try different glpsol parameters (ex.: fpump )
============================================================= Haroldo Gambini Santos Computing Department - Universidade Federal de Ouro Preto - UFOP email: haroldo [at ] iceb.ufop.br home/research page: www.decom.ufop.br/haroldo/ "Computer science is no more about computers than astronomy is about telescopes." Edsger Dijkstra _______________________________________________ Help-glpk mailing list Help-glpk@... https://lists.gnu.org/mailman/listinfo/help-glpk |
|
|
Re: "The conflict graph is either empty or too big"
by spiritfire
::
Rate this Message:
I was told that it is quite normal for a MILP problem.
But the lines haven't change for quite a while : +258023: mip = not found yet >= 5.819440044e+004 (242; 34) +260157: mip = not found yet >= 5.819440044e+004 (242; 34) +262192: mip = not found yet >= 5.819440044e+004 (242; 34) +264262: mip = not found yet >= 5.819440044e+004 (242; 34) +266054: mip = not found yet >= 5.819440044e+004 (242; 34) +267696: mip = not found yet >= 5.819440044e+004 (242; 34) +269282: mip = not found yet >= 5.819440044e+004 (242; 34) +269824: mip = not found yet >= 5.819440044e+004 (243; 34) For 15-30 minutes, only the inside of the parenthesis has changed... Since I'm running on Gusek, I don't know which solver is used neither how to change it :-/ If anybody can help ? Should I wait more or stop it and change some parameters ? Thanks a lot. B.
|
|
|
Re: "The conflict graph is either empty or too big"
by xypron
::
Rate this Message:
Hello,
looking at your model, I would suggest considering the following solution approaches: - a time windowing heuristic, which will try to find a solution for a first time windows, fixes the solution for a first part of the time windows and then moves the window for which a solution is sought - a column generation approach (see Column Generation, Guy Desaulniers, Jacques Desrosiers und Marius M. Solomon, Springer, ISBN-13: 978-1441937995) Best regards Xypron -------- Original-Nachricht -------- > Datum: Mon, 14 May 2012 07:40:00 -0700 (PDT) > Betreff: [Help-glpk] "The conflict graph is either empty or too big" > > Hi, > > I'm running a simulation and it's taking quite a while... > > I'm running on Gusek, which is the only way I found to use GLPK (couldn't > figure out how to install on win) > > > The program seems to found a solution : > > OPTIMAL SOLUTION FOUND > Integer optimization begins... > Gomory's cuts enabled > MIR cuts enabled > Cover cuts enabled > Clique cuts enabled > Creating the conflict graph... > The conflict graph is either empty or too big > > > But then it goes on searching for quite a while : > http://old.nabble.com/file/p33830878/simul.mod simul.mod > > Time used: 1294.0 secs. Memory used: 55.1 Mb. > +176120: mip = not found yet >= 5.813433080e+004 (195; 6) > +176321: mip = not found yet >= 5.813433080e+004 (196; 6) > > I have no clue if it's close to the solution, if it's taking too long or > if > I should wait or ... ? > > Does anybody know if it is normal ? > > my code is attached. > > Thank you. -- NEU: FreePhone 3-fach-Flat mit kostenlosem Smartphone! Jetzt informieren: http://mobile.1und1.de/?ac=OM.PW.PW003K20328T7073a _______________________________________________ Help-glpk mailing list Help-glpk@... https://lists.gnu.org/mailman/listinfo/help-glpk |
|
|
Re: "The conflict graph is either empty or too big"
by spiritfire
::
Rate this Message:
Hi everyone, me again.
By doing some researches I found out that my code is doing fine but the problem is hard to solve. I would like to fasten the solver by reducing the precision from 9 to 7 digits. Is it possible ? Or by reducing the number of iterations but I do not know how to do either one of these. I'm using Gusek. Any help is welcome, thank you.
|
|
|
Re: "The conflict graph is either empty or too big"
by spiritfire
::
Rate this Message:
Hi everyone, me again.
By doing some researches I found out that my code is doing fine but the problem is hard to solve. I would like to fasten the solver by reducing the precision from 9 to 7 digits. Is it possible ? Or by reducing the number of iterations but I do not know how to do either one of these. I'm using Gusek. Any help is welcome, thank you.
|
|
|
Re: "The conflict graph is either empty or too big"
by Michael Hennebry
::
Rate this Message:
On Tue, 22 May 2012, spiritfire wrote:
> By doing some researches I found out that my code is doing fine but the > problem is hard to solve. > > I would like to fasten the solver by reducing the precision from 9 to 7 > digits. Is it possible ? Or by reducing the number of iterations but I do > not know how to do either one of these. Reducing iterations will certainly not work: You have yet to get a solution with the iterations you have. Going from double to single precsion would not be helpful on any Intel or AMD device. All floating point arithmetic is done in at least double precision. I'm not sure there are any devices on which you would get a speed up. At better tactic might be to use problem-specific information to generate either constraints or solutions. Also, suppose one has a zero-one problem and for the current "solution" x: 0<=x<=1 SUM x[j] + SUM (1-x[j]) < 1 j in S j in T and there is no feasible solution with x[j]=0 for j in S and x[j]=1 for j in T. In that case SUM x[j] + SUM (1-x[j]) >= 1 is a valid cut j in S j in T -- Michael hennebry@... "On Monday, I'm gonna have to tell my kindergarten class, whom I teach not to run with scissors, that my fiance ran me through with a broadsword." -- Lily _______________________________________________ Help-glpk mailing list Help-glpk@... https://lists.gnu.org/mailman/listinfo/help-glpk |
|
|
Re: "The conflict graph is either empty or too big"
by Meketon, Marc-2
::
Rate this Message:
A long time ago I built linear programming solvers. One of the lessons was that double precision helps in getting solutions faster - using single precision runs into too many numerical problems (say, too many times when the inverse of the basis needs to be rebuilt).
Michael's comment is interesting. Intel architecture does all of its arithmetic in 10-byte precision. Unless you natively use "long double" everywhere, there is always the conversion of the number to a 10-byte real number before a computation is made. The only "win" in a performance viewpoint from using single precision over double precision is the time it takes to fetch 4 bytes versus 8 bytes. And that "win" disappears with 64-bit architecture. -----Original Message----- From: help-glpk-bounces+marc.meketon=oliverwyman.com@... [mailto:help-glpk-bounces+marc.meketon=oliverwyman.com@...] On Behalf Of Michael Hennebry Sent: Tuesday, May 22, 2012 12:34 PM To: spiritfire Cc: Help-glpk@... Subject: Re: [Help-glpk] "The conflict graph is either empty or too big" On Tue, 22 May 2012, spiritfire wrote: > By doing some researches I found out that my code is doing fine but > the problem is hard to solve. > > I would like to fasten the solver by reducing the precision from 9 to > 7 digits. Is it possible ? Or by reducing the number of iterations but > I do not know how to do either one of these. Reducing iterations will certainly not work: You have yet to get a solution with the iterations you have. Going from double to single precsion would not be helpful on any Intel or AMD device. All floating point arithmetic is done in at least double precision. I'm not sure there are any devices on which you would get a speed up. At better tactic might be to use problem-specific information to generate either constraints or solutions. Also, suppose one has a zero-one problem and for the current "solution" x: 0<=x<=1 SUM x[j] + SUM (1-x[j]) < 1 j in S j in T and there is no feasible solution with x[j]=0 for j in S and x[j]=1 for j in T. In that case SUM x[j] + SUM (1-x[j]) >= 1 is a valid cut j in S j in T -- Michael hennebry@... "On Monday, I'm gonna have to tell my kindergarten class, whom I teach not to run with scissors, that my fiance ran me through with a broadsword." -- Lily _______________________________________________ Help-glpk mailing list Help-glpk@... https://lists.gnu.org/mailman/listinfo/help-glpk This e-mail and any attachments may be confidential or legally privileged. If you received this message in error or are not the intended recipient, you should destroy the e-mail message and any attachments or copies, and you are prohibited from retaining, distributing, disclosing or using any information contained herein. Please inform us of the erroneous delivery by return e-mail. Thank you for your cooperation. _______________________________________________ Help-glpk mailing list Help-glpk@... https://lists.gnu.org/mailman/listinfo/help-glpk |
|
|
Re: "The conflict graph is either empty or too big"
by spiritfire
::
Rate this Message:
What about increasing the error? I don't really care about having the optimal solution, I do not need such a precision.
How can I change it ? Because if I stop it before it finds the optimal solution, than I get no results.... I whish to be able to view a solution even if it is not the optimal one. Does anybody knows if such an option is possible ?
|
|
|
Re: "The conflict graph is either empty or too big"
by Andrew Makhorin
::
Rate this Message:
Your instance is hard for the glpk mip solver due to its size and
combinatorial structure. > What about increasing the error? I don't really care about having the optimal > solution, I do not need such a precision. > How can I change it ? Because if I stop it before it finds the optimal > solution, than I get no results.... I whish to be able to view a solution > even if it is not the optimal one. In case of mip to find *any* integer feasible solution is often as hard as to find the optimal one. > > Does anybody knows if such an option is possible ? > You may try to use a more powerful mip solver. See: http://www.neos-server.org/neos/ http://www.neos-server.org/neos/solvers/index.html _______________________________________________ Help-glpk mailing list Help-glpk@... https://lists.gnu.org/mailman/listinfo/help-glpk |
|
|
Re: "The conflict graph is either empty or too big"
by Michael Hennebry
::
Rate this Message:
On Tue, 22 May 2012, spiritfire wrote:
> What about increasing the error? I don't really care about having the optimal > solution, I do not need such a precision. > How can I change it ? Because if I stop it before it finds the optimal > solution, than I get no results.... I whish to be able to view a solution > even if it is not the optimal one. > > Does anybody knows if such an option is possible ? If by "error" you mean difference from optimal, it wouldn't help. GLPK hasn't found any solution. There is an option to use depth-first. That might help you, but I think that that is the default until a solution is found. You probably need problem-specific help. I've made a suggestion regarding solution and constraint generation. Another possibility is problem reformulation. Big-M methods are notorious for producing poorly scaled problems. Another source of problems is symmetry. If you have twenty equivalent booleans, a branch and bound solver is likely to spend a lot of time grinding over equivalent almost-solutions. It might be useful to add symmetry-breaking constraints such as x[j+1]>=x[j] for j in 1..19 . Symmetry-breaking constraints sometimes work, but if one can, it might be more useful to replace the booleans with a single variable indicating the number of ones. If that cannot be done, one can always replace them with five booleans indicating the number of ones. -- Michael hennebry@... "On Monday, I'm gonna have to tell my kindergarten class, whom I teach not to run with scissors, that my fiance ran me through with a broadsword." -- Lily _______________________________________________ Help-glpk mailing list Help-glpk@... https://lists.gnu.org/mailman/listinfo/help-glpk |
| Free embeddable forum powered by Nabble | Forum Help |
