On a cone covering problem

Given a set of polyhedral cones C₁,…,Ck⊂Rd, and a convex set D, does the union of these cones cover the set D? In this paper we consider the computational complexity of this problem for various cases such as whether the cones are defined by extreme rays or facets, and whether D is the entire Rd or a given linear subspace Rt. As a consequence, we show that it is coNP-complete to decide if the union of a given set of convex polytopes is convex, thus answering a question of Bemporad, Fukuda and Torrisi.     

A probabilistic heuristic for a computationally difficult set covering problem

An efficient probabilistic set covering heuristic is presented. The heuristic is evaluated on empirically difficult to solve set covering problems that arise from Steiner triple systems. The optimal solution to only a few of these instances is known. The heuristic provides these solutions as well as the best known solutions to all other instances attempted.     

A-priori upper bounds for the set covering problem

A matrix M∈R^n×n is said to be a column sufficient matrix if the solution set of LCP(M,q) is convex for every q∈Rⁿ. In a recent article, Qin et al. (Optim. Lett. 3:265–276, 2009) studied the concept of column sufficiency property in Euclidean Jordan algebras. In this paper, we make a further study of this concept and prove numerous results relating column sufficiency with the Z and Lypaunov-like properties. We also study this property for some special linear transformations.     

An inverse eigenvalue problem and a matrix approximation problem for symmetric skew-hamiltonian matrices

Based on the theory of inverse eigenvalue problem, a correction of an approximate model is discussed, which can be formulated as NX=XΛ, where X and Λ are given identified modal and eigenvalues matrices, respectively. The solvability conditions for a symmetric skew-Hamiltonian matrix N are established and an explicit expression of the solutions is derived. For any estimated matrix C of the analytical model, the best approximation matrix to minimize the Frobenius norm of C − N is provided and some numerical results are presented. A perturbation analysis of the solution is also performed, which has scarcely appeared in existing literatures. Supported by the National Natural Science Foundation of China(10571012, 10771022), the Beijing Natural Science Foundation (1062005) and the Beijing Educational Committee Foundation (KM200411232006, KM200611232010).     

An eigenvalue problem for derogatory matrices

A matrix A is called derogatory   if there is more than one Jordan submatrix associated with an eigenvalue λ$\lambda$. In this paper, we are concerned with the eigenvalue problem of this type of matrices.     

Solving a minimum-power covering problem with overlap constraint for cellular network design

We consider a type of covering problem in cellular networks. Given the locations of base stations, the problem amounts to determining cell coverage at minimum cost in terms of the power usage. Overlap between adjacent cells is required in order to support handover. The problem we consider is NP-hard. We present integer linear models and study the strengths of their continuous relaxations. Preprocessing is used to reduce problem size and tighten the models. Moreover, we design a tabu search algorithm for finding near-optimal solutions effectively and time-efficiently. We report computational results for both synthesized instances and networks originating from real planning scenarios. The results show that one of the integer models leads to tight bounds, and the tabu search algorithm generates high-quality solutions for large instances in short computing time.     

Design of a heuristic algorithm for the generalized multi-objective set covering problem

Computational Optimization and Applications - Set covering optimization problems (SCPs) are important and of broad interest because of their extensive applications in the real world. This study...     

An iterated-tabu-search heuristic for a variant of the partial set covering problem

In this paper, we propose a heuristic algorithm to solve a new variant of the partial set covering problem. In this variant, each element $e_i$ has a gain $g_i$ (i.e., a positive profit), each set $s_j$ has a cost $c_j$ (i.e., a negative profit), and each set $s_j$ is part of a unique group $G_k$ that has a fixed cost $f_k$ (i.e., a negative profit). The objective is to maximize profit and it is not necessary to cover all of the elements. We present an industrial application of the model and propose a hybrid heuristic algorithm to solve it; the proposed algorithm is an iterated-local-search algorithm that uses two levels of perturbations and a tabu-search heuristic. Whereas the first level of perturbation diversifies the search around the current local optimum, the second level of perturbation performs long jumps in the search space to help escape from local optima with large basins of attraction. The proposed algorithm is evaluated on thirty real-world problems and compared to a memetic algorithm. Computational results show that most of the solutions found by ITS are either optimal or very close to optimality.     

A tabu search algorithm for the covering design problem

A (v,k,t)-covering design is a collection of k-subsets (called blocks) of a v-set V{\mathcal{V}} such that every t-subset of V{\mathcal{V}} is contained in at least one block. Given v, k and t, the goal of the covering design problem is to find a covering made of a minimum number of blocks. In this paper, we present a new tabu algorithm for tackling this problem. Our algorithm exploits a new implementation designed in order to evaluate efficiently the performance of the neighbors of the current configuration. The new implementation is much less space-consuming than the currently used technique, making it possible to tackle much larger problem instances. It is also significantly faster. Thanks to these improved data structures, our tabu algorithm was able to improve the upper bound of more than 50 problem instances.     

