Abstract

Keywords

Allocation Problems, Hall’s Theorem, Totally Unimodular Matrix, Simplex Method

Share and Cite:

1. Introduction

The type of allocation problems in which flow matrices are doubly stochastic can be solved via 0 - 1 integer programming, which, however, is generally not solvable in polynomial time. To address this issue, Kuhn [1] proposed the Hungarian algorithm which can be recently computed in $O\left(n^3\right)$ time, and suggested that it be used along with the simplex method.

In our Proposal 2033 in Mathematics Magazine [2] , instances could be formulated as allocation problems for which the Hungarian method may not be effective as the non-zero elements in the coefficient matrix are the same.

In this study, we examine the use of the simplex method for this type of problems by using the existence theorem of the solution along with partially total unimodularity and nonnegativeness of the incidence matrix. Specifically, we provide the proof that solutions to these problems can be obtained using the simplex method, which is also easy to use and usually attains a solution efficiently. We also consider a modified problem to obtain a partition including a particular unit.

The remainder of the paper is organized as follows. Section 2 describes the type of allocation problems, the object of this study. Section 3 illustrates the simplex method, while Section 4 concludes.

2. Allocation Problems

Let $G=\left(V,E\right)$ be a graph, where V is a vertex set and E is an edge set. We consider the following allocation problem:

Problem There are kn units comprising n kinds of goods, and the same k ( $1\le k<n$ ) units are available for each of them. After randomization, the kn units are divided into n groups. Is it possible to obtain k partitions, each of which consists of n different goods, by choosing one goods from each group?

Proposal 2033 [2] is an application of the Problem to a deck of cards ( $n=13$ , $k=4$ ).

We let $G=\left(S+T,E\right)$ be a bipartite graph (which admits multiple edges) with bipartition $\left\{S,T\right\}$. In this case, S includes n groups, while T comprises n different goods. We assign $e_{ij}$ , $i\in S$ , $j\in T$ if there is a goods j in group i. We notice that G is k-regular, that is, every vertex $v\in G$ has degree $d_G\left(v\right)=k$.

We use the following lemma of independent interest (see also [3] ), which we prove here for the sake of convenience.

Lemma 2.1 (cf. [3] , Corollary 2.1.3]). If G is k-regular ( $k\ge 1$ ) and bipartite, then G has a perfect matching.

Proof. Summing up the number of edges,

$\left|E\right|={\displaystyle \underset{s\in S}{\sum }{d}_G\left(s\right)}={\displaystyle \underset{t\in T}{\sum }{d}_G\left(t\right)}$.

As G is k-regular and bipartite,

$\left|E\right|=k\left|S\right|=k\left|T\right|$ ,

namely,

$\left|S\right|=\left|T\right|$.

We denote $N\left(X\right)\subset T$ as the neighbors of $X\subset S$.

Let

$N=\left\{\left|\left(x,y\right)\in E\right||x\in X,y\in N\left(X\right)\right\}$.

Then,

$N=k\left|X\right|$ for $X\subset S$

and

$N\le k\left|N\left(X\right)\right|$ for $N\left(X\right)\subset T$.

Therefore,

$\left|X\right|\le \left|N\left(X\right)\right|$.

Hence, as per Hall’s theorem [4] , G has a perfect matching. □

Thus, we give an affirmative answer to the problem.

Theorem 2.2. In the problem setting, there are k disjoint perfect matchings in $G=\left(S+T,E\right)$.

Proof. We apply Lemma 2.1, and recursively obtain and delete the resulting perfect matching k times. □

We now consider how to solve the problem in specific instances.

3. Solution Methods

By adding a source node s to the left of S, and a sink node t to the right of T, and by setting capacities of all arcs $C_{ij}$ to 1, we can consider the resulting network $N=\left(G,s,t,C\right)$. Then, given that the problem can be regarded as a maximum flow problem, we can treat it as a variety of the Ford-Fulkerson method (see [5] ) to solve specific examples. However, we will not use network algorithms because they are not easy to implement for people who have not specialized in networks. We will focus on optimization methods in this paper.

