help-glpk
[Top][All Lists]

## Re: [Help-glpk] How to linearize a weighted average with a decision vari

 From: Matt Subject: Re: [Help-glpk] How to linearize a weighted average with a decision variable? Date: Wed, 25 Apr 2018 12:55:09 -0300

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 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.

--