How to solve an ILP problem with conditions in an objective function?

Question

I have came accross this link.

I have an integer linear programming (ILP) problem
$$\max_{(x_1, x_2,\ldots, x_n)}\sum_{i=1}^n x_i\cdot f(x_i),$$

$$\text{subject to } \begin{cases} ..., &(1)\\ L≤x_i≤U,&(2)\\ x_i \in \mathbb{Z}, i \in I,&(3)\\ \end{cases} $$ here $X=\{x_i \in \mathbb{Z}: L \le x_i \le U, L<0, U>0, i\in I\}$ is the variable, $I=\{1,2, \ldots, n\}$ is the set of indicies, the function $f(x_i)$ is defined as $$f(x_i) = \begin{cases} a_i \in A, &\text{if } x_i>0, \\ b_i, \in B, &\text{if } x_i<0.\\ \end{cases} $$ $A=\{a_i \in \mathbb{R}^+: a_i<a_{i+1}, \forall i= 1, 2, \ldots, n-1\}$, $B=\{b_i \in \mathbb{R}^+: b_i<b_{i+1}, \forall i=1,2,\ldots, n-1\}$ are the input (ordered) constants, such that $b_i < a_i, i \in I$. In the system of constraints mentioned above the Eq.(1) means some extra constraints.

As the result I'd like to have the optimal solution $X^*$ and corresponded values of the $n$ input constants $a_i$ and $b_i$, $i \in I$.

Question. How to solve an ILP problem with the function $f(\cdot)$ in the objective function?

Update 4.

I think, I can obtain the result with next steps:

1) make a precomputing of the input constants: $C=\{c_{ji}, i \in I, j \in J\}$ is the set of permutations of $a_i$ and $b_i$, $J=\{1,2,\dots, 2^n\}$.

Let's $A=(2.2, 4.4, 6.6)$ and $B=(1.1, 3.3, 5.5)$ then $$C=\left(% \begin{array}{ccc} 1.1 & 3.3 & 5.5 \\ 1.1 & 3.3 & 6.6 \\ 1.1 & 4.4 & 5.5 \\ 1.1 & 4.4 & 6.6\\ 2.2 & 3.3 & 5.5\\ 2.2 & 3.3 & 6.6\\ 2.2 & 4.4 & 5.5\\ 2.2 & 4.4 & 6.6\end{array}% \right).$$

2) find the optimal solution $X^*_j$ of the $j$-th IPL problem from the set $$\max_{(x_1, x_2,\ldots, x_n)}\{\sum_{i=1}^n x_i\cdot c_{ji}, j \in J\},$$ and apply $f(\cdot)$ to each element of $X^*$. For instance,

$X^*=\left(% \begin{array}{ccc} -1 & 3 & 2 \\ 1 & -3 & 3 \\ 1 & -4 & 2 \\ -1 & 4 & 1\\ -2 & 3 & 2\\ -2 & 3 & 5\\ 2 & -4 & 1\\ 2 & 4 & 1\end{array}% \right),$ $f(X^*)=\left(% \begin{array}{ccc} 1.1 & 4.4 & 6.6 \\ 2.2 & 3.3 & 6.6 \\ 2.2 & 3.3 & 6.6 \\ 1.1 & 4.4 & 6.6\\ 1.1 & 4.4 & 6.6\\ 1.1 & 4.4 & 6.6\\ 2.2 & 3.3 & 5.5\\ 2.2 & 4.4 & 6.6\end{array}% \right).$

3) match the elements of $C$ and $f(X^*)$ by rows: $Res=if(C==f(X^*),1,0)$. In the example the $4$-th and $6$-th rows were matched only (denoted by 1's):

$$Res=\left(% \begin{array}{ccc} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 1 & 1\\ 0 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0\\ 1 & 1 & 1\end{array}% \right),$$

4) select the maximum from the values of objective functions for the matched rows only:

$\max_{(x_1, x_2,\ldots, x_n)}\{\sum_{i=1}^n x_i\cdot c_{ji}, j =\{4,6\} \}=\max(-1\cdot 1.1 + 4 \cdot 4.4 + 1 \cdot 6.6, 2\cdot 2.2 + 4 \cdot 4.4 + 1 \cdot 6.6 )=\max(23.1, 28.6)=28.6$. Thus, the optimal solution of the intial ILP is: $X^*=(2,4,6)$ which corresponds to the input constants $(a_1, a_2, a_3)=(2.2,4.4,6.6)$.

The weak points are:

1. How to prove that you will have at least one matched pair on the step 3?
2. How to match elements $C$ and $f(X^*)$ if $f(X^*_{ij})=0$ on the step 2?

Answer 1

Introduce integer variables $x^+_i,x^-_i,y_i$, where each $y_i$ is 0 or 1. The intended meaning of $y_i$ is that $y_i=1$ means $x_i$ is positive, $y_i=0$ means $x_i$ is zero or negative; and that $x^+_i$ captures the positive part of $x_i$ and $x^-_i$ captures the negative part. We'll enforce that intention by adding the following constraints:

$$\begin{gather*} x_i = x^+_i + x^-_i\\ 0 \le x^+_i \le U \cdot y_i\\ L \cdot (1-y_i) \le x^-_i \le 0\\ 0 \le y_i \le 1 \end{gather*}$$

This ensures that the $x_i,y_i,x^+_i,x^-_i$ are consistent. Finally, note that

$$x_i \cdot f(x_i) = a_i x^+_i + b_i x^-_i,$$

so the objective function can be expressed as

$$\sum_i a_i x^+_i + b_i x^-_i,$$

which is a linear function of the variables. Now maximize this objective function subject to the constraints above and any other constraints you might have, by feeding it to any ILP solver.

See Express boolean logic operations in zero-one integer linear programming (ILP) for other tricks of the trade.