We associate a matrix U ( $n\times kn$ ) with the bipartite graph $G=\left(S+T,E\right)$ as

$U=\left(u_{ie}\right)=\left[\begin{array}{cccc}1\cdots 1& & & 0\\ & 1\cdots 1& & \\ & & \ddots & \\ 0& & & 1\cdots 1\end{array}\right]$ , (1)

where $u_{ie}=1$ for $i\in S,e\in E$ , and $u_{i{e}^{\prime }}=0$ for $i\in S,e^{\prime }\notin E$.

We also define a matrix V ( $n\times kn$ ) as

$V=\left(v_{je}\right)$ , (2)

where $v_{je}=1$ for $j\in T,e\in E$ , and $v_{j{e}^{\prime }}=0$ for $j\in T,e^{\prime }\notin E$.

We define an incidence matrix W ( $2n\times kn$ ) as

$W=\left[\begin{array}{c}U\\ V\end{array}\right]$. (3)

We let $x_{ij}$ $\left(0\le x_{ij}\le 1\right)$ be a flow between $i\in S$ and $j\in T$ $\left(\left|S\right|=\left|T\right|=n\right)$ , and $N\left(i\right)$ be the neighbor of i. We let

$x=\left(x_{11},\cdots ,x_{1k},x_{21},\cdots ,x_{2k},\cdots ,x_{n1},\cdots ,x_{nk}\right)=\left(x_1,\cdots ,x_{kn}\right)$. (4)

We can now formulate the problem as the following 0 - 1 integer programming problem to find its partition:

Problem I (PI)

minimize $-e^{\text{T}}x$

subject to $Wx=1$ (5)

$x\in {\left\{0,1\right\}}^{kn}$ ,

where $e={\left(1,\cdots ,1\right)}^{\text{T}}\in {\mathbb{Z}}_{+}^{kn}$ , and $1={\left(1,\cdots ,1\right)}^{\text{T}}\in {\mathbb{Z}}_{+}^{2n}$.

Note that there may be multiple edges. We are able to solve (PI) via 0 - 1 programming method, since Lemma 2.1 guarantees the existence of solutions. However, it may be intractable as n becomes large, since 0 - 1 integer programming problems are generally NP-hard.

We show the following result.

Theorem 3.1. Consider the linear programming problem

minimize $-e^{\text{T}}x$

subject to $Ax=1$ (6)

$x\ge 0$ ,

where $A:n\times m\left(n\le m\right)$ is a nonnegative totally unimodular matrix of which columns with exactly one 1 include a permutation matrix. Then, (6) has an optimal 0 - 1 solution $x^{*}\in {\left\{0,1\right\}}^m$.

Proof. The linear programming problem (6) has a basic optimal solution from [ [6] , Theorem 13.2]. The basic solution $x^{*}$ is expressed as $\left(I^{-1}1,0\right)=\left(1,0\right)$ interchanging columns of A if necessary, where I is an $n\times n$ identity submatrix, which implies that $x^{*}\in {\left\{0,1\right\}}^m$. □

We consider the relationship between (PI) and its linear relaxation problem:

Problem L (PL)

minimize $-e^{\text{T}}x$

subject to $Wx=1$ (7)

$x\ge 0$.

We now restrict the linear programming method to the simplex method, since $x_i=\frac{1}{k},i=1,\cdots ,kn$ is a trivial solution to (PL).

We can now establish the following result.

Theorem 3.2. The simplex method applied to (PL) solves (PI).

Proof. Noting that U, V are nonnegative totally unimodular matrices of which columns include a permutation matrices (N.B., even W is totally unimodular from [ [7] , Theorem 18.2]), a solution $\tilde{x}$ to (PL) is expressed as the intersection between solutions to

minimize $-e^{\text{T}}x$

subject to $Ux=1$

$x\ge 0$ ,

and solutions to

minimize $-e^{\text{T}}x$

subject to $Vx=1$

$x\ge 0$ ,

there may be a 0 - 1 solution $\tilde{x}\in {\left\{0,1\right\}}^{kn}$ from Theorem 3.1. In fact, there exists a 0 - 1 solution $\tilde{x}\in {\left\{0,1\right\}}^{kn}$ to (PL) in light of Lemma 2.1.

