# Linear Integer Programming with absolute values in objective function

I'm trying to solve a problem of the form $$\left|a_{1,0}+a_{1,1} x_1 + a_{1,2}x_2\right| + \left|a_{2,0}+a_{2,1} x_1 + a_{2,2}x_2\right|\to\min,$$

where $a_{i,j}$ are real-valued coefficients and the $x_i$ are integers. In fact, in my real problem, their are more variables and the problem looks like this: $$\sum_{i=1}^n\left|a_{i,0}+\sum_{j=1}^ma_{i,j}x_j\right|\to\min,$$ Is there an easy way to transform this into an linear integer programming probably suitable for Mathematica? I'm not sure how to deal with the absolute values in the objective functions, and how to convert the problem into matrix form.

Thanks.

Edit:

As a concrete example, consider the function

f = (x (-9 + 6 x - 8 x^2 + 3 x^3))/(4 (-3 + 3 x - 3 x^2 + x^3)) + 0.0002 Sin[50 x] + 0.0002 Sin[100 x]


which is known on the grid $0,.01,\ldots,1$. Defining

data=Table[{x,f},{x,0,1,.01}]


the problem is to recover the coefficients of $f$ from $data$, knowing that $f$ is a perturbed rational function with integer coefficients of bounded magnitude.

If $f$ was not perturbed then

<< FunctionApproximations
RationalInterpolation[f, {x, 4, 3}, {x, 0, 1}]


could be used recover the coefficients (or a variant that specifies the $x_i$)

Does the a priori information that the coefficients are integers allow exact reconstruction of $f$ despite the perturbation?

• Please, provide a minimum working example code for us to start working on your problem. – Sektor Aug 20 '13 at 18:25
• Thank you @NikolaDimitrov. I edited the question and added an example. – Eckhard Aug 20 '13 at 20:37
• For each abs you can define a new variable and inequalities e.g. {anew >=a10 + a11*x1+a12*x2, anew >= -(a10 + a11*x1+a12*x2)}. If you are minimizing a sum of these absolute values then this tactic should suffice since you simply get a conjunction of new inequality constraints. – Daniel Lichtblau Aug 20 '13 at 21:13

## 1 Answer

You could proceed as below. Note that in thsi instance we do not recover the desired result. I'm not sure what is the cause though it could have to do with the numerator extraction that went into linearizing.

f = (x (-9 + 6 x - 8 x^2 + 3 x^3))/(4 (-3 + 3 x - 3 x^2 + x^3)) +
0.0002 Sin[50 x] + 0.0002 Sin[100 x];

data = Table[{x, f}, {x, 0, 1, .01}];
pow = 4;
nvars = Array[n, pow + 1, 0];
dvars = Array[d, pow, 0];
rat = nvars.x^Range[0, pow]/dvars.x^Range[0, pow - 1];

vals = Numerator[
Together[(rat /. x -> data[[All, 1]]) - data[[All, 2]]]];
newvars = Array[nv, Length[vals]];
ndvars = Join[nvars, dvars];
c1 = Element[ndvars, Integers];
c2 = n >= 1;
newcons =
Flatten[MapIndexed[{#1 >=
vals[[#2[]]], #1 >= -vals[[#2[]]]} &, newvars]];
cons = Flatten[{c1, c2, newcons}];

Timing[{min, mvals} =
FindMinimum[{Total[newvars], cons}, Join[newvars, ndvars]];]

(* Out= {7.450000, Null} *)

In:= min

(* Out= 0.0911328776396 *)


Here is the resulting approximation.

Together[rat /. mvals]

(* Out= (6 x - x^2 + 4 x^3)/(8 - 4 x + 5 x^2) *)


In terms of error, it is not much worse than the desired function.

Map[
Total[Abs[# - data[[All, 2]]]] &, ({Together[
rat /. mvals], (x (-9 + 6 x - 8 x^2 + 3 x^3))/(4 (-3 + 3 x -
3 x^2 + x^3))} /. x -> data[[All, 1]])]

(* Out= {0.0333409066193, 0.0159968085248} *)
`

Anyway, this might give some idea of how one can attack such problems.