Iterative algorithm for a simple linear optimization problem

Question

Let $c_1,\dots,c_n$ be $n$ positive numbers and so be $a_1,\dots, a_n$. For some $r$ such that $1\leq r\leq n$, consider the optimization problem \begin{align} \max_{x_i\in\mathbb{R}}&~~\sum_{i=1}^{r}c_ix_i - \sum_{i=r+1}^{n}c_ix_i \\ & \sum_{i=1}^{r}a_ix_i - \sum_{i=r+1}^{n}a_ix_i \leq b \\ & 0\leq x_i \leq 1~,~\forall i \end{align} I understand that I can use a linear solver for this, however I am interested in finding a separate algorithm for this. I am using the following approach to solve it. First I initialize all $x_i$ as \begin{align} x_i \, = \, \begin{cases}1 ~~\text{if}~i\in\{1,\dots,r\}\\ 0 ~~\text{if}~i\in\{r+1,\dots,n\}\end{cases} \end{align} Note that this is the objective value at the optimum for the unconstrained problem which will be always larger (or equal) than the objective value at optimum of the constrained one. At this point, if this point is feasible, then we are done. Else, note that $\{c_i\}_{r+1}^{n}$ all have a decreasing effect on both objective and LHS of constraint (making it more likely to satisfy the constraint). Thus, I pick the smallest among these $c_i$ and increases its $x_i$ in $[0,1]$ to see if the constraint becomes feasible while decreasing the objective. If not, set $x_i=1$ and pick the second smallest in $\{x_i\}_{i=r+1}^{n}$ and continue in this fashion till I exhaust all in that set. Then I move on to the set $\{c_i\}_{1}^{r}$ and do similar operations there. My question is whether this will find the true solution?

Answer 1

This algorithm is suboptimal. Suppose $a_i=0$ then you change $x_i$ unnecessarily. If you consider the ratio of $c_i$ and $a_i$, you almost mimicked the simplex method.