Search

The generalized assignment problem (GAP) is an open problem in which an integer k is given and one wants to assign k ′ agents to k k ′ ≤ k jobs such that the sum of the corresponding cost is minimal. Unlike the traditional K -cardinality assignment problem, a job can be assigned to many, but different, agents and an agent may undertake several, but different, jobs in our problem. A network model with a special structure of GAP is given and an algorithm for GAP is proposed. Meanwhile, some important properties of the GAP are given. Numerical experiments are implemented, and the results indicate that the proposed algorithm can globally and efficiently optimize the GAP with a large range cost. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for solving a minimum cost flow (MCF) problem with a dual approach. The algorithm holds the complementary slackness at each iteration and finds an augmenting path by updating node potential iteratively. Then, flow can be augmented at the original network. In contrast to other popular algorithms, the presented algorithm does not find a residual network, nor find a shortest path. Furthermore, our algorithm holds information of node potential at each iteration, and we update node potential within finite iterations for expanding the admissible network. The validity of our algorithm is given. Numerical experiments show that our algorithm is an efficient algorithm for the MCF problem, especially for the network with a small interval of cost of per unit flow. [ABSTRACT FROM AUTHOR]