Skip to main content
23 votes
Accepted

How to minimize an absolute value in the objective of an LP?

Alternatively, by observing that $|c \cdot x|= \max \{c^T x, -c^T x\}$, $$\min_x |c\cdot x| \text{ subject to } Ax \le b$$ can be rewritten as $$\min_x \max \{c^T x, -c^T x\} \text{ ...
Siong Thye Goh's user avatar
14 votes
Accepted

Working with absolute values in constraint in a LP or MILP

You need to model disjunctive constraints. I will assume that variable $x$ is constrained to lie in $L_1 \le x \le U_1$ or $L_2 \le x \le U_2$. For instance, if you have the constraint $2 \le |x| \...
Mark L. Stone's user avatar
10 votes

How to minimize an absolute value in the objective of an LP?

This is possible by introducing 2 new variables, $t_1,t_2$, and adding a few constraints: $\begin{align} \min t_1+t_2 \quad \text{s.t.} \quad t_1-t_2 &= c\cdot x\\ t_1&\geq 0 \\ t_2&\geq ...
Discrete lizard's user avatar
9 votes
Accepted

How to minimize the sum of absolute values

You can use the same approach as in the linked question, but with a separate variable for each summand. Explicitly, minimize $\sum_i z_i$ subject to \begin{align} Ax&\ge b\\ z_i&\ge x_i &&...
RobPratt's user avatar
  • 32.7k
7 votes

How to minimize an absolute value in the objective of an LP?

I would like to suggest a different angle using the epigraphical relaxation of the absolute value. In particular, $$ |z| = \min_{|z|\leq t}t = \min_{-t \leq z \leq t}t $$ Using this observation, ...
Pantelis Sopasakis's user avatar
7 votes

Absolute value in an equality constraint

If the objective function and the remaining constraints are such that the solver will always prefer smaller values of $x$ over larger values, you can get by with two constraints: $x\ge y$ and $x\ge -y....
prubin's user avatar
  • 39.5k
6 votes
Accepted

linearizing a constraint involving an absolute function

Note that this is the same relationship as $x \text{ xor } y=z$. You want to enforce four logical implications: \begin{align} x \land y &\implies \lnot z \\ x \land \lnot y &\implies z \\ \...
RobPratt's user avatar
  • 32.7k
6 votes
Accepted

Multiple absolute values with multiple variables in an LP

Yes, the usual technique applies. Introduce a variable $z_j$ (together with linear constraints) to represent the absolute value, and replace the original constraint with $\sum_j (c_j x_j + z_j) \le y$...
RobPratt's user avatar
  • 32.7k
4 votes

Linearizing objective function with absolute differences

Introduce a new variable $z_{i,j}$ to represent the summand, and apply the linearization of $\max$ described here. Explicitly, the problem is to maximize $\sum_{i=1}^{N-1} \sum_{j=i+1}^N z_{i,j}$ ...
RobPratt's user avatar
  • 32.7k
1 vote

How to write constraint with sum of absolutes in Integer Programming?

In CPLEX you can use the absolute value. For instance with the OPL API you can write ...
Alex Fleischer's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible