Black box constraints

Anonymous
2011-05-30
2015-08-17
  • Anonymous - 2011-05-30

    Is it possible to use JaCoP to solve a constraint problem that includes what might be called black box constraints? That is, I would like to be able to write a function that computes the values of one Domain Variable as a function of some other Domain Variables. This is a function that JaCoP will not be able to analyze, i.e., it will be a black box as far as JaCoP is concerned.

    Thanks.

    • Russ Abbott
     
  • Radoslaw Szymanek

    Hi,

    There is nothing readily available. However, it should be rather straightforward to create your own constraint, e.g. BlackBoxConstraint using for example XeqY as a template and then call your function that will compute the new domain of each of the variables given other variables.

    If your constraint does not have a state then the only things you need to implement is consistency() and impose(). The consistency function will just call the external function to compute a new domain and call in(…) functions to restrict domains to just computed values.

    Do you want to have this blackBoxConstraint for security reasons?

    Can you be more specific how would you like to have this blackBox constraint implemented in terms of API? (info about constructor, etc). It does seem like a potential addition we could quickly add but I need to know more to make sure I fully understand your need.

    If this blackBox constraint is not well behaving (etc the result depends not only on the domains of variables but e.g. the number of computations of this function) then nondeterministic and incomplete traversal of the search will occurr.

    The blackBox function used to compute the domain of the result could also be informed about backtracking/changes as they occurr to improve the efficiency of the computation so feel free to express in more details the functionality you need.

    best,
    Radek

     
  • kris

    kris - 2011-05-31

    Hi!

    If you want to define a discrete function in JaCoP you can always try to use ExtensionalSupport *** constraint. Technically it defines a relation between n variables but you might be able to use it for your purpose.

    Best regards,
    /Kris

     
  • Anonymous - 2011-05-31

    The reason for wanting a black-box constraint is to allow one to include arbitrary functions as part of the constraint system.  More generally a capability such as this would in effect add a genetic algorithm capability. The black box constraint could be a GA fitness function. One could then try to minimize that function while at the same time satisfying other constraints. It would then not be necessary to include the other constraints in the fitness function since the constraint system would enforce them.

    In addition, perhaps one doesn't require a minimum of the fitness function, just that it fall in some range.  For example, it might be easier to solve multi-objective problems using a system of this sort-where each objective must fall within some range but where one doesn't require a minimum or maximum of any one of them and where it's not easy to define an overall fitness function.

    This sort of thing comes up a lot when one is doing trade-offs among different capabilities when considering various design options for large systems. You want at least a given amount of each capability, but no one capability is that much more important than the others. The functions that compute the "amount" one has of the capabilities are too complex to be expressed in terms of JaCoP-like arithmetic. 

    Consider designing an automobile. One cares about gas mileage, acceleration, safety, roominess, etc. One has models that given the parameters of a candidate design will estimate what the values are for each of these criteria. The models are too complex to be expressed as JaCoP constraints, but they are not too complex to be expressed as easy-to-compute functions.  One would like to use JaCoP to explore the trade space.

    Often this is done by building a large spreadsheet and doing what-if experiments. The problem with that approach is that spreadsheets produce answers in only one direction.  One would like to be able to express the relationships among the design parameters using the model functions, set some of them as well as some of the acceptable criteria ranges and see what happens.

     
  • Stefan

    Stefan - 2015-07-10

    Is there any update on this about what Russ was asking?

    I mean what I am trying to ask is how to implement blackbox-function in which you just look at an input-output relation? (e.g. if you do have a non-linear model to be evaluated)

     
    • Radoslaw Szymanek

      Hi,

      A constraint is an entity that can given domains of some of its variables reduce the domains of the other variables in its scope. For example, XeqY constraint will reduce the domains of x and y variable to be the intersection of the domains of x and y. For the user using XeqY, it is already a black box constraint as he/she only specifies relation and does not worry how this relationship is enforced.

      Having an efficient implementation of constraint means having an efficient implementation of its consistency function.

      We can not help you in the implementation of your black-box constraint. You have to implement it yourself and then you can plugin into JaCoP by simply imposing it to the store.

      If you wanted to have a specific constraint, e.g. given a non-linear function of given nature then you could try to write a generic implementation of non-linear constraint. You would need to first define the relationship maintained by your constraint as well as variables. Given this I could give you hints what existing constraint you could use to get the relationship you are looking for modeled.

      However, please note that you already have for example ExtensionalSupport constraint that can by simply providing all the solutions (all the allowed assignment within your blackbox) constraint to get propagation. If your blackbox constraint that you want to implement has little structure then you should simply use this extensionalsupport constraint. If your black box constraint has some structure/nature then you could write your own constraint implementation for your specific constraint with some known structure.

      CP is always about exploiting the structure of the relationship that exists and needs to be enforced to make things more efficient.

      best,
      Radek

       
  • Stefan

    Stefan - 2015-08-12

    Hi Radek,

    Thank you! You made a things clearer to me.

    I think I now unterstand how to use ExtensionalSupport, but if you have a problem with a lot of possible solutions this wont work, right? A lot = millions for example?

    Lets say I have a non linear functions like f(x,y,z)=x+y+e^z and I want to have a constraint " f(x,y,z) < constant ", what do you think is the best way to implement such functions? Is there something like a cooking recipe to build such constraints in code?

    Thanks again,
    Stefan

     
  • kris

    kris - 2015-08-12

    Hi Stefan,

    I would not use ExtensionalSupport if you have millions of cases. You can usually create your constraint by decomposition to existing constraints. For your example function I would use the following constraints.

    temp1 = e^z / in JaCoP XexpYeqZ for IntVar and ExpPeqR for FloatVar /
    f = x + y + temp1 / in JaCoP XplusYplusQeqZ /

    Best,
    /Kris

     
  • Radoslaw Szymanek

    Hi,

    I will complement Kris answer.

    First the part "< constant" can be obtained by simply not accepting assignment to x, y, z that produce value f(x, y, z) that is greater than value. Or by imposing constraint XltC(f, constant) if you use f variable.

    Then you could have a potentially huge number of tuples. If it is something that can be manage then you impose ExtensionalSupport constraint. Please note that there are few variants and one may be better for you. You need to experiment with them. In your particular case, it would be not worth if you have more than 1000 tuples as Sum should propagate nicely. The benefit of ExtensionalSupport could be further reduced if you label variables x, y, z in search one after the other. This will make the potential failures due to lack of propagation within Sum constraint restricted.

    You could make the part temp1 = e^z into ExtensionalSupport constraint, as XexpYeqZ is not obtaining GAC thus you will have a benefit of stronger consistency. It will involve only two variables so the constraint will have small size. Again, if you label variables x, y, z, temp1 one after the other in search then again the benefit of Extensional over XexpYeqZ may not show up.

    Summing x + y + temp1 is usually not worth doing into ExtensionalSupport and using a Sum constraint can provide already good propagation.

    Hope that helps.

    best,
    Radek

     
  • Stefan

    Stefan - 2015-08-17

    Hi Kirs, hi Radek,

    Thanks for those explanations. It seems like I really need to get to know to the different constraints already being implemented and then using the temp-variable idea more frequently. Finally I also unterstood how the ExtensionalSupport works, thanks for that.

    To the initial idea of the black box constraint, I more thought of it like this:
    1. Model something by using constraints and come up with some values (e.g. 1,2,5) of the variables (x0, x1, x2)
    2. Those values are then being used in an objective function (ObjFct(x0,x1,x2)) of which the structure is not accesible (for example a simulation) and are evaluated to a result (r).
    3. One implement a contraint: BlackBoxVarFct(ObjctFct, Constant) where a constant is being compared to the result and can be used for optimization purposes (e.g. constant gets smaller after each iteration or something)

    Thanks again.

    Stefan

     

Log in to post a comment.

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:

JavaScript is required for this form.





No, thanks