Intlinprog, how to make sure certain criteria must be met

Hi. I have a problem with intlinprog. Below is the matrices A that I want to solve.

A = [1 0 1 0; 0 1 1 0; 1 1 1 1; 0 0 1 1];
f=[1 1 1 1];
b=[1 1 1 1];
intcon=1:4;
Aeq=[];
beq=[];
lb=zeros(4,1);
ub=ones(4,1);

[x,xfval,exitflag,output]=intlinprog(f,intcon,-A,-b,Aeq,beq,lb,ub);

The solution intlinprog gave me is x={3}, but I would like the solution to be x={1,2} which mean 4 is reachable if 1 and 2 (which connected to 3) are both selected. The solution can also be x={1,4} or x={2,4}. Is there a way I can make this possible? Thank you!

EDIT: Let me rephrase my question. Node 3 act like a switch that can only be enabled if at least 2 nodes that connected to it are active. When that happens, the last node can be reached. For e.g, from the diagram below, if 1,2 are active, 4 can be reached. Same can also be said if 1,4 are active, 2 can be reached. 3 obviously shouldn't be the solution.

Answer 1

[Alan Weiss]

It is very difficult to understand what you are seeking. You gave a complete problem specification. intlinprog gave you the correct answer. Now you are asking if you could get a different answer.

What this means to me is that you want to change your problem specification in a way that gives you the answer that you want. I do not know what you consider a legal change to your problem specification. For example, I could specify

 lb = [1,0,0,1]
 ub = [1,0,0,1]

to force intlinprog to give the answer that you want. But I suspect that you would not like this change, and would call it illegal.

So my question is, what is a legal change to your problem formulation? intlinprog returns an answer that is a global optimum to your original formulation, so if you don't like it you must have left something out of your problem formulation, but how can we know what you left out?

Alan Weiss

MATLAB mathematical toolbox documentation

[maoster]

Hi, thanks for your reply. Let me rephrase my question. Node 3 act like a switch that can only be enabled if at least 2 nodes that connected to it are active. When that happens, the last node can be reached. For e.g, from the diagram below, if 1,2 are active, 4 can be reached. Same can also be said if 1,4 are active, 2 can be reached. 3 obviously shouldn't be the solution.

[Alan Weiss]

You need to reformulate your problem. The first row of A specifies that at least one of x(1) and x(3) is equal to 1. The second row specifies that at least one of x(2) and x(3) is equal to 1. The third row specifies that at least one x(i) is equal to 1. The fourth row specifies that at least one of x(3) and x(4) is equal to 1. And the cost vector f states that the fewest possible number of x(i) should be positive.

So from the specification of your f, A, and b, it is clear that intlinprog solved the problem correctly.

I don't know what problem you are really trying to solve, what the real objective and constraints should be. If you state your objective in words then maybe we can help you formulate your problem.

Alan Weiss

MATLAB mathematical toolbox documentation