This can be formulated and solved as a Mixed Integer Linear Programming (MILP) feasibility problem. Such NP-hard problems are routinely solved in practice, even to fairly large scale, despite being "intractable". For $P$ being $n$ by $n$ with $n$ in the hundreds, it should be easy to solve, and possible with $n$ into the thousands.

The problem is to find a $P$ such that all entries of $P$ are $0$ or $1$, all rows of $P$ sum to $1$, all columns of $P$ sum to $1$, and $APx = 0$.

Formulation in CVX under MATLAB

cvx_begin
variable P(n,n) binary
sum(P,1) == 0
sum(P,2) == 0
A*P*x == 0
cvx_end

Formulation in YALMIP under MATLAB

P = binvar(n,n,'full')
optimize([sum(P,1) == 0,sum(P,2) == 0,A*P*x == 0])

The specific solver to use may be optionally specified for either CVX or YALMIP.

I don't claim this is the fastest way to solve the problem, but it is a valid formulation, and if it meets your needs, then it has accomplished something useful, protestations of NP-completeness not withstanding.

This can be formulated and solved as a Mixed Integer Linear Programming (MILP) feasibility problem. Such NP-hard problems are routinely solved in practice, even to fairly large scale, despite being "intractable". For $P$ being $n$ by $n$ with $n$ in the hundreds, it should be easy to solve, and possible with $n$ into the thousands.

The problem is to find a $P$ such that all entries of $P$ are $0$ or $1$, all rows of $P$ sum to $1$, all columns of $P$ sum to $1$, and $APx = 0$.

Formulation in CVX under MATLAB

cvx_begin
variable P(n,n) binary
sum(P,1) == 1
sum(P,2) == 1
A*P*x == 0
cvx_end

Formulation in YALMIP under MATLAB

P = binvar(n,n,'full')
optimize([sum(P,1) == 1,sum(P,2) == 1,A*P*x == 0])

The specific solver to use may be optionally specified for either CVX or YALMIP.

I don't claim this is the fastest way to solve the problem, but it is a valid formulation, and if it meets your needs, then it has accomplished something useful, protestations of NP-completeness not withstanding.

This can be formulated and solved as a Mixed Integer Linear Programming (MILP) feasibility problem. Such NP-hard problems are routinely solved in practice, even to fairly large scale, despite being "intractable". For $P$ being $n$ by $n$ with $n$ in the hundreds, it should be easy to solve, and possible with n into the thousands.

The problem is to find a $P$ such that all entries of $P$ are $0$ or $1$, all rows of $P$ sum to $1$,all columns of $P$ sum to $1$, and $APx = 0$.

Formulation in CVX under MATLAB

cvx_begin
variable P(n,n) binary
sum(P,1) == 0
sum(P,2) == 0
A*P*x == 0
cvx_end

Formulation in YALMIP under MATLAB

P = binvar(n,n,'full')
optimize([sum(P,1) == 0,sum(P,2) == 0,A*P*x == 0])

Specific solver to use may be optionally specified for either CVX or YALMIP.

I don't claim this is the fastest way to solve the problem, but it is a valid formulation, and if it meets your needs, then it has accomplished something useful, protestations of NP-completeness not withstanding.

This can be formulated and solved as a Mixed Integer Linear Programming (MILP) feasibility problem. Such NP-hard problems are routinely solved in practice, even to fairly large scale, despite being "intractable". For $P$ being $n$ by $n$ with $n$ in the hundreds, it should be easy to solve, and possible with $n$ into the thousands.

The problem is to find a $P$ such that all entries of $P$ are $0$ or $1$, all rows of $P$ sum to $1$, all columns of $P$ sum to $1$, and $APx = 0$.

Formulation in CVX under MATLAB

cvx_begin
variable P(n,n) binary
sum(P,1) == 0
sum(P,2) == 0
A*P*x == 0
cvx_end

Formulation in YALMIP under MATLAB

P = binvar(n,n,'full')
optimize([sum(P,1) == 0,sum(P,2) == 0,A*P*x == 0])

The specific solver to use may be optionally specified for either CVX or YALMIP.

I don't claim this is the fastest way to solve the problem, but it is a valid formulation, and if it meets your needs, then it has accomplished something useful, protestations of NP-completeness not withstanding.