Solving the eigenvalue problem for sparse matrices

A modification of the Danilewski method is presented, permitting the solution of the eigenvalue problem for a constant sparse matrix of large order to be reduced to the solution of the same problem for a polynomial matrix of lower order. Certain solution algorithms are proposed for a partial eigenvalue problem for the polynomial matrix. Questions of the realization of the algorithms on a model PRORAB computer are examined.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 58, pp. 92–110, 1976.     

An extremal problem for positive defintie matrices

A problem studied by Flanders (1975) is minimize the function f(R)=tr(SR+TR^-1) over the set of positive definite matrices R, where S and T are positive semi-definite matrices. Alternative proofs that may have some intrinsic interest are provided. The proofs explicitly yield the infimum of f(R). One proof is based on a convexity argument and the other on a sequence of reductions to a univariate problem.     

The realization of positive definite matrices via planar networks and mixing-type sub-cluster algebras

As an improvement of the combinatorial realization of totally positive matrices via the essential positive weightings of certain planar network by S.Fomin and A.Zelevinsky [7], in this paper,we give a test method of positive definite matrices via the planar networks and the so-called mixing-type sub-cluster algebras respectively,introduced here originally.This work firstly gives a combinatorial realization of all matrices through planar network,and then sets up a test method for positive definite matrices by LDU-decompositions and the horizontal weightings of all lines in their planar networks.On the other hand,mainly the relationship is built between positive definite matrices and mixing-type sub-cluster algebras.     

On a linearization technique for solving the quadratic set covering problem and variations

In this paper we identify various inaccuracies in the paper by Saxena and Arora (Optimization 39:33–42, 1997). In particular, we observe that their algorithm does not guarantee optimality, contrary to what is claimed. Experimental analysis has been carried out to assess the value of this algorithm as a heuristic. The results disclose that for some classes of problems the Saxena–Arora algorithm is effective in achieving good quality solutions while for some other classes of problems, its performance is poor. We also discuss similar inaccuracies in another related paper.     

An effective and simple heuristic for the set covering problem

This paper investigates the development of an effective heuristic to solve the set covering problem (SCP) by applying the meta-heuristic Meta-RaPS (Meta-heuristic for Randomized Priority Search). In Meta-RaPS, a feasible solution is generated by introducing random factors into a construction method. Then the feasible solutions can be improved by an improvement heuristic. In addition to applying the basic Meta-RaPS, the heuristic developed herein integrates the elements of randomizing the selection of priority rules, penalizing the worst columns when the searching space is highly condensed, and defining the core problem to speedup the algorithm. This heuristic has been tested on 80 SCP instances from the OR-Library. The sizes of the problems are up to 1000 rows × 10,000 columns for non-unicost SCP, and 28,160 rows × 11,264 columns for the unicost SCP. This heuristic is only one of two known SCP heuristics to find all optimal/best known solutions for those non-unicost instances. In addition, this heuristic is the best for unicost problems among the heuristics in terms of solution quality. Furthermore, evolving from a simple greedy heuristic, it is simple and easy to code. This heuristic enriches the options of practitioners in the optimization area.     

Exact algorithm for solving a special fixed-charge linear programming problem

A branch-and-bound algorithm (A) for solving a fixed-charge linear programming problem (P) involving identical fixed charges, one equality constraint, and explicit bounds on the variables is presented. Problem (P) can serve as a mathematical model for profit optimization in sawn timber production. Some theoretical considerations upon a fixed-charge problem (P), arising from (P) by permitting the fixed charges to be different for each variable, are carried out. A basic algorithm (A₀) is stated, and it is proved that Algorithm (A₀) finds an optimal solution of Problem (P) [resp., (P)] within a finite number of steps. Algorithm (A₀), combined with bounds developed with regard to Problem (P), yields Algorithm (A), which operates on a subset of all vertices of the feasible region. Finally, computational results concerning the numerical solution of Problem (P) by Algorithm (A) are stated.A part of this work was carried out in connection with the project Optimierung der Schnittholzproducktion auf Zerspaneranlagen, which was done at the Institute of Mathematics of the University of Klagenfurt in cooperation with the firm J. Offner, Holzindustrie GmbH, Wolfsberg. This project was partially supported by Forschungsförderungsfonds für die gewerbliche Wirtschaft. The author would like to thank Professor H. Stettner, C. Nowak, and H. Woschitz for their support and G. Stoiser for his help in achieving the numerical results.