Deterministic optimization is feasible, but the YALMIP robustification module is infeasible.

[HBA-scu]

I have encountered some unresolved issues while using the “uncertain” function to solve robust optimization problems. From a mathematical perspective, the optimization problem is feasible, with uncertainty sets in the form of polytopic uncertainty sets, which can be solved using the YALMIP robustification module. However, during the solving process, I consistently encounter the message of "Infeasible problem" (I have tried the troubleshooting methods provided by you at https://yalmip.github.io/debugginginfeasible, but they did not work). I have attached the specific optimization problem and code for your reference, and I would greatly appreciate it if you could spare some time to have a look at it.
The model is:

The code is:

%% 两阶段鲁棒优化子问题-鲁棒优化模块求解
clc
clear
close all
warning off
%% 参数矩阵
C = [22, 33, 24;
    33, 23, 30;
    20, 25, 27];
d_ = [206; 274; 220];
d_wave = 40;
gamma = [1.8,1.2];
P = [1 1;1 1;1 0];

%% 决策变量
z = [426;0;274];
x = sdpvar(3,3,'full');
g = sdpvar(3,1);

%% 目标函数
objective = sum(sum(C.*x));

%% 约束条件
G = [uncertain(g) , g'*P <= gamma , g >= 0 , g <= 1 ];
Constraints = [];
Constraints = [Constraints , sum(x,2) <= z ,x >= 0 ];
Constraints = [Constraints , sum(x)' >= d_ + g*d_wave];

%% 设置求解器
ops=sdpsettings('verbose', 3, 'solver', 'cplex');
sol=optimize(Constraints + G , objective ,ops);

%% 分析错误标志
if sol.problem == 0
    disp('求解成功');
else
    disp(['求解失败，错误原因为：',sol.info]);
end

%% 输出结果
if sol.problem == 0
    objective = value(objective)
    x = value(x)
    z = value(z)
end

[johanlofberg]

It's simply not feasible. The last row is far from being possible to satisfy as a simple slack will reveal

s = sdpvar(3,1)
Constraints = [Constraints , sum(x)' >= d_ + g*d_wave-s];
optimize([Constraints, G,s>=0],sum(s))
>> value(s)

ans =

     0
     0
   120

[HBA-scu]

Thank you for your response. I now know where the problem lies in the model.

[HBA-scu]

To facilitate your understanding, let me first explain the meanings of the variables and then present my second question.

In this problem, variable z represents the capacities of three warehouses, variable x represents the quantity of goods transported from the i-th warehouse to the j-th customer, and variable g represents the increase in customer demand compared to the benchmark value d_. Previously, I set sum(z) = sum(d_). However, in robust optimization, the customer demand is expected to be larger, rendering the problem infeasible. I understand this issue now.

Considering that in the uncertainty set, sum(g) should be less than or equal to 1.8, I believed that it would be sufficient to ensure the total capacity of the three warehouses, sum(z) >= sum(d_) + 40 * 1.8 to have a feasible solution. However, based on the added slack variables and the results of my debugging, it appears that at least the sum(z) needs to be increased by 120 (i.e., 3 * 40) to potentially obtain a feasible solution. May I ask the reason behind this?

[johanlofberg]

I don't understand the question, but maybe you are talking about the difference between solutions (which easily can be impossible), and policy solutions (which is less restrictive), sort of related to this https://yalmip.github.io/equalityinuncertainty

also, if there are solutions for the indivudal uncertain cases, does not mean there is a solution to the robust case

x <= w
y <= 1-w
x+y>=1/2

where 0<= w<=1 is easily feasible for both w=0 and w=1, but there is no solution to the robust case since uncertain constraints implies x<=0, y<=0

[HBA-scu]

Thank you for your response. I will study the link you provided and then provide you with feedback.

[HBA-scu]

I have studied the link you provided and attempted to debug the code, but the issue still remains unresolved. I would like to provide some background information on this problem and seek your assistance.
In region A, there are 3 warehouses for storing goods, denoted by z for their capacity. In region B, there are 3 users with demand denoted by d. The goods will be transported from the warehouses in region A to the users in region B. The unit transportation cost from the i-th warehouse to the j-th user is represented by cij, and the quantity of goods to be transported from the i-th warehouse to the j-th user is xij. To account for uncertain demand, variable g is used to describe the uncertainty in user demand, where d = d_ + g*40. Here, d_ represents the basic demand, and gj ∈ [0,1]. Additionally, the uncertain variable g is subject to the constraints g1+g2+g3≤1.8 and g1+g2≤1.2.
This problem is essentially a subproblem of a two-stage robust optimization problem discussed in the paper "Zeng B, Zhao L. Solving two-stage robust optimization problems using a column-and-constraint generation method[J]. Operations Research Letters, 2013, 41(5): 457-461." As the capacity z of the warehouses has already been solved in the master problem, it can be treated as a known variable in the subproblem.
The capacity of the warehouses obtained from the master problem is [772, 0, 0]. However, when I substitute this value into the subproblem, it still remains "infeasible". Following the debugging method you provided earlier by adding slack variables, the result shows that a feasible solution is obtained when the slack variables are set as [48; 0; 0]. From the analysis of the background of this transportation problem, it implies that the sum of the capacities of the three warehouses needs to be increased by 48 to obtain a feasible solution.
This problem is quite similar to the example you mentioned, and I have also attempted to solve this optimization problem using the YALMIP toolbox, but it does not seem to be applicable. However, if I utilize the KKT conditions, it appears that a feasible solution can be obtained. I am not quite sure about the underlying reasons for this. Your explanation would be greatly appreciated.
The robust optimization problem you mentioned:

Its Inner problem:

KKT:

Reformulation model:

The code:

clc
clear
% Yalmip robust model
sdpvar x y w
F1 = [x <= w , y <= 1 - w , x+y >= 1/2];
W = [uncertain(w) , 0 <= w <= 1];
sol_1 = optimize(F1 + W);
sol_1.info

% KKT
yalmip('clear')
sdpvar x y w L1 L2 L3
binvar u1 u2 u3
M = 1e8;
F2 = [x <= w , y <= 1 - w , 0 <= w <= 1];
F2 = F2 + [1 + L1 - L3 == 0 , 1 + L2 - L3 == 0 , [L1 L2 L3] >= 0];
F2 = F2 + [L1 <= M*u1 , x - w >= M*(u1 - 1)];
F2 = F2 + [L2 <= M*u2 , y - 1 + w >= M*(u2 - 1)];
F2 = F2 + [L3 <= M*u3 , -x - y + 0.5 >= M*(u3 - 1)];
objective = x + y;
sol_2 = optimize(F2 , -objective);
sol_2.info

The results indicate that the first method is infeasible, but the second method is feasible. Thank you once again for your invaluable assistance!

[johanlofberg]

Too much wall of text, but the code you supply simply cannot make sense as you cannot attack the trival problem I gave using KKT conditions. There is no single solution w that can be computed in this setting, i.e. there does not exist a worst-case. w=1 is worst-case for the second constraint, and w=0 is worst-case for the first, and combined they imply both x and y cannot be larger than 0. For all fixed w in the uncertainty set x+y can always be made >=1

You seem to fail to recognize the for-all property central in a robust solution. It is not about coping with a worst disturbance, but coping with all possible worst-cases

I want to pack a bag going on a travel. I can pack my spring bag which weighs 5kg and an extra winter-bag which weight 15kg and pack my summer-bag which weight 15kg. I can only bring 20kg on the plane. Worst-case is that it is very cold or very warm which requires me to bring either warm or cold bag, but since I do not know which it is I have to be robust against both (which never can happen, but I still have to bring both) which is not allowed as that would weight to much. Thus infeasible, despite both winter and summer travel is feasible

[HBA-scu]

I sincerely apologize for wasting your time due to my ignorance. Because the solver indicated that the problem is feasible, I mistakenly believed that a solution existed. Now, I have gained a general understanding of what you meant. You mentioned that KKT conditions cannot be used to attack the trivial problem you provided. In that case, how should one determine if KKT conditions can be used to solve a robust problem? While a simple problem can be inferred logically, how can one determine the feasibility of using KKT conditions to solve more complex robust problems?

[johanlofberg]

It's not about whether you can solve it using kkt conditions, but understanding what you are trying to solve. In a robust solution you are not (primarily) trying to solve a minmax problem. You are trying to find a solution which is feasible for all possible realizations in the uncertainty set. The only way to solve that using KKT (which you shouldn't) would be to apply a KKT condition on every constraint which involves the uncertainty (as I did manually when I independently optimized the rhs of x<=w and y<=1-w, and thus concluded that it must hold that x<=0 and y<=0. This is what the robust framework does, using various methods to perform that optimization without resorting to expensive methods such as kkt)

To me, it feels like you are not looking for robust solutions, but robust policies or something like that, i.e. given a realization of uncertainty, you want to act accordingly. You don't want to do the same thing regardless of the uncertainty. If you actually want robust solutions, well then you simply discovered that the problem is infeasible

[HBA-scu]

I get it, thank you very much.