5 ms·

I second this. Prolog is extremely well suited for combinatorial optimization, and combinatorial tasks in general. There is also significant overlap between con

by zmonx 9y ago

I second this. Prolog is extremely well suited for combinatorial optimization, and combinatorial tasks in general. There is also significant overlap between constraint programming and integer programming: Many tasks can be easily solved with both approaches or a combination of them, and sometimes one of them is more suitable. Several Prolog systems ship with great implementations of both approaches.

JadeNB 9y ago
> Prolog is extremely well suited for combinatorial optimization, and combinatorial tasks in general. I believe that it can be well suited for such problems—that is, that it is possible to write good solutions to them [0]—but isn't someone diving in without much experience likely just to write solutions that are age-of-universe slow because of combinatorial explosion? [0] I don't know if it's available online anywhere, but Richard O'Keefe's "The craft of Prolog" (well worth reading for anyone interested in problem solving, programmer or not) has a gorgeous explanation of how to solve the problem "find a 9-digit number such that the `n`-digit initial [or maybe final?] segment is divisible by `n` for each `n` from 1 to 9", starting with the most naïve approach and progressing to a much more efficient one. It has a punchline that, for the benefit of anyone who hasn't read it, I won't spoil here.
- zmonx 9y ago
  The trick for achieving efficient Prolog solutions of such tasks is to use the Prolog system's built-in features for constraint logic programming, abbreviated as CLP. Constraints automatically prune those parts of the search space that do not contain solutions. This typically leads to extremely significant speedups over naively generating all possibilities. For example, integer constraints are available under the name "constraint logic programming over finite domains", abbreviated as CLP(FD), in all most widely used Prolog implementations. To solve combinatorial optimization tasks with Prolog, I recommend to start with CLP(FD). If necesseary, you can always combine it with other approaches, such as applying the simplex algorithm and also custom methods and heuristics. Please note that constraints have become widely available in Prolog systems only after the book you cite was published, and it does not mention these methods at all. With current systems, you can elegantly and efficiently solve the task using CLP(FD) constraints.
- zmonx 9y ago
  For example, here is a Prolog version that describes the task you mention via constraints on integers: solution(Ds) :- length(Ds, 9), Ds ins 0..9, foldl(segment_divisible(Ds), Ds, 1, _). segment_divisible(Ds, _, I0, I) :- I #= I0 + 1, length(Finals, I0), append(_, Finals, Ds), reverse(Finals, RFs), foldl(digits_number, RFs, 0-0, N-_), N #= I0*_. digits_number(D, I0-P0, I-P) :- I #= I0 + D*10^P0, P #= P0 + 1. We can use it to generate solutions, for example: ?- solution(Ds), label(Ds). Ds = [0, 0, 0, 0, 0, 0, 0, 0, 0] ; Ds = [0, 0, 0, 0, 1, 2, 6, 0, 0] ; Ds = [0, 0, 0, 0, 1, 5, 1, 2, 0] ; Ds = [0, 0, 0, 0, 2, 7, 7, 2, 0] . To exclude solutions where the leftmost digit is 0, we can simply impose an additional constraint on that digit. In addition, we are free to try different search strategies, completely decoupled from the constraints: ?- solution(Ds), Ds = [First|_], First #\= 0, reverse(Ds, Rs), label(Rs), portray_clause(Ds), false. [9, 0, 0, 0, 0, 0, 0, 0, 0]. [8, 1, 0, 0, 0, 0, 0, 0, 0]. [7, 2, 0, 0, 0, 0, 0, 0, 0]. [6, 3, 0, 0, 0, 0, 0, 0, 0]. [5, 4, 0, 0, 0, 0, 0, 0, 0]. [4, 5, 0, 0, 0, 0, 0, 0, 0]. etc. Constraints allow us to easily describe and efficiently such tasks. Note that this is very different from naive exhaustive search: The constraint solver automatically prunes those branches of the search space that cannot lead to a solution.
  - JadeNB 9y ago
    Thanks! I forgot a constraint: we must use exactly the digits 1 through 9 (of course, each once). I assume that could easily be incorporated?
    - zmonx 9y ago
      Yes, this is easy to add, since there is a dedicated constraint called all_distinct/1 that we can use to express that a set of integers be pairwise distinct. In this concrete case, we get this by simply adding all_distinct(Ds) to the query. For example: ?- solution(Ds), all_distinct(Ds), reverse(Ds, Rs), label(Rs). This yields Ds = [6, 5, 4, 8, 7, 3, 1, 2, 0], in addition to other solutions. Now we only need to add that none of the integers must be 0. We can express this (for example) with the additional constraint Ds ins 1..9: ?- solution(Ds), Ds ins 1..9, all_distinct(Ds), reverse(Ds, Rs), label(Rs). However, when you run this query, you get false in return. This means that there is no solution that satisfies all these constraints at the same time. Therefore, the task you mentioned was probably about the prefices, i.e., the initial segments of the number. We can easily express this with small modifications to the program above: solution(Ds) :- length(Ds, 9), Ds ins 1..9, all_distinct(Ds), foldl(segment_divisible(Ds), Ds, 1, _). segment_divisible(Ds, _, I0, I) :- I #= I0 + 1, length(Prefix, I0), append(Prefix, _, Ds), reverse(Prefix, RPs), foldl(digits_number, RPs, 0-0, N-_), N #= I0*_. digits_number(D, I0-P0, I-P) :- I #= I0 + D*10^P0, P #= P0 + 1. With this program, we get: ?- solution(Ds), label(Ds). Ds = [3, 8, 1, 6, 5, 4, 7, 2, 9] ; false. This means that there is a solution, and it is in fact unique! This is determined very efficiently thanks to the pruning that is automatically applied by the constraint solver.
