Topic
  • 1 reply
  • Latest Post - ‏2013-05-27T12:22:55Z by rdumeur
Faramarz Khosravi
Faramarz Khosravi
1 Post

Pinned topic Solve a Polynomial Problem Containing Look-up Tables

‏2013-05-27T11:00:26Z |

Hello,

I want to solve an integer programming problem. I searched a lot and used different tools including Excel solver.
My issue is that I need to define some look-up functions, since I want to consider performance-power-cost-... trade-off in a system.
My optimization function is polynomial, not linear nor quadratic.

For example (it is not a real problem, just an example in the form I want to solve):
minimize
         c(x1)^5 + c(x2)^3 + 5 * c(x3)*c(x1)*c(x2)^2 + ...
subject to
      0 <= x1, x2, x3, .... <= 10
      p(x1) + 0.5 * p(x2) >= 7
      4 * r(x2) + r(x)^3 <= 30
      x1, x2, .... are integers

The number of variables (x) are restricted (to 5 as an example) and all of them get values from the same set of integers! Moreover, all the functions are small look-up tables like the following:
x1, x2, x3 are in {1,2,3,4}
c(1) = 4.7, p(1) = 3, r(1) = 5.5
c(2) = 3, p(2) = 2.8, r(2) = 7
....

I solved simple problems using brute force simulation in java, but my regular problems are huge, and cannot be solved using brute force.
I would really appreciate if you let me know whether CPLEX, Gurobi or any other tool supports polynomial optimization functions and look-up tables.

Thanks a lot,
Fara

  • rdumeur
    rdumeur
    26 Posts

    Re: Solve a Polynomial Problem Containing Look-up Tables

    ‏2013-05-27T12:22:55Z  

    Dear Fara,

    To use integer variable as indices in lookup tables, all you need to do is to create the appropriate float arrays in the model.

    First declare your variables, with domain 1..m (m being the size of the lookup tables)

    using CP;
    int n = 10;
    int m = 5;
    dvar int x[1..n] in 1..m;

    Then define, suitable arrays for your cost / power functions:


    float c[1..m] = [4.7, 3,  <other values > ...];
    float p[1..m] = [3, 2.8, < other values> ... ];
    float r[1..m] = [ 55, 7, <other values> ... ];


    then declare your objective using element expressions on "c" :


    minimize pow(c[x[1]], 5) + pow(c[x[2]], 3) + c[x[3]]*c[x[1]]*pow(c[x[2]],2) + <other terms> ... ;

     

    then declare your constraints using the contraint element on "p" array with "x" values :


    subject to {
          p[x[1]] + 0.5 * p[x[2]] >= 7;
          4 * r[x[2]] + r[x[1]]^3 <= 30;
    }

    I hope this helps!

     

    Cheers,