Stack Overflow
Stack Overflow

Questions tagged [constraint-programming]

A constraint network is defined by a triplet , where X is a set of variables, C is a set of constraints, and D a domain for X (i.e. a mapping from variables to sets of values). The constraint satisfaction problem (CSP) is the question of deciding whether a constraint network has a solution or not.

Constraint programming is a form of declarative programming. Constraints specify the desired properties of a solution, not a sequence of steps to execute.

A constraint satisfaction problem (CSP) is defined by a triplet <X,C,D>, where X is a set of variables, C is a set of constraints, and D a domain for X (i.e. a mapping from variables to sets of values). A CSP is called consistent if it has a solution.

Constraint programming blends in naturally with logic programming, since logic programming can in fact be regarded as a special form of constraint programming, where the domain is the set of Herbrand terms. When constraint programming is hosted by a logic programming language, it is called constraint logic programming and abbreviated as CLP.

The notion CLP(X) is used to refer to constraint logic programming over the domain X. The following instances are of particular relevance:

  • CLP(FD): reasoning over integers (see )
  • CLP(B): reasoning over Boolean variables (see )
  • CLP(Q): reasoning over rational numbers (see )
  • CLP(R): reasoning over real numbers or an approximation (see ).

All widely used Prolog systems (see ) ship with several constraint solvers, which are available either as built-in predicates or provided by libraries.

More information:

https://en.wikipedia.org/wiki/Constraint_programming

763 questions
129
votes
15 answers

Solving "Who owns the Zebra" programmatically?

Edit: this puzzle is also known as "Einstein's Riddle" The Who owns the Zebra (you can try the online version here) is an example of a classic set of puzzles and I bet that most people on Stack Overflow can solve it with pen and paper. But what…
activout.se
  • 6,058
  • 4
  • 27
  • 37
45
votes
13 answers

Embedded Prolog Interpreter/Compiler for Java

I'm working on an application in Java, that needs to do some complex logic rule deductions as part of its functionality. I'd like to code my logic deductions in Prolog or some other logic/constraint programming language, instead of Java, as I…
Sami
  • 3,263
  • 3
  • 29
  • 37
42
votes
1 answer

Using the "Prolog in Scala" to find available type class instances

Considering https://speakerdeck.com/folone/theres-a-prolog-in-your-scala, I would like to "abuse" the Scala type system to find all instances of e.g. CanBuildFrom that match a given criteria. Prolog style, I would evaluate something in the lines of…
Erik Kaplun
  • 37,128
  • 15
  • 99
  • 111
39
votes
9 answers

Getting started with Constraint Programming

Looking for tips, tutorials, books and other resources to get started with Constraint Programming.
Larsenal
  • 49,878
  • 43
  • 152
  • 220
35
votes
2 answers

Recursion: how to avoid Python set changed set during iteration RuntimeError

Background and Problem Description: I have some code that solves the graph coloring problem (broadly defined as the problem of assigning "colors" to an undirected graph, making sure that no two vertices connected by an edge have the same color). I'm…
rookie
  • 2,783
  • 5
  • 29
  • 43
30
votes
4 answers

Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction)

Problem statement We have one employer that wants to interview N people, and therefore makes N interview slots. Every person has a free-busy schedule for those slots. Give an algorithm that schedules the N people into N slots if possible, and return…
DarthShader
  • 807
  • 1
  • 7
  • 12
19
votes
3 answers

Finding all the combinations of free polyominoes within a specific area with a SAT-solver (Python)

I am new to the world of SAT solvers and would need some guidance regarding the following problem. Considering that: ❶ I have a selection of 14 adjacent cells in a 4*4 grid ❷ I have 5 polyominoes (A, B, C, D, E) of sizes 4, 2, 5, 2 and 1 ❸ these…
solub
  • 1,291
  • 17
  • 40
17
votes
4 answers

Is Erlang a Constraint-Logic programming language?

Since Erlang is based upon Prolog, does this mean that Erlang is a Constraint-Logic Language? Does Erlang have Prolog's building blocks: Facts, Rules and Query
Chiron
  • 20,081
  • 17
  • 81
  • 133
17
votes
3 answers

Difference LP/MIP and CP

what is the difference between Constraint Programming (CP) and Linear Programming (LP) or Mixed Integer Programming (MIP) ? I know what LP and MIP is but dont understand the difference to CP - or is CP just the same as MIP and LP ? I am a but…
Yellown
  • 426
  • 2
  • 6
  • 16
17
votes
5 answers

Programming for Young tableaux

A strange question follows: I'm doing a problem solving competition @ my school, and they allow us to use a computer. Since I'm the only one in the competition who knows how to code, I use C and Pascal programs to solve problems faster. I've done…
user2179983
  • 201
  • 2
  • 5
15
votes
1 answer

Can anyone suggest a good constraint library for Haskell?

I've started learning about Constraint programming and I feel it is something that would work well with Haskell (also I enjoy using Haskell). Are there any mature constraint frameworks for Haskell?
Magnus
  • 1,222
  • 1
  • 12
  • 25
12
votes
1 answer

Which solver do Googles OR-Tools Modules for CSP and VRP use?

I am currently evaluating googles or-tools and just noticed that it's not really a solver on its own but mainly an interface to other solvers. What I'd like to know is which solvers this framework uses for constraint and routing problems. I have…
javaguy
  • 149
  • 1
  • 6
12
votes
1 answer

Any pseudo-polynomial algorithm for bounded 0-1 multi-knapsack?

Suppose that there are n items, e.g i1, i2, .... in, each of them with a known bounded weight w1, w2, ... wn. There are also a set of m knapsacks e.g. k1, k2 and km. Knapsacks are homogeneous, that they all have the same capacity W. The function F…
TonySalimi
  • 8,257
  • 4
  • 33
  • 62
11
votes
3 answers

Optimizing pathfinding in Constraint Logic Programming with Prolog

I am working on a small prolog application to solve the Skyscrapers and Fences puzzle. An unsolved puzzle: A solved puzzle: When I pass the program already solved puzzles it is quick, almost instantaneous, to validate it for me. When I pass the…
F. P.
  • 5,018
  • 10
  • 55
  • 80
11
votes
3 answers

Ordering lists with constraint logic programming

I was wondering if anyone could help me with this problem: I have to order a list using Prolog with Constraing Logic Programming and I must do it with the more efficient way I can. So the main predicate I have defined is the next one: order(Xs,Ys)…
albertoblaz
  • 590
  • 5
  • 19
1
2 3
…
50 51