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?

  • 3
    $\begingroup$ How are you changing a linear programming problem into a markov decision problem? What are the state, actions, and rewards? $\endgroup$
    – Taw
    Aug 19, 2021 at 13:03
  • $\begingroup$ 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? $\endgroup$ Aug 19, 2021 at 16:07

1 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.
  • $\begingroup$ Yes, exactly. I forgot to mention that the problem has lower and upper bound constraints for solution x. I've updated it above. $\endgroup$ Aug 20, 2021 at 0:16
  • $\begingroup$ So now you got the Knapsack Problem. I've updated the answer to cover that! ;) $\endgroup$ Aug 20, 2021 at 3:09
  • $\begingroup$ 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. $\endgroup$ Aug 21, 2021 at 14:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .