MINLP problem with linear constraints and piecewise term 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 the floor() 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 with floor() 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 max function - 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?

 A: 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:


*

*You'll need to implement the constraints into the cost function yourself using some sort of large penalty multiplier. So $x^Tc \leq 3000$ will become:


if x[i]*c[i] > 3000:
    cost += 9001

or some other massive penalty.


*I've personally used this to solve a medium-sized problem with integer parameters, nonlinear objective, and nonlinear constraints so I know for a fact it can solve your problem. However, I have the freedom to run it off-line and can let it chug away overnight. If time is a constraint and you want a solution <5 minutes, then ignore my response.

*If you do decide this is the best approach, there's probably quite a few bugs in my code, but I'm willing to work with you. Just post an "issue" on github describing the problem and I'll get to it as soon as I can.

