# Is it possible to solve a linear programming problem using reinforcement learning? (DDPG algorithm)

I'm trying to solve a linear programming problem using reinforcement learning. The linear programming problem is:

$$\begin{array}{ll} \text{maximize}_x & C* x \\ \text{subject to}& A*x \le b\\ & x_i \in [0,1],\ where \ i=1,2,3,... \end{array}$$

For instance: $$\begin{array}{ll} C &= [1 \; 2 \;3 \;4]\\ x &= [x1; x2; x3; x4]\\ A &= [2 \;3 \;4 \;5]\\ b &= 10\\ \end{array}$$

I've tried to use the DDPG algorithm to train in MATLAB but the result is not good. Any suggestions for this problem, and is it possible to do so, thanks?

• How are you changing a linear programming problem into a markov decision problem? What are the state, actions, and rewards?
– Taw
Aug 19 at 13:03
• In my design, The state is equal to $C.*x$, I mean $[1*x1\ 2*x2\ 3*x3\ 4*x4]$. The action is the matrix x $[x1;x2;x3;x4]$. And the reward is equal to $C*x$, I mean $1*x2+2*x2+3*x3+4*x4$, and the constraint (the isdone signal) is A*x<=b. Do you have any comments on that? Aug 19 at 16:07

In theory, yes, it is possible to model this problem as a Reinforcement Learning. But in practice, RL is not the most suitable approach for a simple linear maximization with a boundary. For instance, you could use a Lagrangian.

### Practical analysis on your specific problem

In this specific example, you have 1 single constrain: $$\sum_{i} a_i x_i \le b$$, for an $$n$$ degree equation (n = size of $$X$$). So you might also want to add another boundary, like: all $$X > 0$$. Otherwise your solution will diverge:

• $$C = [1 2 3 4];$$
• $$X = [x_1; x_2; x_3; x_4];$$
• $$A = [2 3 4 5];$$
• $$b = 10$$

Simple example of divergent solution:

$$X = lim_{k=\infty} [-3k, 0,0, k]$$

Gives you: $$C*X= -3k + 0+0+4k = k$$ ✅ Maximum possible reward for $$lim_{k=\infty}$$

Constrained by $$A*X = -6k + 0 + 0 +5k = -k \le 10$$ ✅ Minimum possible boundary for $$lim_{k=\infty}$$

Edit after adding $$x_i \in [0,1]$$ constraints:

### You have described the simplest version of Knapsack Problem, where we can split items in fractions.

For this problem, the greedy solution is very simple and effective:

Calculate a new weight vector: $$W = C/A = [ c_1 / a_1, c_2/a_2, ... ]$$, which represents the ratio of value $$c_i$$ $$/$$ cost $$a_i$$ for each index $$i$$.

Now, to have the best value $$C$$ for a limited cost $$A$$, you just need to greedy select the $$i$$ from the largest ratio $$w_i$$ and "fill your Knapsack" (by increasing continuously $$x_i$$) until some boundary is filled:

• If $$x_i\le1$$ is reached (you have exhausted all available $$x_i$$), than proceed to the next best $$w_i$$.
• If total boundary $$B$$ is reached, than you've finished the algorithm and that's a guaranteed best solution.
• Yes, exactly. I forgot to mention that the problem has lower and upper bound constraints for solution x. I've updated it above. Aug 20 at 0:16
• So now you got the Knapsack Problem. I've updated the answer to cover that! ;) Aug 20 at 3:09
• Thank you for your answer, Andre. This problem can be solved easily by using the Knapsack algorithm. But I'm a new learner with Reinforcement Learning and just trying to solve this problem with RL. Aug 21 at 14:50