Linear programming based algorithms

A possibly better model [43] of the communication cost in the migration process, as opposed to (12), is the maximum cost of load migration over all processors, that is

$${\rm cost}={\rm max}_{i\in E}\ (t_0+\alpha \ \vert x_i\vert).$$

Here $t_0$ is the communication latency and $\alpha$ is the subsequent cost of communication per word. The flow calculation problem then becomes

$$\begin{eqnarray*} && {\rm Minimise\ \ }\left \{ {\rm max}_{i\in E}\ (t_0+\alpha \ \vert x_i\vert)\right \}\ ,\cr &&{\rm subject\ to\ }\quad Ax=b, \end{eqnarray*}$$

which is equivalent to

$${\rm Minimise\ \ } \quad c,\cr {\rm subject\ to\ }\quad Ax=b,\ c\ge (t_0+\alpha \ \vert x_i\vert),\ i\in E.$$ (15)

However it is not clear that an efficient parallel algorithm exists for such a linear programming problem.

Similar linear programming based flow calculation were proposed in [67], where the problem

$$\begin{eqnarray*} && {\rm Minimise\ \ } \sum_{i\leftrightarrow j} \delta_{ij} \... ...elta_{ij} \le \alpha_{ij},\quad i,j\in V;\ i\leftrightarrow j\\ \end{eqnarray*}$$

was solved. Here $\alpha_{ij}$ is the number of vertices on subdomain $i$ that may be moved to subdomain $j$, using a node selection strategy based on layering (see the next section). This linear programming problem was solved using the simplex method to give the flow. The problem has $2\vert E\vert$ variables and $\vert V\vert+\vert E\vert$ constraints. A multilevel approach was used to group subdomains into super-partitions, thereby breaking the linear programming problem into smaller ones to be solved by subsets of processors. This reduced the overall complexity of solving the linear programming problem.