2
$\begingroup$

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?
$\endgroup$
4
  • $\begingroup$ Are you hoping for a provably globally optimal solution? $\endgroup$
    – David M.
    Mar 19 '19 at 23:27
  • $\begingroup$ @DavidM. 'hoping' yes, but if that's not feasible I'll take something weaker for now. $\endgroup$
    – Reinderien
    Mar 20 '19 at 0:33
  • 1
    $\begingroup$ I suggest having a look at coin-or.org/projects $\endgroup$
    – Pebeto
    Mar 20 '19 at 3:12
  • $\begingroup$ @Pebeto I dove into Couenne. Unfortunately it does not support the max function. Bonmin is failing with an LP relaxation is infeasible or too expensive message. $\endgroup$
    – Reinderien
    Mar 25 '19 at 20:35
1
$\begingroup$

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:

  1. 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.

  2. Evaluate each of these solutions against a fitness function (the objective) and get rid of the worst 50%.

  3. Create a new set of individuals based on some product rule to take the place of the ones you deleted.

  4. 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:

  1. 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.

  1. 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.
  2. 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.
$\endgroup$
1
  • $\begingroup$ My work on this kind of fizzled, but your answer is the best I could have expected so I'm going to accept it. $\endgroup$
    – Reinderien
    Jan 5 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.