1

I am looking for a suitable (exact) optimization method for the following problem (I have already solved the same problem using heuristic methods).

For j number of binary variables (i.e.: $x_1,x_2,x_3,...x_j$), a variable A is defined as follows:

$A=\sum\limits_{i=1}^j x_i$.

Furthermore, there's B:

$B=f(x_j)$,

a non-linear function of all values $x_1 ... x_j$. (i.e.: how much $x_a$ increases $B$, depends on the values of all other $x_j$).

Now I want to achieve the following:

$min(A-B)$

Is it possible to capture this in a MILP / MINLP problem? Any hints or pointers are much appreciated! I am thinking the non-linear part in the objective function prevents me from using some form of LP, and/or makes it much more complex, but I can't seem to figure out why, let alone prove it. (I am not a mathematician by training :(..)

Thanks!

Rat3dr
  • 11
  • what is the formula for $f$? – LinAlg Nov 26 '16 at 12:57
  • So far, I have only been able to put that in a table. To explain the problem a little more:

    || j number of stations in a plant can be automated || the more plants are automated, the faster the total process, the higher B (= cost reduction) || the more plants are automated, the higher the total investment costs (A) || speeding up the process by adding automated stations is interdependent, e.g. the added performance (incease of B) per new automated station depends on the number and location of existing automated stations. ||

    I am working on defining/finding $f$ right now.

     – Rat3dr Nov 26 '16 at 14:21
  • Furthermore, I'd like to add that $f$ is not either constantly increasing or decreasing, it's more or less all over the place while gradually adding more automated stations, and/or moving automated stations 'down the production line'.

    I.e. 2 out 6 automated might give a nice performance, while 3 out 6 might perform worse, and 4 out 6 better again. Also putting the 2 stations in location 1 and 3 may perform better than in 1 and 4, or 1 and 2.

     – Rat3dr Nov 26 '16 at 14:28
  • If you can only put those numbers in a table and can't give any general properties, how could any algorithm find the optimum without enumerating all options? – LinAlg Nov 26 '16 at 16:00
  • Let's assume I can't find $f$ (to be a continuous function), that would mean there's no way to solve this with an exact optimization method? Perhaps except by breaking it up in (many small) sub-problems? – Rat3dr Nov 27 '16 at 04:09

0 Answers0