1
$\begingroup$

I'm trying to model a problem in GLPK but it turned out to be non linear.

A simplified version of the model is written below. Basically it is a weighted average of a set of features of all enabled points substracting a cost associated to enabling those points, provided there are exactly P enabled points.

$\max {\sum_{i=1}^N { f_i \times e_i \times w_i } \over \sum_{i=1}^N { e_i \times w_i } } - \sum_{i=1}^N {c_i \times e_i}$

Subject to constraint $\sum_{i=1}^N e_i = P$

Where:

  • e (enabled) is a vector of either 0 or 1 (decision variable)
  • f (feature) is a vector of decimal numbers in [0,1] (precomputed)
  • w (weight) is a vector of decimal numbers in [0,1] (precomputed)
  • c (cost) is a vector of decimal numbers in [0,1] (precomputed)

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.

So the questions are these.

  1. Is there a way to linearize this model so I can solve it with GLPK or similar?
  2. Do you know any (free) software I can use to solve or approximate it as a non linear model?

Here is a simple example:

N = 5

P = 2

f = (0.1, 0.6, 0.5, 0.5, 0.8)

w = (0.2, 0.3, 0.2, 0.2, 0.1)

c = (0.5, 0.5, 0.5, 0.3, 0.5)

In this scenario the result should be this:

e = (0, 0, 0, 1, 1)

$\endgroup$
4
  • $\begingroup$ If $N$ isn't too large, solve the problem for $\sum_i e_i w_i=1$, $\sum_i e_i w_i=2$, etc. Otherwise, write the objective as one fraction (with a convex numerator and linear denominator) and use Schaible's reformulation. $\endgroup$
    – LinAlg
    Apr 25 '18 at 12:05
  • $\begingroup$ But I don't know what are the possible values for $\sum_i e_i \times w_i$. Why are you assuming they're integers? $\endgroup$
    – Mattx
    Apr 25 '18 at 14:43
  • $\begingroup$ My mistake. Schaible it is :) An example is given here. $\endgroup$
    – LinAlg
    Apr 25 '18 at 15:16
  • $\begingroup$ I just added an example with N=5 and P=2. $\endgroup$
    – Mattx
    Apr 25 '18 at 15:18
2
$\begingroup$

This can be linearized but with some effort. The ratio $$y=\frac{\sum_i f_i w_i x_i}{\sum_i w_i x_i}$$ with $x_i \in \{0,1\}$ can be written as a (nonlinear) constraint: $$ y \sum_i w_i x_i = \sum_i f_i w_i x_i$$ where $y$ is an additional continuous variable. The non-linear expression $(y x_i)$ is a continuous variable times a binary variable. I assume $y\ge 0$. We can now linearize $z_i=y x_i$ as: $$\begin{align} &z_i \le M x_i\\ &z_i \le y \\& z_i \ge y - M(1-x_i)\\ &z_i \ge 0\end{align} $$ Here $M$ is an upper bound on $y$. We have $M=1$ because of the values $w_i$ and $f_i$ can assume.

So putting things together we have: $$\begin{align} \max\> & y - \sum_i c_i x_i\\ & \sum_i w_i z_i = \sum_i f_i w_i x_i\\ & 0 \le z_i \le x_i \\ & y-(1-x_i) \le z_i \le y \\ &y\ge 0\\ & x_i \in \{0,1\} \end{align}$$

I cannot replicate your stated optimal solution. Your solution has:

----     30 VARIABLE obj.L                 =       -0.240  

----     30 VARIABLE x.L  original variables

i2 1.000,    i4 1.000

When I solve it, I get a better solution:

----     48 VARIABLE obj.L                 =       -0.200  

----     48 VARIABLE x.L  original variables

i4 1.000,    i5 1.000


----     48 VARIABLE y.L                   =        0.600  ratio

----     48 VARIABLE z.L  products y*z(i)

i4 0.600,    i5 0.600

The objective for $x=[0,1,0,1,0]$ is $-0.24$ while my optimal $x=[0,0,0,1,1]$ gives an objective value of $-0.2$. (Assuming no typos in transcribing the problem and data).

A similar problem is formulated here.

$\endgroup$
3
  • $\begingroup$ Thank you for your prompt reply and for pointing out the error, I edited the example. I'll check your model in details but it looks like it works! $\endgroup$
    – Mattx
    Apr 25 '18 at 23:11
  • $\begingroup$ I've checked it in details and I still don't understand one thing. What's the purpose of the constraint $z_i ≥ y − M \times (1−x_i)$? I can see it holds true, but why that one? Also, does this kind of linearization has a name or was introduced by an author I can cite in a paper? I've read the article on your blog but it only references another of your articles. $\endgroup$
    – Mattx
    Apr 28 '18 at 21:29
  • $\begingroup$ The constraint $z_i \ge y - M(1-x_i)$ implements the implication $x_i=1 \Rightarrow z_i = y$. Linearizing a multiplication of a binary variable and a continuous variable is somewhat of a standard thing. I don't think it has a name, $\endgroup$ Apr 28 '18 at 21:37
0
$\begingroup$

Hy guys, I've been struggling to code this problem with pulp (python) for the past couple of days but i finally managed, since i'm new to pulp it's not the cleanest code, bit it works. Here the final code in python for those who are interested:

import numpy as np  
import pandas as pd  
import pulp  

N = 5  
P = 2  
f = [0.1, 0.6, 0.5, 0.5, 0.8]  
w = [0.2, 0.3, 0.2, 0.2, 0.1]  
c = [0.5, 0.5, 0.5, 0.3, 0.5]
  
N = [(i) for i in range(0,N)]  
prob = pulp.LpProblem("weighted average", pulp.LpMaximize)

x = pulp.LpVariable.dicts("x",(N),cat="Binary")
z = pulp.LpVariable.dicts("z",(N),lowBound=0, upBound=None, cat='Continuous')
y = pulp.LpVariable("y",)

cx = []
for i in N:
    cx.append(x[i]*c[i])

prob += y - cx

zw = []
fwx = []
for i in N:
    zw.append(z[i]*w[i])
    fwx.append(f[i]*w[i]*x[i])

zw = sum(zw)
fwx = sum(fwx)
prob += zw == fwx

for i in N:
    prob += z[i] >= 0
    prob += z[i] <= x[i]

for i in N:
    prob += y - (1- x[i]) <= z[i]
    prob += z[i] <= y

prob += y >= 0

X = []
for i in N:
    X.append(x[i])
X = sum(X)
prob += X == P

prob.solve()
print("Status:", pulp.LpStatus[prob.status])

result = []
for v in prob.variables():
    print(v.name, "=", v.varValue)
    result.append(v.varValue)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.