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  proposed the Hungarian algorithm which can be recently computed in time, and suggested that it be used along with the simplex method.
In our Proposal 2033 in Mathematics Magazine  , 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 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 ( ) 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  is an application of the Problem to a deck of cards ( , ).
We let be a bipartite graph (which admits multiple edges) with bipartition . In this case, S includes n groups, while T comprises n different goods. We assign , , if there is a goods j in group i. We notice that G is k-regular, that is, every vertex has degree .
We use the following lemma of independent interest (see also  ), which we prove here for the sake of convenience.
Lemma 2.1 (cf.  , Corollary 2.1.3]). If G is k-regular ( ) and bipartite, then G has a perfect matching.
Proof. Summing up the number of edges,
As G is k-regular and bipartite,
We denote as the neighbors of .
Hence, as per Hall’s theorem  , 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 .
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 to 1, we can consider the resulting network . 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  ) 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 ( ) with the bipartite graph as
where for , and for .
We also define a matrix V ( ) as
where for , and for .
We define an incidence matrix W ( ) as
We let be a flow between and , and be the neighbor of i. We let
We can now formulate the problem as the following 0 - 1 integer programming problem to find its partition:
Problem I (PI)
subject to (5)
where , and .
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
subject to (6)
where 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 .
Proof. The linear programming problem (6) has a basic optimal solution from [  , Theorem 13.2]. The basic solution is expressed as interchanging columns of A if necessary, where I is an identity submatrix, which implies that . □
We consider the relationship between (PI) and its linear relaxation problem:
Problem L (PL)
subject to (7)
We now restrict the linear programming method to the simplex method, since 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 [  , Theorem 18.2]), a solution to (PL) is expressed as the intersection between solutions to
and solutions to
there may be a 0 - 1 solution from Theorem 3.1. In fact, there exists a 0 - 1 solution 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 [  , Theorem 13.4], which satisfies and because the elements in U and V consist of 1 or 0. □
Example 1. A deck of cards ( , ).
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:
(initial): 54 iterations
(K♢, 9♣, 8♢, J♠, 2♠, Q♡, 6♠, 5♡, 7♡, 3♡, 10♡, A♣, 4♢),
(delete the previous solution): 32 iterations
(J♣, 8♣, 7♢, 3♢, 6♢, 5♠, A♡, Q♣, 10♠, K♡, 2♢, 4♠, 9♠),
(delete the previous solution): 28 iterations
(7♣, Q♠, 9♢, K♠, 8♡, 5♢, 2♣, 4♡, 6♡, A♢, J♡, 3♠, 10♢),
(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 as
i.e., for the edge including the particular unit, and for .
Table 1. A deck of cards.
♠: Spades, ♡: Hearts, ♢: Diamonds, ♣: Clubs.
Consider the following problem:
Problem L1 (PL1)
subject to (8)
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 is attained. □
By setting , 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 are arbitrary and but there are no multiple edges, the number of variables becomes , 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.
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.