Rewriting an almost linear program to a linear program

Question

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?

Answer 1

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.

Answer 2

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} $$