Answers.Body: <p>LP is a mathematical problem to optimize a linear function subject to linear (in)equality constraints of the sort:
  <span class="math-container">$$
  min_x  w^t x
  $$</span>
  <span class="math-container">$$
  Ax&lt;b
  $$</span></p>
  
  <p>where <span class="math-container">$x$</span> is a continuous variable (vector). If the problem is feasible, then a unique global optimal solution exists for <span class="math-container">$x$</span></p>
  
  <p>A constraint satisfaction problem on the other hand is just the constraints part of the above LP. So we are not interested in the optimal solution, just a set of values that will satisfy the constraints. If the domain of your variables is continuous, then it can be recast as a dummy LP with a fake objective e.g. <span class="math-container">$min_x 0, s.t. Ax&lt;b$</span>, and then solved with an LP solver (e.g. simplex algorithm)</p>
  
  <p>However many CSPs have discrete variables so they are not LP. Also CSP problems may have too many variables for plain LP algorithms to handle, so there are problem specific shortcut algorithms. We are often happy to find a feasible solution and forget about "optimality"</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-09T19:44:37.720Z
Answers.Text: @PrabhDhali If think this answer is useful, you should upvote it by clicking on the arrow pointing upwards. And, if you think this answer answers your question, you should accept it by clicking on the check mark.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-09T12:52:56.937Z
Answers.LastActivityDate: 2020-06-09T12:52:56.937Z
Answers.UserDisplayName: nikos
Body: <p>I have taken an algorithms course where we talked about LP significantly, and also many reductions to LPs. As I recall, normal LP is not NP-Hard. Integer LP is NP-Hard. I am currently taking an introduction to AI course, and I was wondering if CSP is the same as LP. </p>
  
  <p>There seems an awful lot of overlap, and I haven't been able to find anything that confirms or denies my suspicions. </p>
  
  <p>If they are not the same (or one cannot be reduced to the other), what are the core differences in their concepts?</p>
  
Tags: <comparison><constraint-satisfaction-problems><linear-programming>
Title: What are the differences between constraint satisfaction problems and linear programming?
UserDisplayName: Prabh Dhali
ThreadText: # What are the differences between constraint satisfaction problems and linear programming?
  
  (Asked by: username_0 on 2020-06-09)
  
  I have taken an algorithms course where we talked about LP significantly, and also many reductions to LPs. As I recall, normal LP is not NP-Hard. Integer LP is NP-Hard. I am currently taking an introduction to AI course, and I was wondering if CSP is the same as LP.
  
  There seems an awful lot of overlap, and I haven't been able to find anything that confirms or denies my suspicions.
  
  If they are not the same (or one cannot be reduced to the other), what are the core differences in their concepts?
  
  **Tags:** comparison, constraint-satisfaction-problems, linear-programming
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-06-09. Score: 3
  
  LP is a mathematical problem to optimize a linear function subject to linear (in)equality constraints of the sort:
  $$
  min\_x w^t x
  $$
  $$
  Ax<b
  $$
  
  where $x$ is a continuous variable (vector). If the problem is feasible, then a unique global optimal solution exists for $x$
  
  A constraint satisfaction problem on the other hand is just the constraints part of the above LP. So we are not interested in the optimal solution, just a set of values that will satisfy the constraints. If the domain of your variables is continuous, then it can be recast as a dummy LP with a fake objective e.g. $min\_x 0, s.t. Ax<b$, and then solved with an LP solver (e.g. simplex algorithm)
  
  However many CSPs have discrete variables so they are not LP. Also CSP problems may have too many variables for plain LP algorithms to handle, so there are problem specific shortcut algorithms. We are often happy to find a feasible solution and forget about "optimality"
  
  > **Comments:**
  > **username_2**: @username_0 If think this answer is useful, you should upvote it by clicking on the arrow pointing upwards. And, if you think this answer answers your question, you should accept it by clicking on the check mark.  
  
  ---
  
  