RE: [Help-glpk] Knapsack problem using GLPK

[Roberson, Kelly]

If you have one in either mps or lp format, please send it to me.  I
have had luck manipulating knapsack problems to improve performance.

Usually by working with the scale of the objective function.

Kelly Roberson
Operations Research 
The Boeing Company

-----Original Message-----
From: Michael Hennebry [mailto:address@hidden 
Sent: Thursday, September 15, 2005 10:27 AM
To: Lingzi Li
Cc: address@hidden
Subject: Re: [Help-glpk] Knapsack problem using GLPK


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



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