3
$\begingroup$

I have the following optimization problem in $x$

$$\begin{array}{ll} \text{minimize} & \max (K_1+x,0)+ K_2 x\\ \text{subject to} & \quad x \in \mathcal{P}\end{array}$$

Is there any trick to handle $\max(\cdot,0)$ and convert this optimization problem into a linear program?

$\endgroup$
  • $\begingroup$ In fact, the objective in a LP can always be taken to be a single variable (by adding an extra variable as necessary). $\min\{\max(a,b,c...) | ...\}$ is equivalent to $\min\{ \alpha | a \le \alpha, b \le \alpha, ... , ... \}$. $\endgroup$ – copper.hat Feb 17 '14 at 5:48
3
$\begingroup$

This can be easily achieved by adding one dummy variable. \begin{align} \min_P \quad &(\max (K_1+P,0)+ K_2 P)\\ P &\in \mathcal{P}\\& \Updownarrow\\ \min_P\quad &t+K_2P\\P&\in \mathcal{P}\\t&\geq K_1+P\\t&\geq0 \end{align}

$\endgroup$
  • $\begingroup$ What would the variable t become in a maximization model to avoid unboundedness? $\endgroup$ – FarahFai Jun 5 '18 at 15:09

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.