Optimal Binary Matrix solution

Hi,

I tried implementing the solution in this link Finding the optimal binary matrix to a test input as in the following code

a=[450;400;250;200]; % test input
b=[750;500]; % test input
n = 4; % length of a
m = 2; % length of b
oness=ones(m,1);
f = (kron(a,oness))'; % objective function
cont1=kron(eye(n),oness'); 
cont2=-cont1;
cont3=-kron(a',eye(m));
A=[cont1;cont2;cont3];
bb=[ones(n,1);-zeros(n,1);-b];
lb = zeros(m*n,1);
ub = [ones(m*n,1)]; % enforces binary
intcon= [1,2,3,4,5,6,7,8]; % all integer min solution 
 Aeq = [];
 beq = [];
x = intlinprog(f,intcon,A,bb,Aeq,beq,lb,ub)

However, I am getting

Intlinprog stopped because no integer points satisfy the constraints.

An obvious optimal solution for this test input would be x=[0;1;1;0;1;0;0;0].

However, if I remove the Integer constraint by keeping intcon=[], I get optimal solution. why the function cannot find minimum solution with Integer restriction?

Answer 1

[Mustafa]

I had a mistake in my problem definition. I have fixed it now. The code runs fine now. Below is the new code

a=[450;400;250;200]; % test input
b=[750;500]; % test input
n = 4;
m = 2;
oness=ones(m,1);
f = -(kron(a,oness))';
cont1=kron(eye(n),oness');
cont2=-cont1;
cont3=kron(a',eye(m));
A=[cont1;cont2;cont3];
bb=[ones(n,1);-zeros(n,1);b];
lb = zeros(m*n,1);
ub = [ones(m*n,1)]; % enforces binary
intcon= 1:8;
 Aeq = [];
 beq = [];
x = intlinprog(f,intcon,A,bb,Aeq,beq,lb,ub)

Answer 2

[Alan Weiss]

Your claimed solution does not satisfy your constraints.

A*[0;1;1;0;1;0;0;0]

 ans =

     1
     1
     1
     0
    -1
    -1
    -1
     0
  -650
  -450

But the constraint is A*x <= bb, and bb is:

 bb =

     1
     1
     1
     1
     0
     0
     0
     0
  -750
  -500

So the "solution" does not satisfy the last two constraints.

Alan Weiss

MATLAB mathematical toolbox documentation

[Mustafa]

it should be a*[0;1;1;0;1;0;0;0] not A*[0;1;1;0;1;0;0;0]

and Xa≥b not A*x <= bb

[Alan Weiss]

You wrote

x = intlinprog(f,intcon,A,bb,Aeq,beq,lb,ub)

With your problem setup, the interpretation of A and bb is A*x <= bb. If your problem is different than you stated, then please state the correct problem for which you are having difficulty.

Alan Weiss

MATLAB mathematical toolbox documentation

[Mustafa]

Ah sorry I miss interrupted your answer. You are correct. The constraint that I was referring in my comments is for my problem in the Link. How can I modify the setup here to match my requirement.

[Mustafa]

I had a mistake in my problem definition. I have fixed it now. The code runs fine now. I am posting the new code as an answer. Thanks Alan for your feedback.