- #1
smehdi
- 16
- 0
Hello, I am working on an optimization problem but I am not sure if the problem can be formulated and solved with conventional solvers.
Assume the minimization problem for a set of elements ##\mathcal{N} =\{ 1,\dots, h, \dots, i,\dots, N \}##
$$
\mathrm{minimize}\quad C = \sum_{i=1}^{N} \sum_{j=1}^{N} m_{ij}.c_{ij}
$$ in which ##m_{ij} \in \mathbf{M}##.
##\mathbf{M}## is a binary ##N\times N ## matrix such that ##m_{ij}=1## says the element ##i## is connected to element ##j## and its cost ##c_{ij}## is defined as $$ c_{ij} = \frac{a_{ij}}{1+\sum_{n=1}^{\color{red}{i}} m_{nj}} - \sum_{h=1}^{i} \frac{ m_{hj}. a_{hj}}{(1+\sum_{n=1}^{h} m_{nj}) (2+\sum_{n=1}^{h} m_{nj}) }$$ in which ##a_{ij}## and ##a_{hj}## are given.
In a simpler case, we can consider
$$ c_{ij} = \frac{a_{ij}}{1+\sum_{n=1}^{\color{red}{i}} m_{nj}} - \frac{ m_{hj}. a_{hj}}{(1+\sum_{n=1}^{h} m_{nj}) (2+\sum_{n=1}^{h} m_{nj}) }$$ for a given ##h##.
In other words, the cost of connecting to element ##j## for element ##i## depends on how many elements are connected to ##j## and if a particular element ##h## is connected to ##j##.
Every element must be connected to at least one other element and ##m_{i,i} = 0, \forall i \in \mathcal{N}##.
In fact, such a matrix has to be found $$
\mathbf{M} =
\begin{bmatrix}
m_{11} & \dots & m_{1j}& \dots& m_{1N} \\
\vdots & \dots & \vdots & \dots & \vdots \\
m_{i1} & \dots & m_{ij} & \dots& m_{iN} \\
\vdots & \dots & \vdots & \dots & \vdots \\
m_{N1}& \dots & m_{Nj}& \dots& m_{NN} \\
\end{bmatrix}.$$ I am looking for the optimum result and the solver is not very much important.
Actually the main problem is that the denominator of the second part of ##c_{i,j}## is non-linear and I am wondering if it can be converted to a linear form or it can be solved by a solver as it is.
Thanks.
Assume the minimization problem for a set of elements ##\mathcal{N} =\{ 1,\dots, h, \dots, i,\dots, N \}##
$$
\mathrm{minimize}\quad C = \sum_{i=1}^{N} \sum_{j=1}^{N} m_{ij}.c_{ij}
$$ in which ##m_{ij} \in \mathbf{M}##.
##\mathbf{M}## is a binary ##N\times N ## matrix such that ##m_{ij}=1## says the element ##i## is connected to element ##j## and its cost ##c_{ij}## is defined as $$ c_{ij} = \frac{a_{ij}}{1+\sum_{n=1}^{\color{red}{i}} m_{nj}} - \sum_{h=1}^{i} \frac{ m_{hj}. a_{hj}}{(1+\sum_{n=1}^{h} m_{nj}) (2+\sum_{n=1}^{h} m_{nj}) }$$ in which ##a_{ij}## and ##a_{hj}## are given.
In a simpler case, we can consider
$$ c_{ij} = \frac{a_{ij}}{1+\sum_{n=1}^{\color{red}{i}} m_{nj}} - \frac{ m_{hj}. a_{hj}}{(1+\sum_{n=1}^{h} m_{nj}) (2+\sum_{n=1}^{h} m_{nj}) }$$ for a given ##h##.
In other words, the cost of connecting to element ##j## for element ##i## depends on how many elements are connected to ##j## and if a particular element ##h## is connected to ##j##.
Every element must be connected to at least one other element and ##m_{i,i} = 0, \forall i \in \mathcal{N}##.
In fact, such a matrix has to be found $$
\mathbf{M} =
\begin{bmatrix}
m_{11} & \dots & m_{1j}& \dots& m_{1N} \\
\vdots & \dots & \vdots & \dots & \vdots \\
m_{i1} & \dots & m_{ij} & \dots& m_{iN} \\
\vdots & \dots & \vdots & \dots & \vdots \\
m_{N1}& \dots & m_{Nj}& \dots& m_{NN} \\
\end{bmatrix}.$$ I am looking for the optimum result and the solver is not very much important.
Actually the main problem is that the denominator of the second part of ##c_{i,j}## is non-linear and I am wondering if it can be converted to a linear form or it can be solved by a solver as it is.
Thanks.