You can download YALMIP for free http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Main.Download . YALMIP will do the dirty work for you. Install YALMIP, run yalmiptest to test installation, read http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.Basics . If you have CPLEX available and installed under MATYLAB, it will/can use that, otherwise something else. The L need not be psd in order to solve under YALMIP using CPLEX or scip as the solver. However, you stated it is a Laplacian matrix, therefore is must be psd.
n = length(P); % this is not really YALMIP code
x = binvar(n,1) % declare x as binary; would use sdpvar instead for continuous variable
sol = optimize([Ax<=b,Ax==b,lb<=x<=ub],x'*L*x+abs(P'*x))
is complete YALMIP code to solve this. After being solved, value(x) provides the optimal value of x.
If you want to specify a particular solver, for instance scip, rather than letting YALMIP pick the solver, use the form
sol = optimize([Ax<=b,Ax==b,lb<=x<=ub],x'Lx+abs(P'*x), sdpsettings('solver','scip'))
You don't need to put into generic format. YALMIP handles that for you "under the hood" to put in form suitable for solvers. Just put in the constraints you have. If you don't have any constraints other than x being binary, you can use  instead of [Ax<=b,Ax==b,lb<=x<=ub] . Also note that sdpvar doesn't mean that x is being declared to be senidefinite. The declaration is a holdover from when YALMIP only addressed SDPs.