Re: [Help-glpk] How to linearize a weighted average with a decision variable?
On 04/25/2018 03:15 AM, Matt wrote:
> Hi all,
>
> I'm trying to model a problem but it turned out to be non linear.
>
> A simplified version of the model is written below. Basically it
> averages the weighted value of all enabled points, provided there are
> exactly M enabled points.
>
> *max sum(i) { enabled[i] * value[i] * weight[i] } / sum(i) { enabled[i]
> * weight[i] }*
> *s.t. sum (i) enabled[i] = M
If there are no further constraints there is no need for a MIP solver.
The problem can be solved by sorting by value and weight.
If the number of binaries is small (<= 20) you will be able to iterate
over all permutations with sum(enabled) = M sorted by descending
objective and to take the first combination satisfying all constraints.
Regards
Heinrich
> *
>
> - *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)
>
> The model is very simple so I'm guessing there probably is a way to
> linearize it or some workaround I'm not aware of.
>
> Thanks,
> Matt
>
>
> ___
> Help-glpk mailing list
> Help-glpk@gnu.org
> https://lists.gnu.org/mailman/listinfo/help-glpk
>
___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] How to linearize a weighted average with a decision variable?
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 <
henne...@web.cs.ndsu.nodak.edu> 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 henne...@web.cs.ndsu.nodak.edu
> "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
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] How to linearize a weighted average with a decision variable?
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 henne...@web.cs.ndsu.nodak.edu
"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
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] How to linearize a weighted average with a decision variable?
Hi all,
I'm trying to model a problem but it turned out to be non linear.
A simplified version of the model is written below. Basically it averages
the weighted value of all enabled points, provided there are exactly M
enabled points.
*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)
The model is very simple so I'm guessing there probably is a way to
linearize it or some workaround I'm not aware of.
Thanks,
Matt
___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk
