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

Question

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?

Answer 1

Straight theoretical answer:

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.