Re: Re[Help-glpk] garding speeding up MIPs by providing Initial solutions

2009-04-06 Thread Andrew Makhorin 
 Thanks for your reply. Please see
 my reply in the lines.

I've tested your model. In fact, it is not hard for glpk 4.37 and can
be solved in several minutes. However, it is hard enough to be solved
faster.

The model looks like a pseudo-boolean problem (more precisely, like
a satisfiability problem), so you might try to use specific solvers.

 Why do you need to solve the mip many times? Is it a subproblem?
 Do you really need optimal solution, or a suboptimal solution would be
 sufficient to you?

 Because I need to change the constraints according to the solution and
  solve the MIP again. For a MIP, I need an optimal solution. For my big
  problem, of course , it is suboptimal. If I form my big problem into
  a mip, then it will be huge and takes forever to run.

I think that in many cases using a complete description is more
reasonable. If, for example, the complete mip is huge because it has too
many rows (constraints), you could use row generation technique.


Andrew Makhorin







 




___
Help-glpk mailing list
Help-glpk@gnu.org
http://lists.gnu.org/mailman/listinfo/help-glpk

Re: Re[Help-glpk] garding speeding up MIPs by providing Initial solutions

2009-04-02 Thread Andrew Makhorin 
 I am suffering from the same problem. I have tried all the following but
 none works.
 [...]
 My problem size is
 Rows:   711
 Columns:189 (189 integer, 189 binary)
 And the solution time is 270s which is too slow for me because I need to
 call it many times in my code.

Why do you need to solve the mip many times? Is it a subproblem?
Do you really need optimal solution, or a suboptimal solution would be
sufficient to you?

  What else can I do to speed it up?

Could you write your instance in in mps or cplex lp format, gzip it,
and post it to me?

  Do I
 need to study the branch and cut API routines? Is it possible to provide
 an initial solution in the current version?

Yes.

  Will it speed up the program?

In principle, yes.

 Is it possible to bound the object function as mentioned in the original
 post?

Yes, however, it is better to use glp_ios_heur_sol.


Andrew Makhorin



___
Help-glpk mailing list
Help-glpk@gnu.org
http://lists.gnu.org/mailman/listinfo/help-glpk

Re: Re[Help-glpk] garding speeding up MIPs by providing Initial solutions

2009-04-01 Thread rainly 

Hi,

I am suffering from the same problem. I have tried all the following but
none works.
glp_scale_prob(lp, GLP_SF_AUTO);
glp_adv_basis(lp, 0);   
glp_simplex(lp, NULL);
glp_iocp *parm=new glp_iocp;
glp_init_iocp(parm);
parm-presolve=GLP_ON;
parm-gmi_cuts=GLP_ON;
parm-clq_cuts=GLP_ON;
parm-mir_cuts=GLP_ON;
parm-cov_cuts=GLP_ON;
parm-binarize=GLP_ON;
My problem size is
Rows:   711
Columns:189 (189 integer, 189 binary)
And the solution time is 270s which is too slow for me because I need to
call it many times in my code. What else can I do to speed it up? Do I need
to study the branch and cut API routines? Is it possible to provide an
initial solution in the current version? Will it speed up the program? Is it
possible to bound the object function as mentioned in the original post?

Thanks a lot.



Ali Baharev wrote:
 
 You could try the local branching heuristic (Fischetti-Lodi) to
 optimize your initial solution, please see the attached pdf.
 
 If you have a pretty fast heuristic to generate feasible solutions,
 why don't you try genetic algorithm?
 
 Ali
 
 On 12/19/06, Andrew Makhorin m...@gnu.org wrote:
 From what I understand by looking at the GLPK manuals, it does provide
 you
  with the capability to specify a bound on the objective function value
  which avoids extra branching. For my problem, I have formulated it as a
  MIP optimization problem. Currently, it takes too long to solve it and
 I
  have tried almost all relevant options. The other approach that I think
  might work is to employ a heuristic to get a feasible solution and then
  feed the
  entire solution to GLPK. THe heuristic I have currently is very fast so
 if
  GLPK accepts an initial solution of the MIP and optimizes it furthur,
 one
  would expect the runtime to go down.
 
  Does GLPK let you accomplish this in some direct/indirect way?

 Such feature is not implemented yet. However, it is easy to write
 the initial incumbent objective value directly into the bb data
 structure. If you are interested in hacking, I can explain how to
 do that.

 Andrew Makhorin



 ___
 Help-glpk mailing list
 Help-glpk@gnu.org
 http://lists.gnu.org/mailman/listinfo/help-glpk

 
  
 

-- 
View this message in context: 
http://www.nabble.com/Regarding-speeding-up-MIPs-by-providing-Initial-solutions-tp7885588p22839794.html
Sent from the Gnu - GLPK - Help mailing list archive at Nabble.com.



___
Help-glpk mailing list
Help-glpk@gnu.org
http://lists.gnu.org/mailman/listinfo/help-glpk