Answers.Body: <h2>Straight theoretical answer:</h2>
  <p>In theory, yes, it is possible to model this problem as a Reinforcement Learning. But in practice, RL is <strong>not</strong> the most suitable approach for a simple linear maximization with a boundary. For instance, you could use a <a href="https://www.khanacademy.org/math/multivariable-calculus/applications-of-multivariable-derivatives/constrained-optimization/a/lagrange-multipliers-single-constraint" rel="nofollow noreferrer">Lagrangian</a>.</p>
  <hr />
  <h3>Practical analysis on your specific problem</h3>
  <p>In this specific example, you have 1 single constrain: <span class="math-container">$\sum_{i} a_i x_i \le b$</span>, for an <span class="math-container">$n$</span> degree equation (n = size of <span class="math-container">$X$</span>).
  So you might also want to add another boundary, like: all <span class="math-container">$X &gt; 0$</span>. <strong>Otherwise your solution will diverge:</strong></p>
  <ul>
  <li><span class="math-container">$C = [1 2 3 4];$</span></li>
  <li><span class="math-container">$X = [x_1; x_2; x_3; x_4];$</span></li>
  <li><span class="math-container">$A = [2 3 4 5];$</span></li>
  <li><span class="math-container">$b = 10$</span></li>
  </ul>
  <p>Simple example of divergent solution:</p>
  <p><span class="math-container">$X = lim_{k=\infty} [-3k, 0,0, k]$</span></p>
  <p>Gives you: <span class="math-container">$C*X= -3k + 0+0+4k = k$</span> ✅ Maximum possible reward for <span class="math-container">$lim_{k=\infty}$</span></p>
  <p>Constrained by <span class="math-container">$A*X = -6k + 0 + 0 +5k = -k \le 10$</span> ✅ Minimum possible boundary for <span class="math-container">$lim_{k=\infty}$</span></p>
  <hr />
  <p><em><strong>Edit after adding <span class="math-container">$x_i \in [0,1] $</span> constraints:</strong></em></p>
  <h3>You have described the simplest version of <a href="https://en.wikipedia.org/wiki/Knapsack_problem" rel="nofollow noreferrer">Knapsack Problem</a>, where we can split items in fractions.</h3>
  <p>For this problem, the greedy solution is very simple and effective:</p>
  <p>Calculate a new weight vector: <span class="math-container">$W = C/A = [ c_1 / a_1, c_2/a_2, ... ]$</span>, which represents the ratio of value <span class="math-container">$c_i$</span> <span class="math-container">$/$</span> cost <span class="math-container">$a_i$</span> for each index <span class="math-container">$i$</span>.</p>
  <p>Now, to have the best value <span class="math-container">$C$</span> for a limited cost <span class="math-container">$A$</span>, you just need to greedy select the <span class="math-container">$i$</span> from the largest ratio <span class="math-container">$w_i$</span> and &quot;fill your Knapsack&quot; (by increasing continuously <span class="math-container">$x_i$</span>) until some boundary is filled:</p>
  <ul>
  <li>If <span class="math-container">$x_i\le1$</span> is reached (you have exhausted all available <span class="math-container">$x_i$</span>), than proceed to the next best <span class="math-container">$w_i$</span>.</li>
  <li>If total boundary <span class="math-container">$B$</span> is reached, than you've finished the algorithm and that's a guaranteed best solution.</li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-20T00:16:57.347Z
Answers.Text: Yes, exactly. I forgot to mention that the problem has lower and upper bound constraints for solution x. I've updated it above.
Answers.UserDisplayName: Avarash Goel
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-20T03:09:40.300Z
Answers.Text: So now you got the Knapsack Problem. I've updated the answer to cover that! ;)
Answers.UserDisplayName: Andre Goulart
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-21T14:50:58.707Z
Answers.Text: 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.
Answers.UserDisplayName: Avarash Goel
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-19T19:07:26.347Z
Answers.LastActivityDate: 2021-08-20T03:08:40.180Z
Answers.LastEditDate: 2021-08-20T03:08:40.180Z
Answers.UserDisplayName: Andre Goulart
Body: <p>I'm trying to solve a linear programming problem using reinforcement learning.
  The linear programming problem is:</p>
  <p><span class="math-container">\begin{array}{ll}
  \text{maximize}_x  &amp; C* x \\
  \text{subject to}&amp; A*x \le b\\
                   &amp; x_i \in [0,1],\ where \ i=1,2,3,...
  \end{array}</span></p>
  <p>For instance:
  <span class="math-container">\begin{array}{ll}
  C &amp;=  [1 \; 2 \;3  \;4]\\
  x &amp;=  [x1; x2; x3; x4]\\
  A &amp;=  [2 \;3 \;4 \;5]\\
  b &amp;= 10\\
  \end{array}</span></p>
  <p>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?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-08-19T13:03:04.943Z
Comments.Text: How are you changing a linear programming problem into a markov decision problem? What are the state, actions, and rewards?
Comments.UserDisplayName: Taw
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-08-19T16:07:07.247Z
Comments.Text: 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?
Comments.UserDisplayName: Avarash Goel
Tags: <machine-learning><reinforcement-learning><ddpg><linear-programming>
Title: Is it possible to solve a linear programming problem using reinforcement learning? (DDPG algorithm)
UserDisplayName: Avarash Goel
ThreadText: # Is it possible to solve a linear programming problem using reinforcement learning? (DDPG algorithm)
  
  (Asked by: username_0 on 2021-08-19)
  
  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?
  
  **Tags:** machine-learning, reinforcement-learning, ddpg, linear-programming
  
  > **Comments:**
  > **username_1**: How are you changing a linear programming problem into a markov decision problem? What are the state, actions, and rewards?  
  > **username_0**: 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?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-08-19. Score: 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](https://www.khanacademy.org/math/multivariable-calculus/applications-of-multivariable-derivatives/constrained-optimization/a/lagrange-multipliers-single-constraint).
  
  ---
  
  ### 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](https://en.wikipedia.org/wiki/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.
  
  > **Comments:**
  > **username_0**: Yes, exactly. I forgot to mention that the problem has lower and upper bound constraints for solution x. I've updated it above.  
  > **username_2**: So now you got the Knapsack Problem. I've updated the answer to cover that! ;)  
  > **username_0**: Thank you for your answer, username_2. 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.  
  
  ---
  
  