3 ms·

I feel like this is something I may understand the solution to but the problem it solves leaves me dumbfounded. Any recommendations on a "this but for dribblin

by Jenk 4y ago

I feel like this is something I may understand the solution to but the problem it solves leaves me dumbfounded. Any recommendations on a "this but for dribbling primates" introduction?

hosteur 4y ago
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/Operations_research https://en.wikipedia.org/wiki/Operations_research
- 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
dragontamer 4y ago
Constraint Programming is "on the same complexity" as any of your NP-completeness set of problems. IE: Knapsack problem, Traveling Salesman, etc. etc. Today, it seems more popular to use "3-SAT Solvers". But constraint programming is "more logical" for some problems to get converted into rather than 3-SAT. Consider 3-SAT and Constraint Programming to be two different "assembly languages" that you can compile your problem into, and then have a generic solver into. ----------- For example: Sudoku can be "compiled" into the 3SAT problem: https://www.mit.edu/~6.005/sp12/psets/ps2/ps2.html https://www.mit.edu/~6.005/sp12/psets/ps2/ps2.html But it also can be "compiled" into the Constraint-problem, which then gets solved by a constraint solver. https://sonalake.com/latest/constraint-programming-solving-sudoku-with-choco-solver-library/ https://sonalake.com/latest/constraint-programming-solving-s... ------------ Personally speaking, I think that the constraint solver problem is "easier to compile into" rather than the 3SAT problem, especially when you consider generic constraints that have very efficient solutions. For example, it is difficult to think of the optimal alldifferent constraint within 3SAT, but in a constraint-solver framework, its just... well... alldifferent. So you can describe Sudoku as the following: Domain = {1 2 3 4 5 6 7 8 9} Alldifferent(X11, X12, X13, X14, X15, X16, X17, X18, X19) Alldifferent(X21, X22, X23, X24, X25, X26, X27, X28, X29) Alldifferent(X31, X32, X33, X34, X35, X36, X37, X38, X39) ... Alldifferent(X91, X92, X93, X94, X95, X96, X97, X98, X99) ------------------------------------------------------------------------ Alldifferent(X11, X21, X31, X41, X51, X61, X71, X81, X91) Alldifferent(X12, X22, X32, X42, X52, X62, X72, X82, X92) Alldifferent(X13, X23, X33, X43, X53, X63, X73, X83, X93) ... Alldifferent(X19, X29, X39, X49, X59, X69, X79, X89, X99) ------------------------------------------------------------------------ Alldifferent(X11, X12, X13, X21, X22, X23, X31, X32, X33) ... Alldifferent(X77, X78, X79, X87, X88, X89, X97, X98, X99) That is: numbers are 1 through 9, and constrain the problem such that each row is alldifferent, and each column is all different, and each "3x3 square" is all different. ---------- IIRC, the Alldifferent constraint can be efficiently solved using maximum flow. So you write a specialized solver for alldifferent using maximum flow (faster than 3SAT / NP Completeness), and this maximum-flow local solution can be "plugged into" the rest of the constraint solver problem, and integrates cleanly with the rest of the solver's NP-completeness search.
- sacado2 4y ago

by Jenk 4y ago

I feel like this is something I may understand the solution to but the problem it solves leaves me dumbfounded. Any recommendations on a "this but for dribbling primates" introduction?

hosteur 4y ago

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/Operations_research https://en.wikipedia.org/wiki/Operations_research

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

dragontamer 4y ago

Constraint Programming is "on the same complexity" as any of your NP-completeness set of problems. IE: Knapsack problem, Traveling Salesman, etc. etc. Today, it seems more popular to use "3-SAT Solvers". But constraint programming is "more logical" for some problems to get converted into rather than 3-SAT. Consider 3-SAT and Constraint Programming to be two different "assembly languages" that you can compile your problem into, and then have a generic solver into. ----------- For example: Sudoku can be "compiled" into the 3SAT problem: https://www.mit.edu/~6.005/sp12/psets/ps2/ps2.html https://www.mit.edu/~6.005/sp12/psets/ps2/ps2.html But it also can be "compiled" into the Constraint-problem, which then gets solved by a constraint solver. https://sonalake.com/latest/constraint-programming-solving-sudoku-with-choco-solver-library/ https://sonalake.com/latest/constraint-programming-solving-s... ------------ Personally speaking, I think that the constraint solver problem is "easier to compile into" rather than the 3SAT problem, especially when you consider generic constraints that have very efficient solutions. For example, it is difficult to think of the optimal alldifferent constraint within 3SAT, but in a constraint-solver framework, its just... well... alldifferent. So you can describe Sudoku as the following: Domain = {1 2 3 4 5 6 7 8 9} Alldifferent(X11, X12, X13, X14, X15, X16, X17, X18, X19) Alldifferent(X21, X22, X23, X24, X25, X26, X27, X28, X29) Alldifferent(X31, X32, X33, X34, X35, X36, X37, X38, X39) ... Alldifferent(X91, X92, X93, X94, X95, X96, X97, X98, X99) ------------------------------------------------------------------------ Alldifferent(X11, X21, X31, X41, X51, X61, X71, X81, X91) Alldifferent(X12, X22, X32, X42, X52, X62, X72, X82, X92) Alldifferent(X13, X23, X33, X43, X53, X63, X73, X83, X93) ... Alldifferent(X19, X29, X39, X49, X59, X69, X79, X89, X99) ------------------------------------------------------------------------ Alldifferent(X11, X12, X13, X21, X22, X23, X31, X32, X33) ... Alldifferent(X77, X78, X79, X87, X88, X89, X97, X98, X99) That is: numbers are 1 through 9, and constrain the problem such that each row is alldifferent, and each column is all different, and each "3x3 square" is all different. ---------- IIRC, the Alldifferent constraint can be efficiently solved using maximum flow. So you write a specialized solver for alldifferent using maximum flow (faster than 3SAT / NP Completeness), and this maximum-flow local solution can be "plugged into" the rest of the constraint solver problem, and integrates cleanly with the rest of the solver's NP-completeness search.

sacado2 4y ago