1

Let's say I have a set of $N$ members (not ordered) $x_i$, and suppose $N$ is even. To each point are associated $k$ characteristics $x_{ij}$, $j=1,...,k$. There is another additional characteristic $x_{i0}$ which is boolean, and there are $N/2$ members that are $0$ and $N/2$ that are $1$. I want to maximize a certain functional, that is

$$H[f(x)]=\sum_{i=1}^{N/2} g[x_i,f(x_i)] + \sum_{i=\frac{N}{2}+1}^{N}h[x_i,f(x_i)]$$

For certain functions $g$ and $h$.We can assume that $g$ and $h$ aren't arbitrary functions of the specific member but just of its characteristics, that is

$$g(x_i,f(x_i)=y_i)=g(x_{i1},...,x_{ik},y_{i1},...,y_{ik})$$

Further, $f(x_i)=y_i$ has to be of the opposite class (if $x_{i0}=0$ then $y_{i0}=1$) and has to be one to one between the two classes. I don't know much about $g$ and $h$, but I do know that for certain characteristics ($x_{i1}$ say) both $g$ and $h$ are strictly monotone increasing when all other variables are held constant.

What can I say in general about this problem? How do I impose the constraints? Theoretical observations, references and numerical schemes are all very helpful.

Gennaro Marco Devincenzis
  • 2,361
  • You can approach it by defining the functional and mapping function explicitly, introducing constraints to enforce the one-to-one mapping, and then applying suitable optimization techniques based on the characteristics of the optimization problem – rumathe Mar 19 '23 at 11:55
  • Let's say I do have $g$ and $h$. How would you impose the constraint? – Gennaro Marco Devincenzis Mar 19 '23 at 12:30
  • 1
    Now it's a binary integer programming problem. You can solve it using integer programming techniques or relax the binary constraints to continuous variables between $0$ and $1$ and use linear programming techniques with appropriate rounding of the solution. – rumathe Mar 19 '23 at 12:35
  • I see! thanks a lot. If you write an answer I'll accept it. – Gennaro Marco Devincenzis Mar 19 '23 at 12:59

1 Answers1

1

Introduce binary variables $a_{ij}$ for $i=1,...,N/2$ and $j=N/2+1,...,N$. The variable $a_{ij}$ will be equal to $1$ if the mapping $f(x_i) = x_j$ and $0$ otherwise. Add constraints to enforce one-to-one mapping:
a) For each $i$ ($1$ to $N/2$), ensure that exactly one $a_{ij} = 1$:
$$\sum_{j=\frac{N}{2}+1}^{N} a_{ij} = 1, \quad \forall i = 1, \dots, \frac{N}{2}$$ b) For each $j$ ($N/2+1$ to $N$), ensure that exactly one $a_{ij} = 1$:
$$\sum_{i=1}^{\frac{N}{2}} a_{ij} = 1, \quad \forall j = \frac{N}{2}+1, \dots, N$$ Modify the functional $H$ to incorporate the binary variables: $$H[f(x)] = \sum_{i=1}^{\frac{N}{2}}\sum_{j=\frac{N}{2}+1}^{N} a_{ij} \cdot g(x_i, x_j) + \sum_{i=1}^{\frac{N}{2}}\sum_{j=\frac{N}{2}+1}^{N} a_{ij} \cdot h(x_j, x_i)$$ $$\max_{a_{ij}} H[f(x)]$$ subject to $$\sum_{j=\frac{N}{2}+1}^{N} a_{ij} = 1, \quad \forall i = 1, \dots, \frac{N}{2} \sum_{i=1}^{\frac{N}{2}} a_{ij} = 1, \quad \forall j = \frac{N}{2}+1, \dots, N a_{ij} \in {0, 1}, \quad \forall i = 1, \dots, \frac{N}{2}, \forall j = \frac{N}{2}+1, \dots, N$$ Now it's a binary integer programming problem. You can solve it using integer programming techniques or relax the binary constraints to continuous variables between 0 and 1 and use linear programming techniques with appropriate rounding of the solution.

rumathe
  • 438