2
$\begingroup$

would you please help me to solve following problem

$$x^*= \text{argmin}\ xLx^T+ |P^Tx|$$

  • $x$ is binary
  • $P$ is a known vector (with positive and negative values)
  • $L$ is Laplacian matrix

I have limited knowledge on optimization. As I read on the web, I can solve the problem with quadratic MILP if there was no absolute value for the second element of the objective function.

Question: Since $P$ is not a constant positive value, how can get rid of the absolute value?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

You can reformulate this as

$x^{*}=\arg \min x^{T}Lx+ t $

subject to

$t \geq P^{T}x $

$t \geq -P^{T}x $

$x \in \left\{ 0, 1 \right\}^{n}$

This is a 0-1 mixed integer quadratic programming problem (MIQP) The case where $L$ is positive definite is well handled by solvers like CPLEX.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks a lot for your answer. I'm using OPTI Toolbox for MATLAB. I guess this example must be the one I should follow, right? i2c2.aut.ac.nz/Wiki/OPTI/index.php/Probs/MIQP But would you please let me know how should I define t? And also how should I define constraint considering generic form of the example? $\endgroup$
    – Ahad Esmaeilian
    Commented Jun 11, 2015 at 20:57
  • $\begingroup$ t is an auxilliary variable added to the problem. If you just want a single vector of variables, then you can use $x_{n+1}$ as $t$ (and not put a 0-1 restriction on that variable.) It appears that OPTI with SCIP can solve these MIQP's, even if L is not positive definite. $\endgroup$
    – Brian Borchers
    Commented Jun 11, 2015 at 21:08
  • $\begingroup$ x* = arg min xT L x + f x subject to Ax<=b Ax=b lb<=x<=ub x∈{0,1} I mean, how can I map reformulated problem to this generic format which seems to be the only way I can give input to OPTI $\endgroup$
    – Ahad Esmaeilian
    Commented Jun 11, 2015 at 21:18
  • $\begingroup$ Make the extra $t$ variable $x_{n+1}$. Expand $L$ to be of size $n+1$ by $n+1$ by adding an extra row of 0's and an extra column of 0's. The linear inequality constraints are easy to put in the form Ax<=b. Make sure that $x_{n+1}$ isn't marked as a binary variable. $\endgroup$
    – Brian Borchers
    Commented Jun 11, 2015 at 22:45
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.