Why am I getting Infeasible Solution for Location Problem?

Hello,

I am trying to code a simple location p-median problem but I get the following error:

% Solve LP relaxation of p-median using Yalmip

%define data
D = [1  391.9764182 451.2118249 396.276789  222.1349002 196.7985877 411.1001954 258.2849469;
391.9764182 1   210.5685407 105.6487042 262.3794509 201.4011567 37.42638481 257.8745973;
451.2118249 210.5685407 1   107.6389846 418.7416764 272.3862831 178.9988058 428.5756481;
396.276789  105.6487042 107.6389846 1   323.9965151 202.4993001 78.53748028 329.5799849;
222.1349002 262.3794509 418.7416764 323.9965151 1   175.1783494 295.0366141 37.37528766;
196.7985877 201.4011567 272.3862831 202.4993001 175.1783494 1   216.7141787 200.0632283;
411.1001954 37.42638481 178.9988058 78.53748028 295.0366141 216.7141787 1   292.3665484;
258.2849469 257.8745973 428.5756481 329.5799849 37.37528766 200.0632283 292.3665484 1];
p = 1;

%define variables
x = binvar(8,8);
y = binvar(8,1);

%define constraints
F = [sum(y)== p; x <= repmat(y',8,1); sum(x)==1];

%define obj
obj = sum(sum(D.*x));

%solve;default is minimize
solvesdp(F,obj);

LP:                Optimal objective value is 1741.192845.                                          
Cut Generation:    Applied 1 Gomory cut, 1 strong CG cut,                                           
                   and 1 zero-half cut.                                                             
                   Lower bound is 14621.979434.                                                     
No feasible solution found.
Intlinprog stopped because no integer points satisfy the constraints.

D is my 8x8 distance matrix. I am looking for P=1 (1 node/hub). X and Y should be binary. Sum of Y's should equal P. Sum of X's should equal 1. If Y is on, X should be turned on.

Please help! Thanks!

Answer 1

[Alan Weiss]

While I know nothing about Yalmip, and do not really follow your problem setup, the error message is clear: it seems that there is no integer feasible point. So try solving the problem with a 0 objective function, just to be sure. Then try solving it with no integer constraints, but leave the other constraints such as bounds in the problem, to see if there is a noninteger feasible point. Also, try figuring out an integer feasible point just from your understanding of the problem, and see whether that point satisfies the constraints of the problem as you gave them.

It is not always easy to diagnose why a problem is infeasible.

Alan Weiss

MATLAB mathematical toolbox documentation