How to transfer an objective with separate positive and negative parts into linear programming

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?

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

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.$$
• 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. Dec 23, 2023 at 11:56
• @A.Omidi Suppose that $(Kx)_j < 0.$ If you set $y_j = u_j,$ you reduce the objective by the largest amount possible.
• Dear @prubin, thanks. I actually supposed the variable $x \geq 0$. đź™Ź Dec 23, 2023 at 19:21
• @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.
• @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. Jan 15 at 13:36