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 [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
