Mixed Integer Linear Programming Problem

Question

Hafsa Farooqi 2020-12-22

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/700535-mixed-integer-linear-programming-problem

回答： Alan Weiss 2020-12-27

I am trying to solve a integer linear programming problem, written in matlab as follows:

fs = 170;
Ts = 1/fs;
t = 0:Ts:1;
fo = 20;
f = -1*ones(1,171);
intcon = 1:length(f); %% All variables are integers. 
lb = zeros(length(171),1); %% 
ub = 1*ones(length(171),1); %% Enforces the optimization variables are binary.
Aeq = [];
beq = []; 
A = ADS; %% Teoplitz Matrix (Convolution to Matrix Multiplication)
b = 5.*sin(2*pi*fo*t); %% 
x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub);

When I try to solve this in matlab using default options, it tells me that no feasible solution exists. Then I removed the integer constraints and tried resolving it using linprog solver. It again tells me the same thing. I do not see any reason why this should happen.

I was just wondering if the reason for this might be the linear constraint b which is a sinusoidal? When I put b as a constant value, it solves the optimization problem.

Can someone please give me a bit more insight as to the reason of infeasibility in this case?

4 个评论
显示 2更早的评论隐藏 2更早的评论

Walter Roberson 2020-12-23

What are the mininum and maximum number of positive and negative entries in one row of the toeplitz matrix?

For example if all of the entries except for (say) 3 were negative, and the rest positive, then with your f being all negative 1, that could turn into a sum that could not feasibly be negative enough to satisfy the 5*sin() being as low as -5

Hafsa Farooqi 2020-12-23

在 MATLAB Online 中打开

@Walter, below are the first three rows of the Teoplitz matrix. It is like an lower triangular matrix. The entries are zeros or close to zero.

-4.38881148728960e-09	 0	0	0	0	0	0	...................................
000373969299993102	-4.38881148728960e-09	0	0	0	...................................................
000981230594043130	0.000373969299993102	-4.38881148728960e-09	0	0	0	.............................................
00151783785076426	0.000981230594043130	0.000373969299993102	-4.38881148728960e-09	 0	0	.............

Is there a way to deal with this issue in order to achieve feasibility?

请先登录，再进行评论。

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

Answer 1

Matt J 2020-12-24

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/700535-mixed-integer-linear-programming-problem#answer_583452

编辑：Matt J 2020-12-24

Since your unknown x(i) are bounded between 0 and 1, an upper bound on abs(A*x) is sum(abs(A),2). It seems doubtful to me that sum(abs(A),2) for the matrix you've shown could ever exceed 5. Therefore A*x could never reach a value less than -5, which it would have to in order for A*x to be bounded from above by b=5.*sin(2*pi*fo*t).