1

If linear programming is to be used to solve an objective function which contains absolutes then the absolute terms have to be rewritten using extra values, for example, the trivial objective "minimise $\left| x_1 + x_2 \right|$" becomes:

$$\begin{align} \mathrm{minimise}\ \ & t_1 \\ \mathrm{constraints}\ \ & x_1 + x_2 \le t_1 \\ & x_1 + x_2 \ge -t_1 \\ \end{align}$$

I'm currently rewriting this sort of thing as below in order to use the standard lp_solve solver (the objective and constraints must be expressed as a matrix of constants, and the constraint RHS must be a constant):

$$\begin{align} \mathrm{minimise}\ \ & 0x_1 + 0x_2 + 1x_3 \\ \mathrm{constraints}\ \ & 1x_1 + 1x_2 - 1x_3 \le 0 \\ & 1x_1 + 1x_2 + 1x_3 \ge 0 \\ \end{align}$$

Is this approach, with an extra decision variable plus two extra constraints for every absolute term in the objective, the best way to use lp_solve or is there a better way to rearrange things? The real problems I'm trying to solve have four to seven absolute parts and so the number of extra variables and constraints does start to mount up.

Asher Hoskins
  • 13

1 Answers1

1

You are going about it the right way. Four to seven absolute values will give you ~7 extra decision variables and ~14 extra constraints. That is quite small for an LP. It might start to get tedious to code it in this way, but from the solver's point of view, it is trivial. (If it does start to get too tedious, you might be better off using a modeling language like AMPL or GAMS, or a Python package for math modeling like PuLP or gurobipy.)

By the way: There is an effort to start a SE site for Operations Research, which mathematical programming questions like this will be a great fit for.

LarrySnyder610
  • 1,131