bitL 9y ago
Prolog is well suited for small (toy) combinatorial optimization, useless in practice. It's no wonder the whole 5GL idea tanked mainly because Prolog just couldn't deliver. Yes, I had fun with SWI Prolog and 2nd order abstractions, but in no way I am going to use it on large problems, though I might implement pieces of Warren's Abstract Machine when I see fit.
- zmonx 9y ago
  SWI-Prolog lacks a commercial-grade constraint solver that is sufficiently efficient for the tasks you might have tried. If you are interested in applying constraint solving for very complex combinatorial tasks, consider trying a Prolog system with more efficient constraint solvers which are routinely used in industry. Note that SWI-Prolog is not based on the WAM either.
  - saosebastiao 9y ago
    The only one I know of is sicstus prolog and it hasn't kept up with the state of the art, such as OR-Tools and HaifaCSP, both of which are available from a FlatZinc language interface. Prolog has some benefits in its more declarative nature, but it really constrains you because it forces you to use an entire prolog implementation, when all you really need is an interface to a solver.
    - zmonx 9y ago
      Conversely, what if you really need a Prolog system or indeed any general purpose programming language, but only have an interface to a more limited solver? I find this even more constrained. As technology progresses, interfaces to other solvers that appear from time to time become available in Prolog systems if enough users demand it. For many cases, a Prolog system is already more than sufficient on its own, and is far more flexible than specialized tools which can still be provided as add-ons to Prolog. It is straight-forward to use only a specific subset of Prolog, if that is all you need. In contrast, it is generally impossible to use basic features of Prolog, such as backtracking and logical variables, in more specialized tools and solvers.

by zmonx 9y ago

JadeNB 9y ago

> Prolog is extremely well suited for combinatorial optimization, and combinatorial tasks in general. I believe that it can be well suited for such problems—that is, that it is possible to write good solutions to them [0]—but isn't someone diving in without much experience likely just to write solutions that are age-of-universe slow because of combinatorial explosion? [0] I don't know if it's available online anywhere, but Richard O'Keefe's "The craft of Prolog" (well worth reading for anyone interested in problem solving, programmer or not) has a gorgeous explanation of how to solve the problem "find a 9-digit number such that the `n`-digit initial [or maybe final?] segment is divisible by `n` for each `n` from 1 to 9", starting with the most naïve approach and progressing to a much more efficient one. It has a punchline that, for the benefit of anyone who hasn't read it, I won't spoil here.

