How can I solve or re-write an optimization problem with equality constraints, some integer variables and a non-linear objective function?

Hi,

I'm trying to optimize the following (very simplified) problem:

Non_linear_objective = 500 * (x(1)+x(2)+x(3)+x(4)) + 200 * (x(5)+x(6)+x(7)+x(8)) + 95 * ( x(9)-1)^2 + (x10-x9)^2 + (x11-x10)^2 + (x12-x11)^2 + (1-x12)^2 );

5 equality constraints:

    x(1)+x(5)+x(9) = 1
    x(2)+x(6)+x(10) = 1
    x(3)+x(7)+x(11) = 1
    x(4)+x(8)+x(12) = 1
    40 *( x(1)+x(2)+x(3)+x(4)) = 80

4 integer variables: x(9), x(10),x(11),x(12) (which actually means that x(1)+x(5) (etc) is binary)

Why I'm currently not able to solve this:

1. fmincon does not support integer variables
2. I can rewrite the problem to a linear objective, with non-linear constraints, and 4 integer variables. But intlinprog does not support non-linear constraints
3. I can use the Genetic Algorithm, but this finds a local mimum only. I have to solve this simple problem >300 times, to find the correct answer. (I'm using lb and ub of 0 and 1 for all variables)

Is my reasoning correct?

How could I solve these kind of problems?

Thank you!

[Torsten]

Are there positivity constraints on the x(i), i.e. x >= 0 e.g. ?

If this is the case, x(9)-x(12) can only have values 0 or 1. There are 2^4 = 16 combinations for x(9)-x(12) with 0 or 1 for the variables. So just solve your problem by running it 16 times using "quadprog" (or "fmincon").

Best wishes

Torsten.

Answer 1

[Dredging Production]

Thank you. Note sure whether I can use that software, but I will have a look.

I'm thinking about another solution: Creating the input (selection of integer variables) in such a way that the optimum solution can be found without calculating all the combinations. So, somehow the 'input creator' should learn from the output (machine learning). I have some ideas on how to do this, but I have never set-up something like this before.

Do you perhaps have somes ideas about this, or an example in which this is used ?

[Torsten]

I'd concentrate on the codes that already exist. Your problem is a mixed-integer quadratic programming problem. Codes for solving such problems are listed here:

http://plato.asu.edu/sub/discrete.html

Best wishes

Torsten.

[Dredging Production]

Thank you a lot! Your answers are very useful.

I have tried to use Mosek to solve this (mixed-integer quadratic problem). However, I get an error saying that the problem is not convex. First I thought this is because the problem has multiple solutions. Since x(9:12) : [0 0 1 1] and [1 1 0 0 ] and [1 0 0 1 ] all result in the same solution). However, I'm not sure whether that's the reason?

For this smaller problem I'm using BMIBNB now, and it works

[Torsten]

If your objective function is not convex, you will have to live with local minima, I guess.

[Dredging Production]

Thank you for your help.

Things are working now :) !

[Torsten]

If I may ask: Which solver did you finally use ?

[Dredging Production]

Actually I'm still stuck. I thought I solved it, cause it worked for a very small problem (BMIBNB).

But solving my real problem, or simplified version of my problem, takes very long (it actually never finished). I think I have to re-write the problem in a more efficient way.... (?).

Have you got any idea how long it would take to solve a problem with 5408 variables and 208 integer variables ? (this is a simplified version of my problem)

[Torsten]

If this task is important for you, I'd consider licencing "CPLEX". It's the best software package you can get in the field of optimization, I guess.

[Dredging Production]

Great, had a quick look seems robust, fast and organized. Will have a proper look later.

Btw an update: I slightly rewrote the problem and it solves the problem much quicker now. I'm using the MOSEK solver. BMIBNB works as well, but a lot slower.

Will try to increase the size of my problem now, and see whether it works.

Thank you for all your help!

Answer 2

[Dredging Production]

Thank you for the quick reply!

All x are >= 0 and <=1.

I understand that solving 16 problems, is a solution for this small problem (thanks). But actually this problem is quite big in reality. For instance, there are actually 48 instead of 4 integer variables (and some more other constraints). This would mean I need to solve the problem way too many times.

Is there a way to avoid solving multiple problems ( = preferable!), or at least to decrease the amount of problems to be solved?