# A Can this optimization problem be solved?

Tags:
1. Jul 18, 2016

### smehdi

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.

2. Jul 18, 2016

### Irene Kaminkowa

If N is not too big, you can find "brute force" numerical solution.
The code is simple. No "conventional solver" is needed.

Or, you can find Cij and then feed any solver with them.

3. Jul 18, 2016

### Stephen Tashi

Are they non-negative ?

4. Jul 18, 2016

### maka89

This problem screams "simulated annealing" in my opinion. For large M's where you cant brute-force every single combination(computational time for evaluating 2^(N*N) combinations will blow up fast) ,it will give you results that are really good (close to global minimum), but may not be THE optimal solution(Unless you run it long enough to evaluate all combinations)

It is not very difficult to implement either. If you are going for this alternative, I will be happy to answer more of your questions.

Other than that, if you manage to get a linear problem, you could use the Branch-and-bound method with LP relaxations. Dunno if you could do something similar for a nonlinear problem, but in any case I think simulated annealing is the better option(and easiest) option.

Where did you come across this model?

Last edited: Jul 18, 2016
5. Jul 18, 2016

### smehdi

Thanks, $N$ is around 20.
"brute force" should work but I am looking for a more efficient way to solve the problem.
Actually I am trying to find a way to formulate it as an standard optimization problem.

Last edited: Jul 18, 2016
6. Jul 18, 2016

### smehdi

All the $a_{i,j}, i,j \in \mathcal{N}$ are non-negative.

7. Jul 18, 2016

### smehdi

Thanks. "simulated annealing" is a good candidate to use. I will work a bit more to see if I can find an easier way, preferably in an standard optimization form.

The problem comes from distributed control for resource allocation in a multiagent system. When an agent uses a resource, the efficiency of the network depends on whether the other agents use the same resource or not. For instance, when two agents can be served by one resource, the cost assigned to each agent is less than that of assigning one resource per agent, as the denominator depends on the number of agents using the resource. In this case, assigning lower cost to the agents results in saving resource for the whole system, i. e., one resource is required for the whole system instead of two. The cost function that I am using is a very specific form of the Shapley function.

What I am trying to find is the global optimum point for the system, as a centralized approach. It will be used as a benchmark for distributed algorithm to see how good the distributed approach works compared to the global optimum.

8. Jul 20, 2016

### smehdi

Well, I am going for simulated annealing but I have some questions regarding the implementation of this algorithm.
I have a couple of constraints for $M$, like $\sum_{j \in \mathcal{N}} m_{i,j}=1$ and some more.
I think I have to first find a feasible $M$ based on my constraints and then give it to SA algorithm. In this case, how $M$ is generated will also be very important. In fact, $M$ must be generated in a way to somehow, by considering the constraints, go all over the feasible region in order to make sure that we do not miss the global optimum. Moreover, $M$ must be completely random but at a same time an $M$, generated and rejected at any step by SA alg., must not be generated again. Then I think it would be a bit complicated and consumes huge memory and also the run-time would be very high. right?
Another issue is that MATLAB optimization toolbox has the SA algorithm implemented. Based on your experience, is it better to use the MATLAB optimization toolbox or I should write the code by myself?

9. Jul 21, 2016

### maka89

I wouldn't bother with making sure that an M is not generated twice.

I havent tried the MATLAB version, its probably good. It does not take many lines of code to implement the algorithm, but maybe it takes some time to understand it.

I did not know that you had constraints. It basically just means that you have to be a bit clever about how you define your states and/or the part of the algorithm that chooses a neighbour states.

If I understood your constraint right, one only has one nonzero entry in each row? With the constraint you gave, one way of choosing states and neighbours is : Let j(i) be the column index of the non-zero entry in row i. You can then choose a neighbour state by 1. Pick a random row, 2. move non-zero entry in that row to the left or the right in the matrix with even probability(unless you are looking at the first or last column, in which case it can only go one way).

Last edited: Jul 21, 2016