4
$\begingroup$

I want to add two constraints as follows in my linear programming model:

one constraint is defined as: A-B=C-D, and another constraint is defined as: A+B=|C-D|, where A, B, and C are decision variables in the model, A>=0. B>=0 and C>=0, and D is a positive number given by the model. how to formulate the second constraint in the model?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ By breaking the problem into cases. This question is not research level, so I am voting to close. See mathoverflow.net/faq . $\endgroup$
    – user5810
    Commented Jan 14, 2011 at 5:12
  • 1
    $\begingroup$ @Ricky Demer: The question is indeed an elementary one, but the answer is not so straightforward. In math programming, there are many formulation subtleties that have different properties despite representing the same mathematical idea. For instance, the absolute function $|C-D|$ can either be formulated using a non-smooth function $\max{C-D,D-C}$, as indicator constraints, as MIP constraints (if the upper-bound of C is known, a convex hull constraint can be derived), or in some cases, just by introducing a penalty in the objective function. $\endgroup$
    – Gilead
    Commented Jan 14, 2011 at 5:46
  • 1
    $\begingroup$ or, by doing what I said, and breaking the problem into cases. $\endgroup$
    – user5810
    Commented Jan 14, 2011 at 5:56
  • 1
    $\begingroup$ Yes, what you're suggesting is essentially full enumeration (worst-case scenario). That's easily done if indeed there are only a few cases (that is, the OP's specific case, exactly 1 absolute function... literally), but in the general case, that strategy is inefficient when there are hundreds of constraints of this nature. Reformulating the problem as an MIP allows one to take advantage of branch-and-bound algorithms which can potentially avoid full enumeration. Most modern solvers have heuristics that exploit structure, so the average case is often better than the worst case. $\endgroup$
    – Gilead
    Commented Jan 14, 2011 at 6:44

1 Answer 1

Reset to default
7
$\begingroup$

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.

The bad ways

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 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).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Why is the standard LP approach a poor one? I've seen it recommended elsewhere, so I'm curious. $\endgroup$
    – arsmath
    Commented Jan 14, 2011 at 7:44
  • 2
    $\begingroup$ Well, the problem with penalty methods is if there is a sufficiently high cost preventing $z$ from reaching its minimum, then the answer will be incorrect. Consider an extreme case where $\Phi = -2z$ (a bit unrealistic I know, but just to make a point). The objective then becomes $\min -z = \max z$, which is problematic because in the formulation, the slacks are unbounded and there exists a nullspace of solutions. Balancing the penalty and the original objective is often tricky and unreliable, which is why penalty methods for absolutes are often not favored. $\endgroup$
    – Gilead
    Commented Jan 14, 2011 at 15:19
  • 1
    $\begingroup$ Gilead, many thanks for this answer. It has convinced me there is more to these problems than I thought I understood. $\endgroup$
    – Andrés E. Caicedo
    Commented Jan 14, 2011 at 17:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .