Topic
  • 2 replies
  • Latest Post - ‏2014-01-24T21:14:07Z by s.st1led
s.st1led
s.st1led
18 Posts

Pinned topic Can we express a non-arithmetical dependency between variables?

‏2014-01-24T14:04:45Z |

Hi everybody, I have a general question that I'm not sure if it makes sense, so forgive me in case I say some blasphemy on the theoretical point of view.

Let's say that I have an optimization problem with three variables x, y, z, and z is the variable to optimize over. Suppose x and y are independent variables, and z depends in some way from their value. This means that, if we fix x and y, then z can only have one value. In other words, z=f(x,y) for some function f.

If f can be expressed through an arithmetic function, I can define z as a dexpr: For instance, if z is equal to the sum of x and y I can define z as

dexpr int z = x+y;

instead of defining it a variable and let the search assign its value through the propagation of the constraint z == x+y that I will have to define in the subject to block.

Now, imagine that f is a complex function that can't be expressed arithmetically, but it's still writable in some programming language. Think of f as a Java function with nested loops, complex data structures (internal array variables, queues, hashmaps, trees...) that takes as input x and y and after some iterations outputs the value of z.

Would it be possible, with the obvious help of the Concert API, to express this kind of dependency? Ideally, I would like to write something like that in my constraint model:

dvar int x, y;

dexpr int z = f(x,y);

maximize z;

Where f(int a, int b) is a function defined in some context  where I have access to more expressive structures than the sole arithmetic operators of OPL. Here I'm thinking of a program that uses the Concert API, but perhaps even OPL Script might do the job.

Ideas?

 

Regards,

Stefano

Updated on 2014-01-24T14:08:29Z at 2014-01-24T14:08:29Z by s.st1led
  • AlexFleischer
    AlexFleischer
    110 Posts

    Re: Can we express a non-arithmetical dependency between variables?

    ‏2014-01-24T18:37:32Z  

    Hi,

    have you thought about using a custom constraint or a custom goal in concert ?

    If the possible values of x and y are not that huge, could storing all f results in an array an option ?

    regards

  • s.st1led
    s.st1led
    18 Posts

    Re: Can we express a non-arithmetical dependency between variables?

    ‏2014-01-24T21:14:07Z  

    Hi,

    have you thought about using a custom constraint or a custom goal in concert ?

    If the possible values of x and y are not that huge, could storing all f results in an array an option ?

    regards

    Hi, thank you for your answer.

    For sure pre-computing all the values for f(x,y) is not an option, since the domain of x and y is usually extremely big (they are arrays of up to ~100 values and domain size up to ~1000).

    As for custom constraints and custom goals, I didn't really look into them. Now that you told me, I had a very quick look on the manual and custom constraints look like they do exactly what I want.

    I'm not sure about custom goals, that should be a way to specify how the search behaves (what variables to branch on at each step, etc). Maybe using custom goals it's a logical step after choosing to write custom constraints, but I'm not sure. I guess I'll read the chapter of CP Optimizer Extensions and then come back with some code examples.

     

    Regards,

    Stefano