On Tue, 24 Apr 2018, Matt wrote:
*max sum(i) { enabled[i] * value[i] * weight[i] } / sum(i) { enabled[i] * weight[i] }**s.t. sum (i) enabled[i] = M* - *value* is a vector of decimal numbers in [0, 1] (precomputed) - *weight* is a vector of decimal numbers in [0, 1] (precomputed) - *enabled* is a vector of either 0 or 1 (decision variable)
For linear constraints, there is a tranformation to an LP: https://en.wikipedia.org/wiki/Linear-fractional_programming#Transformation_to_a_linear_program It does not convert an integer problen to an integer problem. My suggestion is to use it to get an LP-based bound, call it q. Then maximize numerator - q*denominator as an IP. If it's zero, you are done. If it's negative, the true objective gives you another q. If it's positive, you made a mistake. You might need to explicitly bound the denominator. -- Michael [email protected] "Sorry but your password must contain an uppercase letter, a number, a haiku, a gang sign, a heiroglyph, and the blood of a virgin." -- someeecards _______________________________________________ Help-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/help-glpk
