I have an optimization problem where the objective function is non-linear but (I think) differentiable, there are linear constraints, and all parameters are integers. To make matters more difficult, there is a max term in the objective function that I think makes the solution piecewise.
With these variables:
- $n = 67$
- $i \in \mathbb Z, 0 \le i \lt n$, index for vectors below
- $x_i \in \mathbb Z, x_i \ge 0$, unknown column vector
- $c_i \in \mathbb Z, c_i \ge 0$, known column vector
- $U_{ij} \in \mathbb Z, U_{ij} \ge 0, j \in \mathbb Z, 0 \le j \lt 4$, known matrix
And this constraint:
$$x^T c \le 3000$$
I have to find values for $x$ that maximize the following scalar objective function s:
$$
s(x) =
\frac {
\left(
\sum_i \left(
x_i c_i \sum_j U_{ij}
\right)
\right)^2
}
{
2
\left(
\sum_i x_i c_i
\right)
\max_j
\sum_i x_i c_i U_{ij}
}
$$
I've been looking for open-source implementations of a MINLP (mixed-integer non-linear programming) optimizer.
The approaches I've tried so far are:
jDE
I used jDE optimization (Brest 2006), as implemented by Conceicao (2016) in the DEoptimR package. Whereas it doesn't directly support MINLP, it does say that the objective can be modified to support it:
Discrete and Integer Variables: Any DE variant is easily extended to deal with mixed integer nonlinear programming problems using a small variation of the technique presented by Lampinen
and Zelinka (1999). Integer values are obtained by means of thefloor()function only for
the evaluation of the objective function. This is because DE itself works with continuous
variables. Additionally, each upper bound of the integer variables should be added by 1.
Notice that the final solution needs to be converted withfloor()to obtain its integer elements.
It accepts a constraint function returning a scalar, which can enforce the "3000" constraint.
For technical reasons I haven't yet narrowed down, the algorithm doesn't converge and instead errors out.
Nelder-Mead
With mixed success, I used R's constrOptim, an implementation of the
Nelder-Mead method. This was very fast, and better supported the linear "3000" constraint through direct entry of a constraint matrix. Unfortunately, it has no support for integer parameters, and rounding error was so big that this method can't be used naively with a rounding step at the end.
So I need to figure something else out.
Questions
- Can the maxima for $s(x)$ be determined analytically? How would this work with the
maxfunction – would four solutions need to be found and compared? - Failing that, is there a different package for R, Octave or Python that's able to do MINLP with linear constraints?
Best Answer
Let me start by saying that my solution is in no way the best solution. In fact, it's probably the second worst next to brute force, but it might be a solution nonetheless.
Have you tried a genetic algorithm based on bit-string affinity? The main idea is:
You generate a "population", or rather a bunch of randomly generated solutions in a (non-feasible) space. Each individual in the population is encoded into a bit-string.
Evaluate each of these solutions against a fitness function (the objective) and get rid of the worst 50%.
Create a new set of individuals based on some product rule to take the place of the ones you deleted.
Repeat from step 1 until ~90% of the bit-strings match.
Because you use a bit-string encoding instead of smooth numbers, you can choose the number of bits to encode a variable so they are truly integers. i.e. If you use $2^3$ bits, since $2^3 = 8$ you have 8 potential values the parameter can take on by choosing a lower and upper bound as $0$ and $7$ respectively. the parameters can only take on integer values by definition. It also doesn't assume differentiability or linearity so those points are satisfied. You can read more about this type of algorithm here, and I've also programmed an open-source GA based on bit-string affinity here.
Some notes:
or some other massive penalty.