MATLAB Answers

Mixed Integer Linear Programming Problem

58 views (last 30 days)
Hafsa Farooqi
Hafsa Farooqi on 22 Dec 2020
Answered: Alan Weiss on 27 Dec 2020
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 Comments

Show 1 older comment
Hafsa Farooqi
Hafsa Farooqi on 23 Dec 2020
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
Walter Roberson on 23 Dec 2020
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
Hafsa Farooqi on 23 Dec 2020
@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?

Sign in to comment.

Answers (2)

Matt J
Matt J on 24 Dec 2020
Edited: Matt J on 24 Dec 2020
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).

  0 Comments

Sign in to comment.


Alan Weiss
Alan Weiss on 27 Dec 2020
You might find the following documentation useful:
Alan Weiss
MATLAB mathematical toolbox documentation

  0 Comments

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!