How to solve the min-max problem with mixed integer linear programming(MILP)?

Question

keisuke maesako 2021-8-17

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1081367-how-to-solve-the-min-max-problem-with-mixed-integer-linear-programming-milp

编辑： Sadia Tasnim 2024-2-3

I am trying to solve the MILP problem by referring to the page below.

https://jp.mathworks.com/help/optim/ug/mixed-integer-linear-programming-basics-problem-based.html?lang=en

The problem I want to solve is that the objective function is represented by min-max.

However, I understand that the "optimproblem function" that creates an optimization problem only supports maximization and minimization, not min-max.

https://jp.mathworks.com/help/optim/ug/optimproblem.html?lang=en

So, please tell me how to solve the min-max problem.

thanks in advance.

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

keisuke maesako 2021-8-18

I want to solve an optimization problem to achieve network traffic distribution.

Therefore, the maximum value of the network link utilization rate is set to be minimized as the objective function.

The constraint condition is the calculation of the network link utilization rate.

The only determinant is

and I think it's MILP.

Below is a description of the formulas and variables.

V is network node set, E is Network link set, F is network flow set,

is link l utilization,

is link l capacity,

is amount of traffic through link l by flow f,

is path set for flow f,

is requested traffic volume of flow f,

is 1 If route r is assigned to flow f,

is 1 if route r is assigned to flow f and route r contains link l.

Sadia Tasnim 2024-2-2

移动：Matt J 2024-2-2

How did you solve your problem? I am facing the similar challange as you described here.

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Matt J 2021-8-18

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1081367-how-to-solve-the-min-max-problem-with-mixed-integer-linear-programming-milp#answer_769442

编辑：Matt J 2021-8-18

Eliminate the inner max problem by rewriting it as,

7 个评论
显示 5更早的评论隐藏 5更早的评论

Sadia Tasnim 2024-2-2

编辑：Sadia Tasnim 2024-2-2

在 MATLAB Online 中打开

thank you so much for your kind response. I am new to this expression and also learning optimization recently. can you please help me figure out how to code this kinda min max z expression in matlab?

The following is my sample code. I wanted to minimize the maximum of z under nonlinear constarints but cannot figure out how to make matlab understand:

clc; clear; close all;
rowx = 2; colx = 2;
x = optimvar("x",rowx,colx,"LowerBound",0,"UpperBound",2);
rowy = 3; coly = 3;
%x = optimvar(name,n) creates an n-by-1 vector of optimization variables.
y = optimvar("y",rowy,coly,"Type", "integer", "LowerBound",0,"UpperBound",1);
z = optimvar("z","UpperBound",1);
obj = [];
prob = optimproblem('Objective',obj);
prob.Constraints.cons1 = sum(y) == ones(1,coly);
count = 0;
for i = 1:rowx
    for j = 1:colx
        count = count+1;
        prob.Constraints.(['cons', num2str(1+count)]) = z >= (sin(x(i,j)))^2 + y(1)^2/4-(x(i,j)+x(i,j)-x(i,j)/5)^2+exp(y(2));
    end
end
for i = 1:rowx
    for j = 1:colx
        x0.x(i,j) = abs(randn(1,1));
    end
end
for i = 1:rowy
    for j = 1:coly
        x0.y(i,j) = 0;
    end
end
for i = 1:coly
    x0.y(randi(rowy),i)= 1;         
end
x0.z = 0.59;
show(prob)
[sol,fval] = solve(prob,x0)

I also understand that my code is just finding points that meets the constraints only rather than minimizing it.

Torsten 2024-2-2

编辑：Torsten 2024-2-2

在 MATLAB Online 中打开

@Sadia Tasnim

You mean that you want to add

prob.Objective = z;

to your problem formulation ?

The code gives a result, but I wonder why because you try to access y(1) and y(2) although you define y as a 3x3 matrix.

Sadia Tasnim 2024-2-3

编辑：Sadia Tasnim 2024-2-3

Answer to your question is yes. Thank you so much @Torsten. Perhaps my problem is solved. This code is just a practice sample that I randomly made to learn optimization syntax using MATLAB.

Thanks again for your sincere response @Torsten and @Matt J.

请先登录，再进行评论。

How to solve the min-max problem with mixed integer linear programming(MILP)?

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

回答（1 个）

7 个评论
显示 5更早的评论隐藏 5更早的评论

另请参阅

类别

标签

产品

版本

Community Treasure Hunt

How to solve the min-max problem with mixed integer linear programming(MILP)?

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

回答（1 个）

7 个评论 显示 5更早的评论隐藏 5更早的评论

另请参阅

类别

标签

产品

版本

Community Treasure Hunt

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

7 个评论
显示 5更早的评论隐藏 5更早的评论