Re: How to linearize a weighted average with a decision variable?
Matt <[email protected]>
| Newsgroups | gmane.comp.gnu.glpk |
|---|---|
| Message-ID | <CA+jyAG8Dz6DMUJ8kr=zeMcD80GGfUAADSzyw6dgQf0crQadDEA@mail.gmail.com> |
By the way, this is basically the same question with a better explanation and a simple example: https://math.stackexchange.com/questions/2752558/how-to-linearize-a-weighted-average-with-a-decision-variable On Wed, Apr 25, 2018 at 11:04 AM, Michael Hennebry < [email protected]> wrote: > 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