Re: [Help-glpk] Solve subproblem then use sol'n in larger problem

[Michael Hennebry]

On Fri, 8 Feb 2008, Joey Rios wrote:

> For my particular problem, I have a method for obtaining a feasible, 
> sub-optimal solution using GLPK.  I do this by creating a subproblem that 
> optimizes the 'tricky' parts of the problem.  It's usually within 10-20% of 
> optimal and can be found 10-20X faster than solving the larger problem 
> optimally.  What I would like to start doing is using this solution as a 
> starting point for the larger optimization problem.   Basically, I am asking 
> here if it sounds as if I am thinking about my approach correctly.

Approximately.

> All of the variables in the subproblem will have the same name in the larger 
> problem.  The variables that are missing from the subproblem that are present 
> in the larger problem will have known values that keep the problem feasible 
> (essentially all of the binary vars would be '1' if they weren't in the 
> subproblem).
>
> So what I am thinking I should do is the following:
>
> 1)  Read in MathProg model and data for subproblem.
> 2)  Solve subproblem.
> 3)  Read in MathProg model and data for larger problem.
> 4)  For each column in larger problem, set value according to subproblem 
> solution (since variable names are same in both problems, I think this will 
> be easy?).
> 5)  Solve larger problem.

To do what you want, you need to provide
an initial basis for the bigger problem.
Copy the stati of the common variables and
rows from the subproblem to the big problem.
Place the new binary variables at their upper bounds.
Make the new rows basic.
Tell GLPK to use what you have provided.
If one can, tell GLPK you have an incumbent.
If one cannot, one can tell GLPK that one has a pessimistic bound.
Invoke the simplex method.
Invoke branch and bound.

There are magic words for each of these steps,
but I forget them.

-- 
Michael   address@hidden
"Those parts of the system that you can hit with a hammer (not advised)
are called Hardware;  those program instructions that you can only
curse at are called Software."