Hence, the simplex method applied to (PL) solves (PI), since it terminates at a basic optimal point [ [6] , Theorem 13.4], which satisfies $x^{*}\in {\left\{0,1\right\}}^{kn}$ and $-e^{\text{T}}{x}^{*}=-n$ because the elements in U and V consist of 1 or 0. □

Example 1. A deck of cards ( $n=13$ , $k=4$ ).

See Table 1.

The experiments are implemented on a laptop, using FORTRAN to code the simplex method. At first, there are 52 variables and 26 constraints. The solutions are as follows:

$k=4$ (initial): 54 iterations

(K♢, 9♣, 8♢, J♠, 2♠, Q♡, 6♠, 5♡, 7♡, 3♡, 10♡, A♣, 4♢),

$k=3$ (delete the previous solution): 32 iterations

(J♣, 8♣, 7♢, 3♢, 6♢, 5♠, A♡, Q♣, 10♠, K♡, 2♢, 4♠, 9♠),

$k=2$ (delete the previous solution): 28 iterations

(7♣, Q♠, 9♢, K♠, 8♡, 5♢, 2♣, 4♡, 6♡, A♢, J♡, 3♠, 10♢),

$k=1$ (the remainder)

(Q♢, 6♣, 5♣, 9♡, A♠, 3♣, 7♠, K♣, 4♣, 2♡, 8♠, 10♣, J♢).

We should note that the objective function value of (7) is -n from the proof of Theorem 3.2. Therefore, the simplex method terminates in Phase I, in which case, we may generally expect high efficiency.

It is also worth noting that we can select a particular unit (e.g., A♠) in a partition, since the existence of such a partition is guaranteed by Theorem 2.2. For this purpose, we set the coefficient $e^{\prime }$ as

$e^{\prime }=\left(1,\cdots ,1,1+s,1,\cdots ,1\right)\in {\mathbb{Z}}_{+}^{kn}$

i.e., ${e^{\prime }}_{j_0}=1+s\left(s>0,s\in {\mathbb{Z}}_{+}\right)$ for the edge including the particular unit, and ${e^{\prime }}_i=1$ for $i\ne j_0$.

♠: Spades, ♡: Hearts, ♢: Diamonds, ♣: Clubs.

Consider the following problem:

Problem L1 (PL1)

minimize $-{e^{\prime }}^{\text{T}}x$

subject to $Wx=1$ (8)

$x\ge 0$.

Then, the solution of (8) becomes the desired partition, as formalized in the following theorem.

Theorem 3.3. The simplex method applied to (PL1) determines a partition that includes the particular unit.

Proof. The simplex method is valid since, as per Theorem 2.2, there are feasible points in both (PI) and (PL1). In this case, the simplex method terminates in either Phase I or Phase II, when the objective function value $-n-s$ is attained. □

By setting ${e^{\prime }}_{17}=2$ , ${e^{\prime }}_i=1,i=1,\cdots ,16,18,\cdots ,52$ in order to select A♠ in Example 1, we obtained the solution

(K♢, 9♣, 8♢, J♠, A♠, Q♡, 6♠, 5♡, 7♡, 2♡, 10♡, 3♠, 4♢).

after 60 iterations (Phase I: 54 iterations, Phase II: 6 iterations) in total.

In general transportation problems, i.e., when $e\ge 0$ are arbitrary and $\left|S\right|=\left|T\right|=n$ but there are no multiple edges, the number of variables becomes $n^2$ , which tends to be much larger than kn. This may cause difficulties in using the simplex method. Note that, for the considered problem (kn variables), the simplex method is efficient, and we can select an arbitrary unit in the solution.

4. Conclusion

In this study, we derived the result for allocation problems which can be modeled using bipartite graphs, which might lead to unexpected results. Specifically, we provided the proof that the simplex method solves these problems by using the existence theorem of the solution along with partially total unimodularity and nonnegativeness of the incidence matrix. The elementary numerical result we presented shows the validity and efficiency of the method. Moreover, we considered the application of the simplex method to a modified problem to obtain a partition that includes a particular unit.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References