Re: [Help-glpk] Knapsack problem using GLPK

[Michael Hennebry]

On Thu, 15 Sep 2005, Lingzi Li wrote:

> I am using GLPKMEX to develop my project now. It is a branch-and-price
> problem, and I use GLPK to solve Lagrangian relaxation's master and sub
> problems. The subproblem is like the following:
>
> min  y - sum(ui*xi)
> s.t. sum(wi*xi) <= c*y
>      xi + xj <= 1 (for some (i,j))
>      xi, y are binary
>
> (variables are xi and y)
>
> When there are 80 variables, it takes 9 minutes to run out a solution. But if
> there are 100 variables, it will take more than 3 hours. And I do belive that
> most of the time is in subproblem mentioned above. Do you think it is normal
> for 100 variables to take that long time? Or do I need to do some special
> settings for large scale problem? But acturally I don't think 100 variables
> is "large" scale. Thank you very much in advance for your help!

It's an integer problem.
An 80 variable integer problem can be hard.
Yours might or might not be.

Important questions:
What are the signs of the ui's?
What are the signs of the wi's?
Do the (i,j) pairs overlap?

Regardless of the answers to those questions,
tightening the linear relaxation would likely help.

SUM wi*xi - c*y <= 0
 i
x, y  binary

is a knapsack constraint.
There are good separation algorithms
that will let you find cuts that are
facets of the knapsack polytope.
With some analysis, it might be possible to
find facets defined by a smaller polytope,
one that satisfies some of the xi + xj <= 1 constraints.

-- 
Mike   address@hidden
"I AM DEATH, NOT TAXES.  *I* ONLY TURN UP ONCE."  --  Death