4 ms·

I think this can be applied to much the same domains as simplex or similar algorithms. So optimization problems/OR. See https://en.wikipedia.org/wiki/Operation

• dragontamer 4y ago
  Constraint Programming is NP-complete (non-polynomial bounds, likely exponential complexity). Simplex is provably within the polynomial bounds of complexity, ie: simplex is a so called "easy" problem in complexity theory. -------- You're right that simplex is applied to optimization problems. Constraint programming could be seen as a "more generic" optimizer, in that it can handle integer-optimization (simplex cannot handle integer optimization at all). Of course, integer-optimization is NP complete, which means that constraint programming is innately "inefficient" or "hard" in terms of complexity.
  • aaplok 4y ago
    Not quite. Simplex is an algorithm to solve linear programming problems. Linear programming is (weakly) polynomial. The simplex algorithm itself has exponential worst case [0]. Whether there exist a polynomial-time variant of the simplex algorithm is an open problem. Constraint programming is very broad — it encompasses many types of problems. Some of them are in P, some (most?) are in NP. In principle you can use the simplex algorithm for solving certain constraint programming problems, but mostly when people talk about constraint programming they refer to different techniques. [0] https://en.wikipedia.org/wiki/Klee%E2%80%93Minty_cube https://en.wikipedia.org/wiki/Klee%E2%80%93Minty_cube