Re: [Help-glpk] multiplication of linear forms not allowed

[Mihai Banciu]

I suspect that you may be wrong on one count. a[i] shouldn't be a
variable, but a parameter. Basically, what yo need to do is solve the LP
relaxation of the original MKP, get the dual variables a[i] associated
with the solution, and use those duals as *FIXED* parameters in the
surrogate problem!. This way, in the surrogate, the only variables are
x[j] and your problem is linear, since a[i]'s are fixed.

Check out this reference for more information: "A Genetic Algorithm for
the Multidimensional Knapsack Problem" by P.C. Chu and J.E Beasley,
Journal of Heuristics, 4:63-86, 1998, specifically page 73. Given your
research interests, I suspect this may be something you like.

Take care,
Mihai

Jorge Tavares wrote:
> Hi,
>
> First of all, thank you for our reply Andrew.
>
> On Nov 30, 2005, at 04:45 , Andrew Walbran wrote:
>
> >> Could you please clarify which of a, r, x, c are variables, and
> which are
> >> parameters?
>
> I am sorry, I forgot to specify it: "x" is a variable and can take any
> value from 0 to 1, "a" is a binary variable and "r" and "c" are
> parameters.
>
> >> If both a and r are variables, then this is not a linear program,
> and GLPK
> >> cannot solve it (at least not without first rewriting it to be
> linear, if
> >> possible).
>
> My fear is that glpk cannot solve this problem because of the dual
> variables as surrogate multipliers. Nevertheless, this is a
> simplification of the original problem by transforming all constraints
> into a single one, which then is supposed to be solved by linear
> programming.
>
> If glpk reveals to be unable to solve this problem, any recomendations
> for a software package that might do it?
>
> Thanks in advance,
> Jorge
>
> --
> Jorge Tavares
> University of Coimbra | http://eden.dei.uc.pt/~jast
>
> "Sometimes the appropriate response to reality is to go insane."
>
>
>

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