A column generation heuristic for a dynamic generalized assignment problem

This paper studies the dynamic generalized assignment problem (DGAP) which extends the well-known generalized assignment problem by considering a discretized time horizon and by associating a starting time and a finishing time with each task. Additional constraints related to warehouse and yard management applications are also considered. Three linear integer programming formulations of the problem are introduced. The strongest one models the problem as an origin–destination integer multi-commodity flow problem with side constraints. This model can be solved quickly for instances of small to moderate size. However, because of its computer memory requirements, it becomes impractical for larger instances. Hence, a column generation algorithm is used to compute lower bounds by solving the linear program (LP) relaxation of the problem. This column generation algorithm is also embedded in a heuristic aimed at finding feasible integer solutions. Computational experiments on large-scale instances show the effectiveness of the proposed approach.     

On the variable-depth-search heuristic for the linear-cost generalized assignment problem

The classical assignment problem seeks to determine a mapping between a set of assignees and a set of assignments. The linear cost assignment problem (LCGAP), as a generalized model, incorporates the relative workloads between assignees and assignments. Although LCGAP is computationally intractable, it has been extensively studied because of its practical implications in many real world situations. Variable-depth-search heuristic (VDSH) method is one of the solution methods that have been developed to produce quality near-optimal solutions to LCGAP. The main structure of VDSH consists of two basic operations: reassign and swap. In this paper, we make further observations on this effective heuristic method through a series of computational experiments. The numerical results statistically evince that different combina-tions of these two operations will result in solutions of different quality levels. These findings are expected to have similar implications to search heuristics for other optimization problems.     

Algorithms for the generalized weighted frequency assignment problem

We report the performance of 15 construction heuristics to find initial solutions, and 4 search algorithms to solve a frequency assignment problem where the value of an assigned frequency is determined by the site where it is assigned. The algorithms were tested on 3 sets of problems, the first one corresponds to the well-known Philadelphia problems, and the last two correspond to situations frequently encountered when FM frequencies are assigned in Mexico. Our experimental results show that the construction heuristics that consider the weights of the sites perform well. Among the 4 search algorithms tested, the one based on cross entropy performed better than the others in small problems, whereas in large problems the algorithm based on simulated annealing performed the best.     

An ANTS heuristic for the frequency assignment problem

The problem considered in this paper consists in assigning frequencies to radio links between base stations and mobile transmitters in order to minimize the global interference over a given region. This problem is NP-hard and few results have been reported on techniques for solving it to optimality. We have applied to this problem an ANTS metaheuristic, that is, an approach following the ant colony optimization paradigm. Computational results, obtained on a number of standard problem instances, testify the effectiveness of the proposed approach.     

A heuristic procedure for the integrated facility layout design and flow assignment problem

We present an efficient iterative heuristic procedure for solving the integrated layout design and product flow assignment problem. The layout design decisions involve planar location of unequal-area machines with duplicates. The product flows are assigned to machines according to the product processing routes. The integrated decision problem is a nonlinear mixed integer model which cannot be efficiently solved using classical methods for large problems. We propose a novel integrated heuristic procedure based on the alternating heuristic, a perturbation algorithm and sequential location heuristic. Since the alternating heuristic between facility layout design and product-machine assignment sub-problems terminates with local optima, we developed a perturbation algorithm based on assignment decisions. The results of an experimental study show that proposed procedure is both efficient and effective in identifying quality solutions for small to very large-sized problems.     

An efficient algorithm for saving ordered sets in a compacted form

Although developed for saving the large number of lines that occur in the construction of biplanes, the algorithm described in this article has a general significance. The algorithm takes any set of ordered elements and converts it into an array of symbols based on a number system with a factorial base. This array is then partitioned and saved as one or more numbers. In this way a saving of more than 50% can be achieved.     

Finite dominating sets for the multi-facility ordered median problem in networks and algorithmic applications

We identify a finite dominating set (FDS) for a special case of the multi-facility ordered median problem in networks, in which the λ-weights can take at least two different values. This FDS result not only includes the FDS research for the p-center problem, but also extends the case of a<b in the λ-weights provided by Kalcsics et al. (Kalcsics, J., Nickel, S., Puerto, J. (2003). Multi-facility ordered median problems: A further analysis. Networks, 41(1), 1–12). Furthermore, based on the FDS result, we devise an exact algorithm for the problem. In addition, we present a polynomial time algorithm for the problem with at most three different values in the λ-weights in tree networks. Finally, we pose an open problem on identifying the existence of a polynomial size FDS for the multi-facility convex ordered median problem in networks.     

Improved LP-based algorithms for the closest string problem

In a recent paper by Liu et al. [Exact algorithm and heuristic for the closest string problem, Computers & Operations Research 2011;38:1513-20], a polynomial time heuristic procedure is proposed for the closest string problem (CSP). Such heuristic called LDDA_LSS is a combination of a previously published approximation algorithm and local search strategies. This paper points out that an instant algorithm deriving a feasible solution directly from the continuous relaxation solution of a standard ILP formulation of CSP already strongly outperforms LDDA_LSS both in terms of solution quality and computing time. Two core based procedures are then proposed that further improve the results of the instant algorithm. Based on these results, we conclude that such LP-based approaches for their efficiency and simplicity should be used as a benchmark for future heuristics on CSP.     

An LP-based heuristic algorithm for the node capacitated in-tree packing problem

In this paper, we deal with the node capacitated in-tree packing problem. The input consists of a directed graph, a root node, a node capacity function and edge consumption functions for heads and tails. The problem is to find a subset of rooted spanning in-trees and their packing numbers, where the packing number of an in-tree is the number of times it is packed, so as to maximize the sum of packing numbers under the constraint that the total consumption of the packed in-trees at each node does not exceed the capacity of the node. This problem is known to be NP-hard.We propose a two-phase heuristic algorithm for this problem. In the first phase, it generates candidate spanning in-trees to be packed. The node capacitated in-tree packing problem can be formulated as an IP (integer programming) problem, and the proposed algorithm employs the column generation method for the LP (linear programming) relaxation problem of the IP to generate promising candidate in-trees. In the second phase, the algorithm computes the packing number of each in-tree. Our algorithm solves this second-phase problem by first modifying feasible solutions of the LP relaxation problem and then improving them with a greedy algorithm. We analyze upper and lower bounds on the solution quality of such LP-based algorithms for this problem.We conducted computational experiments on graphs used in related papers and on randomly generated graphs. The results indicate that our algorithm has a better performance than other existing methods.     

On the structure of generalized rough sets

In this paper we consider some fundamental properties of generalized rough sets induced by binary relations on algebras and show that

1.

Any reflexive binary relation determines a topology.

2.

If θ is a reflexive and symmetric relation on a set X, then O={A⊆X|θ_-(A)=A} is a topology such that A is open if and only if it is closed.

3.

Conversely, for every topological space (X,O) satisfying the condition that A is open if and only if it is closed, there exists a reflexive and symmetric relation R such that O={A⊆X|R_-(A)=A}.

4.

Let θ be an equivalence relation on X. For any pseudo ω-closed subset A of X, θ₋(A) is an ω-closed set if and only if ω(x, x, … , x) ∈ θ₋(A) for any x ∈ X.

Moreover we consider properties of generalized rough sets.     

Exact and heuristic algorithms for the interval data robust assignment problem

We consider the Assignment Problem with interval data, where it is assumed that only upper and lower bounds are known for each cost coefficient. It is required to find a minmax regret assignment. The problem is known to be strongly NP-hard. We present and compare computationally several exact and heuristic methods, including Benders decomposition, using CPLEX, a variable depth neighborhood local search, and two hybrid population-based heuristics. We report results of extensive computational experiments.     

An improved heuristic for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is an important and practical problem in the OR literature. In short, the problem is to identify routes to service (e.g., pickup or deliver) demand located along the edges of a network such that the total cost of the routes is minimized. In general, a single route cannot satisfy the entire demand due to capacity constraints on the vehicles. CARP belongs to the set of NP-hard problems; consequently numerous heuristic and metaheuristic solution approaches have been developed to solve it. In this paper an “ellipse rule” based heuristic is proposed for the CARP. This approach is based on the path-scanning heuristic, one of the mostly used greedy-add heuristics for this problem. The innovation consists basically of selecting edges only inside ellipses when the vehicle is near the end of each route. This new approach was implemented and tested on three standard datasets and the solutions are compared against: (i) the original path-scanning heuristic; (ii) two other path-scanning heuristics and (iii) the three best known metaheuristics. The results indicate that the “ellipse rule” approach lead to improvements over the three path-scanning heuristics, reducing the average distance to the lower bound in the test problems by about 44%.     

