Good afternoon, my experience in mathematical programming is low. I would like to know if there is any general method to address the following problem:

$$\text{Minimize }\sum_{i=1}^n d_i(x_j)$$ $$s.a.\quad Ax=b,$$ $$~~~~~~~~\qquad x\geq 0,$$ where $A$ is a matrix $m\times n$ with rank $m$, $x\in \mathbb{R}^n$, $b\in\mathbb{R}^m$, and \begin{equation*} d_j(x_j) = \begin{cases} 0, & \text{if $x_j= 0$},\\ d_jx_j+t_j, & \text{if $x_j> 0$}, \end{cases} \end{equation*} $d_j,x_j$ are constants.

Very grateful for your answers and references of the problem mentioned.


If $x_j \le u_j$ for some constant $u_j$, you can introduce a binary variable $y_j$, nonnegative variable $z_j$, and linear constraints: \begin{align} x_j &\le u_j y_j \\ d_j x_j + t_j - z_j &\le t_j(1-y_j) \end{align} The objective is then to minimize $\sum_{j=1}^n z_j$.

  • $\begingroup$ Thanks, could you give me some references? $\endgroup$
    – Rusbert
    Aug 20 '19 at 18:49
  • $\begingroup$ These are called big-M constraints. Here is a good blog post about them. $\endgroup$
    – RobPratt
    Aug 20 '19 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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