# How to model and solve this problem?

I have a matrix $P \in M_n(\mathbb N)$, where

$$P = \begin{bmatrix} 0 & P_{12} & \ldots & P_{1n}\\ P_{21} & 0 & \ldots & P_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ P_{n1} & P_{n2} & \ldots & 0 \end{bmatrix}$$

with $P_{ii} = 0$ for all $i \in \{1,2,\dots,n\}$. I need to find matrices $A, B \in M_n(\mathbb N)$ that satisfy $A + B = P$ and that satisfy the following constraints

$$\forall i\in [\![ 1,n]\!] \sum_{k=1}^{n} A_{ik} = \sum_{k=1}^{n} A_{ki}$$

such that $\sum_{i=1}^{n} \sum_{k=1}^{n} A_{ik}$ is maximized.

I need to implement an algorithm to solve this problem. On my input data I have approximately: $n = 16$ and $\sum_{i=1}^{n}\sum_{k=1}^{n} P_{ik} = 60000$ so the brute-force approach is out of question. I don't know what could be a good approximation algorithm so my current approach is to reduce the problem to a binary integer programming problem and then apply Branch-and-Cut but I have serious doubt on it effectiveness for this specific problem.

Finding the optimal solution in polynomial time would be perfect (not sure if it's possible), but I can satisfy myself with a good approximation algorithm. Not having a strong background in CS I'm a bit confused, help would be greatly appreciated !

• How good is the LP solution? If it's fractional, you could try rounding down each entry, then for any paired row and column with different sums, randomly choosing an entry in whichever part (row or column) has the too-high sum and decrementing it. Repeat this (possibly 60000 times until you reach a zero matrix...) until no paired row and column violate the equal-sum condition. – j_random_hacker Jul 2 '18 at 15:48
• Another idea: Find the smallest uncoloured number in $P$, let's say $P_{ij}$, and set its "mate" $P_{ji}$ to the same value, then colour both squares so that you know they have been processed. Repeat until every entry has been coloured. This will certainly produce a legal solution, though it may not be very good. – j_random_hacker Jul 2 '18 at 16:00
• What happens when you try reducing it to integer linear programming and apply an off-the-shelf ILP solver? (No need to implement branch-and-cut yourself; just feed it to Gurobi or CPLEX or some other ILP solver.) – D.W. Jul 2 '18 at 16:21
• I suggest you set aside your fear and give it a try. You might be surprised at what might be feasible. Even systems 60000 variables can be solved sometimes; and many ILP solvers have an option to stop after a set timeout and output the best solution found so far. By the way, I don't understand why you think there will be 60000 variables. All you need is $n^2=256$ integer variables. That doesn't sound overwhelming. It should be easy to try. If you care about the problem enough to ask strangers to spend their time helping you with it, it seems like it should be worth your time to try ILP. – D.W. Jul 3 '18 at 6:42
• You don't really need to do anything to "reduce" your problem to LP: the constraints you have already written as equations already are an LP instance! An LP instance with 256 variables will be solved in probably a few milliseconds even with freely available solvers like SCIP or lp_solve, and the worst you could end up with is a fractional solution that gives you a high-quality upper bound! – j_random_hacker Jul 3 '18 at 9:54

Choose a modelling language, like JuMP, and solve it as a MILP.

An attempt I made with CPLEX solves a random instance ( $n=16$, $max(P)=60000$ ) to optimality almost instantly.

I've implemented the following

$$max(z)$$ $$z = \sum_{i=1}^n\sum_{k=1}^n A(i,k)$$

$$\sum_{k=1}^n A(i,k) =\sum_{k=1}^n A(k,i)\quad \forall i \in [1,n]$$ $$A(i,k) + B(i,k) = P(i,k)\quad \forall (i,k) \in [1,n] \times [1,n]$$

$$A\in[0,max(P)-1]^{n\times n}\subset\mathbb{Z}^{n\times n}$$ $$B\in[0,max(P)-1]^{n\times n}\subset\mathbb{Z}^{n\times n}$$

Barring an optimal solution, you could choose $A_{ij}= \min(P_{ij}, P_{ji})$. This is guaranteed to follow the constraints, except it will not always maximize the matrix $A$.

• Unfortunately I need better approximation than this – Youssef Azzaoui Jul 2 '18 at 16:39