What is Constraint: Definition and 184 Discussions

Constraint programming (CP) is a paradigm for solving combinatorial problems that draws on a wide range of techniques from artificial intelligence, computer science, and operations research. In constraint programming, users declaratively state the constraints on the feasible solutions for a set of decision variables. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties of a solution to be found. In addition to constraints, users also need to specify a method to solve these constraints. This typically draws upon standard methods like chronological backtracking and constraint propagation, but may use customized code like a problem specific branching heuristic.
Constraint programming takes its root from and can be expressed in the form of constraint logic programming, which embeds constraints into a logic program. This variant of logic programming is due to Jaffar and Lassez, who extended in 1987 a specific class of constraints that were introduced in Prolog II. The first implementations of constraint logic programming were Prolog III, CLP(R), and CHIP.
Instead of logic programming, constraints can be mixed with functional programming, term rewriting, and imperative languages.
Programming languages with built-in support for constraints include Oz (functional programming) and Kaleidoscope (imperative programming). Mostly, constraints are implemented in imperative languages via constraint solving toolkits, which are separate libraries for an existing imperative language.

View More On Wikipedia.org
Recent contents Top users
  1. G

    Derivative with a range constraint - mystified

    Homework Statement x=sin(a) / cos(b) a+b < pi/2 a>0, b>0 0<x<1 show that da/dx = cos^3(b)cos(a) / cos(a+b)cos(a-b) The Attempt at a Solution dx/da = cos(a) / cos(b) therefore da/dx = cos(b) / cos(a) =cos^3(b)cos(a) / cos^2(b)cos^2(a) However the denominator of the...
  2. N

    Find the extrema of f subject to the stated constraint

    Homework Statement Find the extrema of f subject to the stated constraint: f(x,y) = x-y subject to x2-y2=2Homework Equations Apply the Lagrange Multiplier!The Attempt at a Solution This question was rather odd... I just did a problem similar to this one, and I got the answer right. Let...
  3. H

    How Do You Maximize a Quadratic Form on a Sphere with an Affine Transformation?

    Hi, I search for the maximum of a quadric for points on a sphere. I have an affine transform A (4x4 matrix, in homogeneous coord.) and apply it to points on (and inside) a sphere x \in S_{m,r} \Leftrightarrow (x-m)^2<=r^2 . (Although I think the extremum must be on the surface of the sphere?)...
  4. M

    Lagrange multiplier with inequality and point constraint?

    Find an equation of the largest sphere that passes through the point (-1,1,4) and is such that each of the points (x,y,z) inside the sphere satisfies the condition x^2 + y^2 + z^2 < 136 + 2(x + 2y + 3z) I know this problem requires Lagrange multipliers. I assume that x^2 + y^2 + z^2 is...
  5. W

    The Constraint Based Statistics - Beyond the Entropy Based Statistical Mechanics

    The Constraint Based Statistics --- Beyond the Entropy Based Statistical Mechanics The Constraint Based Statistics --- Beyond Tsallis Entropy and Boltzmann Entropy Based Statistical Mechanics This post is a summary about a brand new work in the field of Nonextensive Statistical Mechanics...
  6. B

    Einstein Vacuum Equation, Vacuum Constraint Equations

    Having a Lorentzian 4-manifold, the Einstein vacuum equations of general relativity read \overline R_{\alpha \beta} - \frac{1}{2}\overline g_{\alpha\beta}\overline R=0 where \overline R the scalar curvature, \overline g_{\alpha\beta} the metric tensor and \overline R_{\alpha\beta} the Ricci...
  7. W

    How do I setup an equation for the acceleration constraint?

    Homework Statement The Attempt at a Solution Could someone explain how to setup an equation for position so that I can find an acceleration constraint?
  8. E

    Master Constraint and canonical LQG

    So Thieman and co are still working on the Master Constraint program for canonical, non-SF, LQG? I thought that approach was dead and given way to SF ala Rovelli
  9. O

    States counting of many particales under a constraint

    Let’s say i have n identical classical non interacting particles and N sites where i can put them in. BUT the total energy is given. The number of possible states is (N)^n/n!/(n/2)! Where N^n is the total possibilities to arrange the particles. We divide it by n! since they are identical...
  10. N

    Constraint equation for a solid disk

    Homework Statement I'm wondering how to write the equation of constraint for a solid disk (mass m, radius R) that is attached to a spring (spring constant k) and rolls without slipping. Any suggestions? Homework Equations there are no equations to use, but this has to do with lagrange's...
  11. J

    Analysis of beam bending against constraint

    I have been trying to analyze the deflection of the free end of a cantilevered beam with a point load P at the end. The trick is, the beam is supported underneath by a surface described by the arbitrary function g(x). So let's say that g(x)= 0.001*x^2, a very shallow parabola. As the beam...
  12. R

    Constraint Relations Homework: Acceleration of Block

    Homework Statement http://img510.imageshack.us/img510/5505/systemet4.jpg What I wish to do is to relate the accelerations of the loop an the massive block. I know the angle theta at any instant. I also know that the acceleration of the loop on the fixed support is a. I have been given no...
  13. A

    Lagrangian for a rheonomic constraint?

    How does a Lagrangian change for a system with a rheonomic constraint? As far as I can see in the derivations, it shouldn't seem to matter, but I just want to make sure. And if I have a rheonomic constraint, what should I do with the time? Should I just ignore it and use the Euler-Lagrange...
  14. R

    Constraint Relations: Acclerations of Blocks in System

    The system is given in the picture. I want to know the relation between the acclerations of each block. My attempt: suppose if the body in the middle moves up by x. the string will get loose by 2x. therefore, if a1, a2, a3 are the acclerations. -2*a2=a1+a3 am i correct?
  15. B

    Maximise the following expression subject to the constraint

    Hi guys, I wish to maximise the following expression subject to the constraint that \|\underline{w}\| = 1, and \mathbb{R} is fixed. P = \underline{w}^H \mathbb{G}^H\mathbb{G}\underline{w} = \underline{w}^H \mathbb{R} \underline{w} where \mathbb{R} \triangleq...
  16. P

    Constraint Forces: Definition & Necessity

    the fundamental basis of the lagrangian formulation is the fact that the virtual displacement are perpendicular to the constraint forces so how does one define constraint forces? is it necessary for the virtual displacement consistent with the given constraints be perpendicular to the...
  17. I

    Constraint Equation? Multivariate calculus

    Homework Statement This is a second (university) year calculus problem dealing with calculus of multiple variables. In economics, utility is a measure of the relative satisfaction from, or desirability of, consumption of goods. A utility function u = u(a,b) gives the utility from consuming...
  18. O

    Maximization subject equality constraint

    Homework Statement Max f = x²yz³ sub. 50x+10y+100z = 1000 Homework Equations Using Lagrange: L = x²yz³ - λ ( 50x + 10 y + 100z - 1000 ) Lx = 2xyz³ - λ50 = 0 Ly = x²z³ - λ10 = 0 Lz = 3x²yz² - λ100 = 0 i found z = 2,5 x= 10 y=25, what's wrong? The Attempt at a...
  19. V

    Lagrange-multiplier constraint for collinear beads in 3d?

    Homework Statement I'm trying to write a Lagrange-multiplier constraint simulation along the lines of those described by Andrew Witkin here. The basic idea for this simulation is that you have a number of objects represented by three collinear beads joined by massless rods; one of the...
  20. O

    Optimization inequality constraint

    Homework Statement Minimize 2x²+2y²-2xy-9y subject 4x + 3y =,< 10 , y - 4x² =,< -2 x >,= 0 and y >,= 0. I don't undersant this: "This equation has no nonnegative root, which contradicts a nonnegativity constraint." and how we solve -16x² + 2x + 17 + h2 = 0
  21. D

    Multivariate Linear Regression With Coefficient Constraint

    [SOLVED] Multivariate Linear Regression With Coefficient Constraint I'm attempting a multivariate linear regression (mvlr) by method of least squares. Basically, I'm solving a matrix of the following form for \beta_p, $ \begin{bmatrix} \sum y \\ \sum x_1 y \\ \sum x_2 y \\ \sum x_3 y...
  22. P

    Least fuel consumed from point A to B with no time constraint

    Let's assume we have a generic, standard design ICE car, except that transmission is CVT (continously variable) and can be popped into neutral, since this simplifies the problem. Assume car travels in a hypothetically-empty freeway at any speed and also assume that driver is optimizing fuel...
  23. S

    Gr-qc/921001 - the constraint algebra of general relativity

    Hi. I'm trying to work my way through Chris Isham's "Canonical Quantum Gravity and the Problem of Time", gr-qc/921001. However, I've gotten a bit stumped by the constraint algebra of general relativity. By "stumped" I don't mean that I can't understand the reasoning behind the constraint...
  24. S

    Gr-qc/921001 - the constraint algebra of general relativity

    Hi. I'm trying to work my way through Chris Isham's "Canonical Quantum Gravity and the Problem of Time", gr-qc/921001. However, I've gotten a bit stumped by the constraint algebra of general relativity. By "stumped" I don't mean that I can't understand the reasoning behind the constraint...
  25. S

    Gr-qc/921001 - the constraint algebra of general relativity

    Hi. I'm trying to work my way through Chris Isham's "Canonical Quantum Gravity and the Problem of Time", gr-qc/921001. However, I've gotten a bit stumped by the constraint algebra of general relativity. By "stumped" I don't mean that I can't understand the reasoning behind the constraint...
  26. G

    How to get the constraint equation of this problem

    A particle moves in the xy plane under the constraint that its velocity vector is always directed towards a point on the x-axis whose abscissa is some given function of time f(t). Show that for f(t) differentiable, but otherwise arbitrary, the constraint is nonholonomic...
  27. P

    Working out a Second Class Constraint in Gory detail?

    Hello, I've been fooling around with some equations, and I've managed to land a second class constraint (I don't know whether to laugh or cry). Well, I was wondering is there any good introduction to the subject? The problem I have is that I made the conjugate momentum a function of...
  28. Reshma

    Understanding Non-Holonomic Constraints for Particle Motion

    A particle moves in the x-y plane under the constraint that its velocity is always directed towards a point on the x-axis whose absicissa is some given function of time f(t). Show that for f(t) differentiable, but otherwise arbitrary, the constraint is non-holonomic. All I could infer from...
  29. T

    3 by 3 matrix with an orthogonality constraint

    This is a paragraph from a book, which I don't understand: "How many independent parameters are there in a 3x3 matrix? A real 3x3 matrix has 9 entries but if we have the orthogonality constraint, RR^T = 1 which corresponds to 6 independent equations because the product RR^T being the same...
  30. S

    Another Constraint on Quantum Gravity

    This paper by Mohammed Ansari and Lee Smolin, http://arxiv.org/abs/hep-th/0412307, seems to have been overlooked here. The authors argue that for any quantum theory of gravity (they mention LQG and causal triangulations) to produce macroscopic physics - which would be necessary for it to have...
  31. S

    Solving constraint equations [Term Paper, HELP ]

    Solving constraint equations [Term Paper, HELP please] Hi, I am new here. I'm not sure if this fits in calculus&analysis forum, but i figured its not really simple math so, please move it into approprieate area if deemed necessary... I am doing materials selection analysis and my constraint...
  32. marcus

    Progress on LQG dynamics (the Master Constraint program)

    Five new papers by Thomas Thiemann and Bianca Dittrich http://arxiv.org/abs/gr-qc/0411138 Testing the Master Constraint Programme for Loop Quantum Gravity I. General Framework 42 pages "Recently the Master Constraint Programme for Loop Quantum Gravity (LQG) was proposed as a...
  33. mindcircus

    How Is the Equation of Constraint Derived for a Disk Rolling Inside a Parabola?

    A disk of radius R rolls without slipping inside the parabola y=a*x^2. Find the equation of constraint. Express the condition that allows the disk to roll so that it contacts the parabola at one and only one point, independent of position. I know the equation of constraint: On the disk...
  34. E

    Simplifying Equations of Motion for a Bead Sliding on a Parabolic Wire

    So a bead slides down a frictionless parabolic wire of shape y=ax^2. I have to express the Lagrangian in terms of x and y. Then I have to use the constraint equation to express this solely in terms of x. Then I have to find the equations of motion, and simplify them for small oscillations...
Back
Top