An efficient cost scaling algorithm for the assignment problem

The cost scaling push-relabel method has been shown to be efficient for solving minimum-cost flow problems. In this paper we apply the method to the assignment problem and investigate implementations of the method that take advantage of assignment's special structure. The results show that the method is very promising for practical use.This author's research was supported in part by ONR Young Investigator Award N00014-91-J-1855, NSF Presidential Young Investigator Grant CCR-8858097 with matching funds from AT&T, DEC and 3M, and a grant from the Powell Foundation.This author's research was supported by the above-mentioned ONR and NSF grants.     

Pinpointing the complexity of the interval min–max regret knapsack problem

We show that a natural robust optimization variant of the knapsack problem is complete for the second level of the polynomial hierarchy.     

How ∗ not ∗ to solve a Sudoku

We prove the NP-hardness of a consistency checking problem that arises in certain elimination strategies for solving Sudoku-type problems.     

The equilibrium generalized assignment problem and genetic algorithm

The well-known generalized assignment problem (GAP) is to minimize the costs of assigning n jobs to m capacity constrained agents (or machines) such that each job is assigned to exactly one agent. This problem is known to be NP-hard and it is hard from a computational point of view as well. In this paper, follows from practical point of view in real systems, the GAP is extended to the equilibrium generalized assignment problem (EGAP) and the equilibrium constrained generalized assignment problem (ECGAP). A heuristic equilibrium strategy based genetic algorithm (GA) is designed for solving the proposed EGAP. Finally, to verify the computational efficiency of the designed GA, some numerical experiments are performed on some known benchmarks. The test results show that the designed GA is very valid for solving EGAP.     

Using the WOWA operator in robust discrete optimization problems

In this paper a class of discrete optimization problems with uncertain costs is discussed. The uncertainty is modeled by introducing a scenario set containing a finite number of cost scenarios. A probability distribution over the set of scenarios is available. In order to choose a solution the weighted OWA criterion (WOWA) is applied. This criterion allows decision makers to take into account both probabilities for scenarios and the degree of pessimism/optimism. In this paper the complexity of the considered class of discrete optimization problems is described and some exact and approximation algorithms for solving it are proposed. Applications to the selection and the assignment problems, together with results of computational tests are shown.     

A robust approach to the chance-constrained knapsack problem

In this paper, the chance-constrained knapsack problem (CKP) is addressed. Relying on robust optimization, a tractable combinatorial algorithm is proposed to solve approximately CKP. For two specific classes of uncertain knapsack problems, it is proved to solve CKP at optimality.     

An inverse model for the most uniform problem

In this paper, we consider a kind of inverse model for the most uniform problem. This model has some practical background. It is shown that the model can be solved in polynomial time whenever an associated min-sum problem can be solved in polynomial time.     

Upper and lower bounding procedures for the multiple knapsack assignment problem

We formulate the multiple knapsack assignment problem (MKAP) as an extension of the multiple knapsack problem (MKP), as well as of the assignment problem. Except for small instances, MKAP is hard to solve to optimality. We present a heuristic algorithm to solve this problem approximately but very quickly. We first discuss three approaches to evaluate its upper bound, and prove that these methods compute an identical upper bound. In this process, reference capacities are derived, which enables us to decompose the problem into mutually independent MKPs. These MKPs are solved euristically, and in total give an approximate solution to MKAP. Through numerical experiments, we evaluate the performance of our algorithm. Although the algorithm is weak for small instances, we find it prospective for large instances. Indeed, for instances with more than a few thousand items we usually obtain solutions with relative errors less than 0.1% within one CPU second.     

A new algorithm for the assignment problem

We propose a new algorithm for the classical assignment problem. The algorithm resembles in some ways the Hungarian method but differs substantially in other respects. The average computational complexity of an efficient implementation of the algorithm seems to be considerably better than the one of the Hungarian method. In a large number of randomly generated problems the algorithm has consistently outperformed an efficiently coded version of the Hungarian method by a broad margin. The factor of improvement increases with the problem dimensionN and reaches an order of magnitude forN equal to several hundreds.Work supported by Grant NSF ENG-7906332.     

ON THE COMPUTATIONAL COMPLEXITY OF THE MAXIMUM TRADE PROBLEM

ＯＮＴＨＥＣＯＭＰＵＴＡＴＩＯＮＡＬＣＯＭＰＬＥＸＩＴＹＯＦＴＨＥＭＡＸＩＭＵＭＴＲＡＤＥＰＲＯＢＬＥＭＺ．－Ｑ．Ｌｕｏ；Ｄ．Ｌ．ＰＡＲＮＡＳ（ＣｏｍｍｕｎｉｃａｔｉｏｎｓＲｅｓｅａｒｃｈＬａｂｏｒａｔｏｃｙＤｅｐａｒｔｍｅｎｔｏｆＥｌｅｃｔｒｉｃａ...     

Fuzzy weighted equilibrium multi-job assignment problem and genetic algorithm

In this paper, the equilibrium optimization problem is proposed and the assignment problem is extended to the equilibrium multi-job assignment problem, equilibrium multi-job quadratic assignment problem and the minimum cost and equilibrium multi-job assignment problem. Furthermore, the mathematical models of the equilibrium multi-job assignment problem and the equilibrium multi-job quadratic assignment problem with fuzzy parameters are formulated. Finally, a genetic algorithm is designed for solving the proposed programming models and some numerical examples are given to verify the efficiency of the designed algorithm.     

The Wiener maximum quadratic assignment problem