zmonx 9y ago
The trick for achieving efficient Prolog solutions of such tasks is to use the Prolog system's built-in features for constraint logic programming, abbreviated as CLP. Constraints automatically prune those parts of the search space that do not contain solutions. This typically leads to extremely significant speedups over naively generating all possibilities. For example, integer constraints are available under the name "constraint logic programming over finite domains", abbreviated as CLP(FD), in all most widely used Prolog implementations. To solve combinatorial optimization tasks with Prolog, I recommend to start with CLP(FD). If necesseary, you can always combine it with other approaches, such as applying the simplex algorithm and also custom methods and heuristics. Please note that constraints have become widely available in Prolog systems only after the book you cite was published, and it does not mention these methods at all. With current systems, you can elegantly and efficiently solve the task using CLP(FD) constraints.
zmonx 9y ago
For example, here is a Prolog version that describes the task you mention via constraints on integers: solution(Ds) :- length(Ds, 9), Ds ins 0..9, foldl(segment_divisible(Ds), Ds, 1, _). segment_divisible(Ds, _, I0, I) :- I #= I0 + 1, length(Finals, I0), append(_, Finals, Ds), reverse(Finals, RFs), foldl(digits_number, RFs, 0-0, N-_), N #= I0*_. digits_number(D, I0-P0, I-P) :- I #= I0 + D*10^P0, P #= P0 + 1. We can use it to generate solutions, for example: ?- solution(Ds), label(Ds). Ds = [0, 0, 0, 0, 0, 0, 0, 0, 0] ; Ds = [0, 0, 0, 0, 1, 2, 6, 0, 0] ; Ds = [0, 0, 0, 0, 1, 5, 1, 2, 0] ; Ds = [0, 0, 0, 0, 2, 7, 7, 2, 0] . To exclude solutions where the leftmost digit is 0, we can simply impose an additional constraint on that digit. In addition, we are free to try different search strategies, completely decoupled from the constraints: ?- solution(Ds), Ds = [First|_], First #\= 0, reverse(Ds, Rs), label(Rs), portray_clause(Ds), false. [9, 0, 0, 0, 0, 0, 0, 0, 0]. [8, 1, 0, 0, 0, 0, 0, 0, 0]. [7, 2, 0, 0, 0, 0, 0, 0, 0]. [6, 3, 0, 0, 0, 0, 0, 0, 0]. [5, 4, 0, 0, 0, 0, 0, 0, 0]. [4, 5, 0, 0, 0, 0, 0, 0, 0]. etc. Constraints allow us to easily describe and efficiently such tasks. Note that this is very different from naive exhaustive search: The constraint solver automatically prunes those branches of the search space that cannot lead to a solution.
- JadeNB 9y ago
  Thanks! I forgot a constraint: we must use exactly the digits 1 through 9 (of course, each once). I assume that could easily be incorporated?
  - zmonx 9y ago
    Yes, this is easy to add, since there is a dedicated constraint called all_distinct/1 that we can use to express that a set of integers be pairwise distinct. In this concrete case, we get this by simply adding all_distinct(Ds) to the query. For example: ?- solution(Ds), all_distinct(Ds), reverse(Ds, Rs), label(Rs). This yields Ds = [6, 5, 4, 8, 7, 3, 1, 2, 0], in addition to other solutions. Now we only need to add that none of the integers must be 0. We can express this (for example) with the additional constraint Ds ins 1..9: ?- solution(Ds), Ds ins 1..9, all_distinct(Ds), reverse(Ds, Rs), label(Rs). However, when you run this query, you get false in return. This means that there is no solution that satisfies all these constraints at the same time. Therefore, the task you mentioned was probably about the prefices, i.e., the initial segments of the number. We can easily express this with small modifications to the program above: solution(Ds) :- length(Ds, 9), Ds ins 1..9, all_distinct(Ds), foldl(segment_divisible(Ds), Ds, 1, _). segment_divisible(Ds, _, I0, I) :- I #= I0 + 1, length(Prefix, I0), append(Prefix, _, Ds), reverse(Prefix, RPs), foldl(digits_number, RPs, 0-0, N-_), N #= I0*_. digits_number(D, I0-P0, I-P) :- I #= I0 + D*10^P0, P #= P0 + 1. With this program, we get: ?- solution(Ds), label(Ds). Ds = [3, 8, 1, 6, 5, 4, 7, 2, 9] ; false. This means that there is a solution, and it is in fact unique! This is determined very efficiently thanks to the pruning that is automatically applied by the constraint solver.

bitL 9y ago

Prolog is well suited for small (toy) combinatorial optimization, useless in practice. It's no wonder the whole 5GL idea tanked mainly because Prolog just couldn't deliver. Yes, I had fun with SWI Prolog and 2nd order abstractions, but in no way I am going to use it on large problems, though I might implement pieces of Warren's Abstract Machine when I see fit.

zmonx 9y ago
SWI-Prolog lacks a commercial-grade constraint solver that is sufficiently efficient for the tasks you might have tried. If you are interested in applying constraint solving for very complex combinatorial tasks, consider trying a Prolog system with more efficient constraint solvers which are routinely used in industry. Note that SWI-Prolog is not based on the WAM either.
- saosebastiao 9y ago
  The only one I know of is sicstus prolog and it hasn't kept up with the state of the art, such as OR-Tools and HaifaCSP, both of which are available from a FlatZinc language interface. Prolog has some benefits in its more declarative nature, but it really constrains you because it forces you to use an entire prolog implementation, when all you really need is an interface to a solver.
  - zmonx 9y ago
    Conversely, what if you really need a Prolog system or indeed any general purpose programming language, but only have an interface to a more limited solver? I find this even more constrained. As technology progresses, interfaces to other solvers that appear from time to time become available in Prolog systems if enough users demand it. For many cases, a Prolog system is already more than sufficient on its own, and is far more flexible than specialized tools which can still be provided as add-ons to Prolog. It is straight-forward to use only a specific subset of Prolog, if that is all you need. In contrast, it is generally impossible to use basic features of Prolog, such as backtracking and logical variables, in more specialized tools and solvers.