3 deleted 1 characters in body

This is really a question for http://www.or-exchange.com (since the answer requires practical know-how rather than mathematical abillity). However, since linear programming questions are of some interest to some folks here, I'll make an attempt at an answer that is not completely useless.

There are many ways of formulating an absolute function in an LP (some bad, some good). I'm going to discuss the bad ways, in case you are tempted to use them.

You can try these approaches, but bear in mind that they are not rigorous unless the absolute function is the sole term in the objective (I believe the $l_{1}$-norm LP in compressed sensing fulfills this criterion).

As far as I am aware, there is no 100% reliable way of formulating an absolute function that appears in the constraint set in an LP and if there exists a competing objective $\Phi$.

• The standard LP approach that is often used (but IMHO, is a poor method) is as follows: introduce a dummy variable $z$ (that is, $z=|C - D|$) and nonnegative slack variables $s_{0},s_{1}$. Write the LP as below: \begin{align} &\min \Phi + z\\ s.t.\;\; & z = s_{0} + s_{1}\\ & C - D = s_{0} - s_{1}\\ & s_{0} \geq 0, s_{1} \geq 0\\ & A - B = C - D\\ &A + B = z \end{align} where $\Phi$ is the original objective. In theory, this seems like it will work, but in practice, depending on how the other constraints are posed, and the "downward pressure" of $z$ with respect to $\Phi$, this might not always give you the correct answer. For instance, if $\Phi$ makes the absolute function $z$ tend toward a non-minimum value, it will depend on the weighting between $z$ and $\Phi$ to determine which term "wins".

• A similar (but equally flawed) approach is to use the fact that $|C - D| = \max(C-D,D-C)$, and to write this: \begin{align} &\min \Phi + z\\ s.t.\;\; & z \geq D-C \\ & z \geq C-D\\ & A - B = C - D\\ &A + B = z \end{align}

The good ways (but your problem will no longer remain an LP)

The only reliable way to formulate an absolute function in the constraint set is to reformulate your LP as MIP (Mixed Integer Program).

• If your solver supports indicator constraints, you can write the following: \begin{align} &\min \Phi\\ s.t.\;\; & z \geq D - C\\ & z \geq C - D\\ & z \leq D - C\text{ or }z\leq C - D \\ & A - B = C - D\\ &A + B = z \end{align} where the "or" is handled as an indicator constraint. Most solvers will use a Big-M formulation to convert the problem into an MIP.

