2
$\begingroup$

I've got to deal with an optimization problem as follows, $$ \begin{aligned} \max_{x,y} & a^Tx+y^TKx\\ {s.t.}&Ax=b\\ &{Cx}\leq d\\ l&\leq y\leq u\end{aligned} $$ where $x \in \bf{R}^n$, $y \in \bf{R}^m$. An intuitive is that as $y$ is bounded in $[l,u]$, the later term in the objective ($y^TKx$) can be rewritten as $$ \sum_{j=1}^{m}\{\max\{(Kx)_j,0\}u_j+\min\{(Kx)_j,0\}l_j\} $$ How can I incorporate the above expression in the optimization problem to avoid bilinear term?

$\endgroup$
2
  • $\begingroup$ Are you willing to introduce binary variables and solve a mixed integer linear program? $\endgroup$
    – prubin
    Dec 21, 2023 at 17:12
  • $\begingroup$ @prubin Sure. Can you tell me how to do? $\endgroup$ Dec 22, 2023 at 1:54

1 Answer 1

2
$\begingroup$

I'm going to assume that $\ell \ge 0.$ We introduce nonnegative variables $0\le w,z \in \mathbb{R}^m$ and binary variables $v\in \lbrace 0, 1 \rbrace^m$ and convert the objective to maximizing $a^T x + u^T w - \ell^T z.$ We also add the following constraints, where $M_j$ is a valid upper bound on $\vert (Kx)_j \vert:$ $$Kx - w + z = 0$$ $$w_j \le M_j v_j \quad\forall j$$ $$z_j \le M_j (1-v_j) \quad \forall j.$$

$\endgroup$
8
  • $\begingroup$ Dear @prubin, why not try to just set $y$ in its upper bound? As the problem is of the form maximization, the value of the variable $y$ will take its upper bound. Otherwise, if the domain of the variable $y$ was not unbounded, the problem may be unbounded. $\endgroup$
    – A.Omidi
    Dec 23, 2023 at 11:56
  • 1
    $\begingroup$ @A.Omidi Suppose that $(Kx)_j < 0.$ If you set $y_j = u_j,$ you reduce the objective by the largest amount possible. $\endgroup$
    – prubin
    Dec 23, 2023 at 16:49
  • $\begingroup$ Dear @prubin, thanks. I actually supposed the variable $x \geq 0$. 🙏 $\endgroup$
    – A.Omidi
    Dec 23, 2023 at 19:21
  • 1
    $\begingroup$ @A.Omidi $x\ge 0$ might well be intended, but the key is whether $Kx \ge 0,$ and I see no reason to assume that. $\endgroup$
    – prubin
    Dec 23, 2023 at 19:33
  • $\begingroup$ @prubin Thank you. I also want to ask is the original problem equivalent to the folloing formulation: $$ \begin{aligned} \max_{x,y} & a^Tx+1^Tt\\ {s.t.}&Ax=b\\ &{Cx}\leq d\\ &Kx - w + z = 0\\ & w_j l_j-z_j u_j \leq t_j \leq w_j u_j - z_jl_j\\ & 0 \leq w_j, z_j \leq M_j \end{aligned} $$ where $M_j$ is a big M number. $\endgroup$ Jan 15 at 13:36

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.