Mixed Integer Linear Programming Problem

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?

[Walter Roberson]

We do not know ahat ADS or bDS are?

Is it correct that bDS is the "constant value" that you were expermenting with?

[Hafsa Farooqi]

Hi Walter. Thanks for your reply. I had updated my code to remove some unnecessary code.

b is basically a sinusoidal with frequency of 20 Hz as defined above.

ADS is teoplitiz matrix, in this case with an order 681x 171. It is generated from an linear time invariant (LTI) tranfer function.

What I want is to maximize the sequence of x such that ADS*x <= b such that x is binary.

Now, when I define the problem as it is, it says that no feasible solution exists. Then I removed the binary constraints and resolved it using linprog solver. I thought maybe the binary constraints were too strict and resulted in infeasibility but even with linprog it resulted in infeasibility. Finally I tried to replace b (which is a sinusoidal) with a constant value just to see if that works. And it worked.

So I am just wondering what might be the reason of infeasibility when b is a sinusoidal? Or if that is not the case, what else might be the issue which results in infeasibility?

[Walter Roberson]

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]

@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	...................................
0.000373969299993102	-4.38881148728960e-09	0	0	0	...................................................
0.000981230594043130	0.000373969299993102	-4.38881148728960e-09	0	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]

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).

Answer 2

[Alan Weiss]

You might find the following documentation useful:

Investigate Linear Infeasibilities

Alan Weiss

MATLAB mathematical toolbox documentation