• The best way is to use a mixed-integer (MIP) formulation. In order to do that, you need to know the upper bound for $C \in [0,C^{U}]$. (Since $D$ is a known, we'll assume it is constant.) If you have no idea what the upper bound is, choose an adequately large value for $C^U$, bearing in mind that very large values of $C^{U}$ can cause conditioning problems. Also, the larger the $C^{U}$, the poorer your LP-relaxation for branching will be, which in turn will adversely impact the performance of the solution process. So choose $C^{U}$ carefully. First, define an upper-bound $U$ as follows, $U = \max(D,C^{U})$. Then write the following constraints:

\begin{align} &\min \Phi\\ s.t.\;\; & 0 \leq C \leq C^{U}\\ & 0 \leq z - (C - D) \leq (2U)\delta_{1}\\ & 0 \leq z - (D - C) \leq (2U)\delta_{2}\\ & \delta_{1} + \delta_{2} = 1\\ & A - B = C - D\\ &A + B = z \end{align} where $\delta_{1},\delta_{2} \in \{0,1\}$ (binary variables).

2 added 132 characters in body

This is really a question for http://www.or-exchange.com (since the answer requires practical know-how rather than mathematical abillity). However, since linear programming questions are of some interest to some folks here, I'll make an attempt at an answer that is not completely useless.

There are many ways of formulating an absolute function in an LP (some bad, some good). I'm going to discuss the bad ways, in case you are tempted to use them.

You can try these approaches, but bear in mind that they are not rigorous unless the absolute function is the sole term in the objective (I believe the $l_{1}$-norm LP in compressed sensing fulfills this criterion).

As far as I am aware, there is no 100% reliable way of formulating an absolute function that appears in the constraint set in an LP and there exists a competing objective $\Phi$.

• The standard LP approach that is often used (but IMHO, is a poor method) is as follows: introduce a dummy variable $z$ (that is, $z=|C - D|$) and nonnegative slack variables $s_{0},s_{1}$. Write the LP as below: \begin{align} &\min \Phi + z\\ s.t.\;\; & z = s_{0} + s_{1}\\ & C - D = s_{0} - s_{1}\\ & s_{0} \geq 0, s_{1} \geq 0 0\\ & A - B = C - D\\ &A + B = z \end{align} where $\Phi$ is the original objective. In theory, this seems like it will work, but in practice, depending on how the other constraints are posed, and the "downward pressure" of $z$ with respect to $\Phi$, this might not always give you the correct answer. For instance, if $\Phi$ makes the absolute function $z$ tend toward a non-minimum value, it will depend on the weighting between $z$ and $\Phi$ to determine which term "wins".

• A similar (but equally flawed) approach is to use the fact that $|C - D| = \max(C-D,D-C)$, and to write this: \begin{align} &\min \Phi + z\\ s.t.\;\; & z \geq D-C \\ & z \geq C-D C-D\\ & A - B = C - D\\ &A + B = z \end{align}

The good ways (but your problem will no longer remain an LP)

The only reliable way to formulate an absolute function in the constraint set is to reformulate your LP as MIP (Mixed Integer Program).

• If your solver supports indicator constraints, you can write the following: \begin{align} &\min \Phi\\ s.t.\;\; & z \geq D - C\\ & z \geq C - D\\ & z \leq D - C\text{ or }z\leq C - D \\ & A - B = C - D\\ &A + B = z \end{align} where the "or" is handled as an indicator constraint. Most solvers will use a Big-M formulation to convert the problem into an MIP.

• The best way is to use a mixed-integer (MIP) formulation. In order to do that, you need to know the upper bound for $C \in [0,C^{U}]$. (Since $D$ is a known, we'll assume it is constant.) If you have no idea what the upper bound is, choose an adequately large value for $C^U$, bearing in mind that very large values of $C^{U}$ can cause conditioning problems. Also, the larger the $C^{U}$, the poorer your LP-relaxation for branching will be, which in turn will adversely impact the performance of the solution process. So choose $C^{U}$ carefully. First, define an upper-bound $U$ as follows, $U = \max(D,C^{U})$. Then write the following constraints:

\begin{align} &\min \Phi\\ s.t.\;\; & 0 \leq C \leq C^{U}\\ & 0 \leq z - (C - D) \leq (2U)\delta_{1}\\ & 0 \leq z - (D - C) \leq (2U)\delta_{2}\\ & \delta_{1} + \delta_{2} = 1 1\\ & A - B = C - D\\ &A + B = z \end{align} where $\delta_{1},\delta_{2} \in \{0,1\}$ (binary variables).

1

This is really a question for http://www.or-exchange.com (since the answer requires practical know-how rather than mathematical abillity). However, since linear programming questions are of some interest to some folks here, I'll make an attempt at an answer that is not completely useless.

There are many ways of formulating an absolute function in an LP (some bad, some good). I'm going to discuss the bad ways, in case you are tempted to use them.

You can try these approaches, but bear in mind that they are not rigorous unless the absolute function is the sole term in the objective (I believe the $l_{1}$-norm LP in compressed sensing fulfills this criterion).

As far as I am aware, there is no 100% reliable way of formulating an absolute function that appears in the constraint set in an LP and there exists a competing objective $\Phi$.

• The standard LP approach that is often used (but IMHO, is a poor method) is as follows: introduce a dummy variable $z$ (that is, $z=|C - D|$) and nonnegative slack variables $s_{0},s_{1}$. Write the LP as below: \begin{align} &\min \Phi + z\\ s.t.\;\; & z = s_{0} + s_{1}\\ & C - D = s_{0} - s_{1}\\ & s_{0} \geq 0, s_{1} \geq 0 \end{align} where $\Phi$ is the original objective. In theory, this seems like it will work, but in practice, depending on how the other constraints are posed, and the "downward pressure" of $z$ with respect to $\Phi$, this might not always give you the correct answer. For instance, if $\Phi$ makes the absolute function $z$ tend toward a non-minimum value, it will depend on the weighting between $z$ and $\Phi$ to determine which term "wins".

• A similar (but equally flawed) approach is to use the fact that $|C - D| = \max(C-D,D-C)$, and to write this: \begin{align} &\min \Phi + z\\ s.t.\;\; & z \geq D-C \\ & z \geq C-D \end{align}

The good ways (but your problem will no longer remain an LP)

The only reliable way to formulate an absolute function in the constraint set is to reformulate your LP as MIP (Mixed Integer Program).

• If your solver supports indicator constraints, you can write the following: \begin{align} &\min \Phi\\ s.t.\;\; & z \geq D - C\\ & z \geq C - D\\ & z \leq D - C\text{ or }z\leq C - D \end{align} where the "or" is handled as an indicator constraint. Most solvers will use a Big-M formulation to convert the problem into an MIP.

• The best way is to use a mixed-integer (MIP) formulation. In order to do that, you need to know the upper bound for $C \in [0,C^{U}]$. (Since $D$ is a known, we'll assume it is constant.) If you have no idea what the upper bound is, choose an adequately large value for $C^U$, bearing in mind that very large values of $C^{U}$ can cause conditioning problems. Also, the larger the $C^{U}$, the poorer your LP-relaxation for branching will be, which in turn will adversely impact the performance of the solution process. So choose $C^{U}$ carefully. First, define an upper-bound $U$ as follows, $U = \max(D,C^{U})$. Then write the following constraints:

\begin{align} &\min \Phi\\ s.t.\;\; & 0 \leq C \leq C^{U}\\ & 0 \leq z - (C - D) \leq (2U)\delta_{1}\\ & 0 \leq z - (D - C) \leq (2U)\delta_{2}\\ & \delta_{1} + \delta_{2} = 1 \end{align} where $\delta_{1},\delta_{2} \in \{0,1\}$ (binary variables).