An orthogonal systolic design for the assignment problem

A systolic array for the solution of the assignment problem is presented. The algorithm requires O(n²) time on an orthogonally connected array of (n + 2) * (n + 2) cells consisting of simple adders and control logic. The design is area efficient and incorporates the new concept of a Systolic Control Ring (SCR) to generate the necessary systolic wavefronts in any orientation within the design, while special cells are positioned only on the periphery of the design. The design was simulated and tested by an OCCAM program.     

On the complexity of short-term production planning and the near-optimality of a sequential assignment problem heuristic approach

In semiconductor manufacturing, the process of short-term production planning requires setting clear and yet challenging and doable goals to each operation and toolset in the process flow per each product type. We demonstrate the complexity of this problem using an experimental study performed with proficient workforce, and then show how the problem can be decomposed, aggregated, and solved using sequential recurrent linear programming assignment problems. We also refer to the improvements that the proposed algorithm has achieved in practice when applied to multiple semiconductor production facilities, and discuss its efficiency and uniqueness as a fast heuristic relative to other proposed methods.     

火力优化分配问题的小生境遗传蚂蚁算法

火力分配问题是NP难题,经典的求解算法存在指数级的时间复杂度。文中提出一种小生境遗传算法与蚁群优化算法相结合的小生境遗传蚂蚁算法,并针对具体问题提出蚂蚁搜索的禁忌规则。对该算法进行了实验,并将实验结果与其他算法进行比较分析,分析结果表明：新算法无论是在优化性能还是在时间性能都取得了非常好的效果。文中算法对其他的NP问题同样适用。     

An effective subgradient algorithm for the generalized assignment problem

A modified subgradient algorithm is presented for the generalized assignment problem, which, like the classical assignment problem, is concerned with the minimum cost assignment of agents to jobs. The generalized assignment problem, however, permits differences in job performance efficiencies among agents and thereby allows the possibility that each agent may be assigned more than a single job, as long as each job is ultimately assigned and the total resources available to every agent are not exceeded. A two stage heuristic algorithm using a modified subgradient approach and branch and bound is developed for solving the problem. By computing step sizes precisely and using the dual as a bound, the algorithm is shown to be particularly effective and easy to program and implement. A numerical example is presented to illustrate the model and method, and computational experience is cited for problems containing up to 12,000 0–1 variables.     

An addendum on the incremental assignment problem

In Toroslu and Üçoluk [I.H. Toroslu, G. Üçoluk, Incremental assignment problem, Information Sciences 177 (2007) 1523-1529] the incremental assignment problem is defined as follows. A new pair of vertices and their incident edges are added to a weighted bipartite graph whose maximum-weighted matching is already known, and the maximum-weighted matching of the extended graph is sought. An O(n²) algorithm for the problem has been derived, with n the size of a partition in the bipartite graph. We point out that such a result can be found in literature.     

An adaptive guidance approach for the heuristic solution of a minimum multiple trip vehicle routing problem

One of the most important problems in combinatorial optimization is the well-known vehicle routing problem (VRP), which calls for the determination of the optimal routes to be performed by a fleet of vehicles to serve a given set of customers. Recently, there has been an increasing interest towards extensions of VRP arising from real-world applications. In this paper we consider a variant in which time windows for service at the customers are given, and vehicles may perform more than one route within a working shift. We call the resulting problem the minimum multiple trip VRP (MMTVRP), where a “multiple trip” is a sequence of routes corresponding to a working shift for a vehicle. The problem objective is to minimize the overall number of the multiple trips (hence the size of the required fleet), breaking ties in favor of the minimum routing cost.     

A new heuristic for solving the p-median problem in the plane

This paper presents a new local search for solving the continuous p-median problem in the plane. The basic idea is to first find a good starting solution by overlaying the area containing the set of demand points with a grid and solving heuristically the location problem on this grid. The solution is then used as an initial point for running an improved version of Cooper's well-known alternating local search.