We investigate a special case of the maximum quadratic assignment problem where one matrix is a product matrix and the other matrix is the distance matrix of a one-dimensional point set. We show that this special case, which we call the Wiener maximum quadratic assignment problem, is NP-hard in the ordinary sense and solvable in pseudo-polynomial time.Our approach also yields a polynomial time solution for the following problem from chemical graph theory: find a tree that maximizes the Wiener index among all trees with a prescribed degree sequence. This settles an open problem from the literature.     

A cardinality-constrained robust model for the assignment problem in Home Care services

Home Care includes medical, paramedical and social services which are delivered to patients at their domicile rather than in hospital. Managing human and material resources in Home Care services is a difficult task, as the provider has to deal with peculiar constraints (e.g., the continuity of care, which imposes that a patient is always cared for by the same nurse) and to manage the high variability of patients’ demands. One of the main issues encountered in planning Home Care services under continuity of care requirement is the nurse-to-patient assignment. Despite the importance of this topic, the problem is only marginally addressed in the literature, where continuity of care is usually treated as a soft-constraint rather than as a hard one. Uncertainty is another relevant feature of nurse-to-patient assignment problem, and it is usually managed adopting stochastic programming or analytical policies. However, both these approaches proved to be limited, even if they improve the quality of the assignments upon those actually provided in practice. In this paper, we develop a cardinality-constrained robust assignment model, which allows exploiting the potentialities of a mathematical programming model without the necessity of generating scenarios. The developed model is tested on real-life instances related to a relevant Home Care provider operating in Italy, in order to evaluate its capability of reducing the costs related to nurses’ overtimes.     

On the complexity of the robust spanning tree problem with interval data

This paper studies the complexity of the robust spanning tree problem with interval data (RSTID). It shows that the problem is NP-complete, settling the conjecture of Kouvelis and Yu, and that it remains so for complete graphs or when the intervals are all [0,1]. These results indicate that the difficulty of RSTID stems from both the graph topology and the structure of the cost intervals, suggesting new directions for search algorithms.     

Proportion-based robust optimization and team orienteering problem with interval data

In this paper, a proportion-based robust optimization approach is developed to deal with uncertain combinatorial optimization problems. This approach assumes that a certain proportion of uncertain coefficients in each solution are allowed to change and optimizes a deterministic model so as to achieve a trade-off between optimality and feasibility when the coefficients change. We apply this approach on team orienteering problem with interval data (TOPID), a variant of vehicle routing problem, which has not yet been studied before. A branch and price algorithm is proposed to solve the robust counterpart by using two novel dominance relations. Finally, numerical study is performed. The results show the usefulness of the proposed robust optimization approach and the effectiveness of our algorithm.     

Complexity analysis of an assignment problem with controllable assignment costs and its applications in scheduling

We extend the classical linear assignment problem to the case where the cost of assigning agent j to task i is a multiplication of task i’s cost parameter by a cost function of agent j. The cost function of agent j is a linear function of the amount of resource allocated to the agent. A solution for our assignment problem is defined by the assignment of agents to tasks and by a resource allocation to each agent. The quality of a solution is measured by two criteria. The first criterion is the total assignment cost and the second is the total weighted resource consumption. We address these criteria via four different problem variations. We prove that our assignment problem is NP-hard for three of the four variations, even if all the resource consumption weights are equal. However, and somewhat surprisingly, we find that the fourth variation is solvable in polynomial time. In addition, we find that our assignment problem is equivalent to a large set of important scheduling problems whose complexity has been an open question until now, for three of the four variations.     

On dual solutions of the linear assignment problem

For the linear assignment problem we describe how to obtain different dual solutions. It turns out that a shortest path algorithm can be used to compute such solutions with several interesting properties that enable to do better post-optimality analysis.Two examples illustrate how different dual solutions can be used in the context of the traveling salesman problem.     

A robust optimization model for a cross-border logistics problem with fleet composition in an uncertain environment

Since the implementation of the open-door policy in China, many Hong Kong-based manufacturers' production lines have moved to China to take advantage of the lower production cost, lower wages, and lower rental costs, and thus, the finished products must be transported from China to Hong Kong. It has been discovered that logistics management often encounters uncertainty and noisy data. In this paper, a robust optimization model is proposed to solve a cross-border logistics problem in an environment of uncertainty. By adjusting penalty parameters, decision-makers can determine an optimal long-term transportation strategy, including the optimal delivery routes and the optimal vehicle fleet composition to minimize total expenditure under different economic growth scenarios. We demonstrate the robustness and effectiveness of our model using the example of a Hong Kong-based manufacturing company. The analysis of the trade-off between model robustness and solution robustness is also presented.     

A labeling algorithm for the sensitivity ranges of the assignment problem

In view of the simplex-type algorithm, the assignment problem is inherently highly degenerate. It may be the optimal basis has changed, but the optimal assignment is unchanged when parameter variation occurs. Degeneracy then makes sensitivity analysis difficult, as well as makes the classical Type I range, which identifies the range the optimal basis unchanged, impractical. In this paper, a labeling algorithm is proposed to identify two other sensitivity ranges – Type II range and Type III range. The algorithm uses the reduced cost matrix, provided in the final results of most solution algorithms for AP, to determine the Type II range which reflects the stability of the current optimal assignment. Thus, the algorithm generates a streamlined situation from searching the optimal solution until performing the sensitivity analysis of the assignment problem. The Type III range, reflecting the flexibility of optimal decision making, can be obtained immediately after the Type II range is determined. Numerical examples are presented to demonstrate the algorithm.