3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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"

$\endgroup$
2
  • $\begingroup$ Thank you, this was very helpful! $\endgroup$ Jun 10 '20 at 18:23
  • $\begingroup$ @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. $\endgroup$
    – nbro
    Jul 9 '20 at 19:44

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.