# Rewriting an almost linear program to a linear program

This is my first post on stack exchange. Sorry if I haven't complied with any of the guidelines.

The following shows the almost linear program that I am trying to solve. It gives a solution when using non-linear solvers (such as the GRG non-linear solver in the standard Excel solver).

\begin{alignat*}{2} & \text{minimize: } & & \sum_{j=1}^{m} \text{max($b_{j}$,0)} \\ & \text{subject to: }& \quad & \begin{aligned}[t] c_{j} &= \sum_{i=1}^{n}x_{i}*s_{ij} & \quad j &=1 ,\dots, m\\[3ex] b_{j} &= b_{j-1} + r_{j} - c_{j} &\quad j &=1 ,\dots, m\\[3ex] b_{0} &= b_{m} = 0 \\[3ex] \sum_{j=1}^{m}c_{j} & \leq C \\[3ex] c_{j} & \in \mathbb{R}_{\geq 0} & \quad j &=1 ,\dots, m\\[3ex] x_{i} & \in \mathbb{N}_{0},& i & =1, \dots, n\\[3ex] s_{ij} & \in \{0,1\},& i &=1 , \dots, n & \quad j &=1 ,\dots, m \end{aligned} \end{alignat*}

I am trying to rewrite this to a linear program as follows (I constrain the $b_{j}$ to be real and non-negative): \begin{alignat*}{2} & \text{minimize: } & & \sum_{j=1}^{m} b_{j} \\ & \text{subject to: }& \quad & \begin{aligned}[t] c_{j} &= \sum_{i=1}^{n}x_{i}*s_{ij} & \quad j &=1 ,\dots, m\\[3ex] b_{j} &= b_{j-1} + r_{j} - c_{j} &\quad j &=1 ,\dots, m\\[3ex] b_{0} &= b_{m} = 0 \\[3ex] \sum_{j=1}^{m}c_{j} & \leq C \\[3ex] b_{j}, c_{j} & \in \mathbb{R}_{\geq 0} & \quad j &=1 ,\dots, m\\[3ex] x_{i} & \in \mathbb{N}_{0},& i & =1, \dots, n\\[3ex] s_{ij} & \in \{0,1\},& i &=1 , \dots, n & \quad j &=1 ,\dots, m \end{aligned} \end{alignat*}

However, when I try to solve this linear program with a linear solver it does not give a feasible solution.

My question is: have I made an error in rewriting the program?

• there are two errors: the objective is different, and the product $x_i s_{ij}$ is not linear – LinAlg Nov 21 '16 at 22:53
• @LinAlg The objective is the same because he has constrained the $b_j$ to be non-negative. – tomi Nov 22 '16 at 0:48
• @LinAlg the objective functions are indeed different, because the first one is non linear and I want to rewrite it to a linear one. I was wondering if I had done it correctly by doing what tomi said. And how is the first constraint not linear? If $x_i$ are decision variables, then they are still linearly related to each other in. – Desmond Cheung Nov 22 '16 at 5:01

Something sounds bad in the linearization. When you perform a linearization you must preserve the feasible solutions of the non linear problem. In the first model the $b_j$ variables are unrestricted, while in the second model they are constrained to be nonnegative. So the feasible sets of the two problems are different, and may be that actually the feasible set of the linear model may be empty if you consider $b_j \geq 0$. The right way to linearize the objective function is to introduce new variables $$z_j = max(b_j,0)$$

and the constraints $$z_j \geq b_j$$ $$z_j \geq0$$ leaving the $b_j$ unrestricted.

• Thank you for your reply. I did implement this, but it yielded the same non-feasible solution. I will adjust my program to this. Thank you! – Desmond Cheung Nov 22 '16 at 11:35

Additionally, the multiplication $y_{i,j}=x_i \cdot s_{i,j}$ with $s_{i,j}\in \{0,1\}$ and $x_i\ge 0$ can be linearized as: \begin{align} &y_{i,j} \le s_{i,j}\cdot x^{up}_i\\ &y_{i,j} \le x_i \\ &y_{i,j} \ge x_i - x^{up}_i (1-s_{i,j})\\ &y_{i,j} \in [0,x^{up}_i] \end{align}

• Thank you for your answer, but why isn't that constraint linear? And what is $x_{i}^{up}$? – Desmond Cheung Nov 22 '16 at 10:39
• $x_i^{up}$ is an upperbound on $x_i$ that you determine beforehand. The original constraint is not linear since two variables are multiplied with eachother. – LinAlg Nov 22 '16 at 11:56
• In an LP or MIP linear constraint have the form $a_1 x_1 + a_2 x_2 +... \{\le,=,\ge\} b$ where $a_i$ are constants (numbers). Clearly $x_i \cdot s_{i,,j}$ does not fit this scheme. – Erwin Kalvelagen Nov 22 '16 at 13:24
• @Erwin Kalvelagen Thank you for your answer. The matrix s is a predetermined 0-1 matrix. I haven't made that clear in my question, but I should formulate it this way in my program, right? – Desmond Cheung Nov 22 '16 at 13:31
• If $s_{i,j}$ are constants (we don't care if 0-1 or not) then the model is linear. Usually $s_{i,j} \in \{0,1\}$ indicates $s_{i,j}$ is a binary variable (as for constants we would not care if they are binary). In a description of a model it is very important to make a distinction between decision variables and constants. From this discussion you see why. – Erwin Kalvelagen Nov 22 '16 at 13:40