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:
- How to prove that you will have at least one matched pair on the step 3?
- How to match elements $C$ and $f(X^*)$ if $f(X^*_{ij})=0$ on the step 2?