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

Question

Dredging Production 2018-12-19

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/436456-how-can-i-solve-or-re-write-an-optimization-problem-with-equality-constraints-some-integer-variable

编辑： Walter Roberson 2019-1-13

采纳的回答： Dredging Production

在 MATLAB Online 中打开

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:

fmincon does not support integer variables
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
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!

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Torsten 2018-12-19

编辑：Torsten 2018-12-19

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 2018-12-19

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/436456-how-can-i-solve-or-re-write-an-optimization-problem-with-equality-constraints-some-integer-variable#answer_353122

编辑：Dredging Production 2018-12-19

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 ?

8 个评论
显示 6更早的评论隐藏 6更早的评论

Torsten 2019-1-7

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 2019-1-13

编辑：Dredging Production 2019-1-13

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 2018-12-19

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/436456-how-can-i-solve-or-re-write-an-optimization-problem-with-equality-constraints-some-integer-variable#answer_353077

编辑：Dredging Production 2018-12-19

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?