0
$\begingroup$

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?

$\endgroup$
2
  • 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 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 at 16:07
1
$\begingroup$

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.
$\endgroup$
3
  • $\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 at 0:16
  • $\begingroup$ So now you got the Knapsack Problem. I've updated the answer to cover that! ;) $\endgroup$ Aug 20 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 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.