The p-median problem under uncertainty

Consider the need to currently locate p facilities but it is possible that up to q additional facilities will have to be located in the future. There are known probabilities that 0 ? r ? q facilities will need to be located. The p-median problem under uncertainty is to find the location of p facilities such that the expected value of the objective function in the future is minimized. The problem is formulated on a graph, properties of it are proven, an integer programming formulation is constructed, and heuristic algorithms are suggested for its solution. The heuristic algorithms are modified to reduce the run time by about two orders of magnitude with minimal effect on the quality of the solution. Optimal solutions for many problems are found effectively by CPLEX. Computational results using the heuristic algorithms are presented.     

Batch delivery scheduling with batch delivery cost on a single machine

We consider a scheduling problem in which n independent and simultaneously available jobs are to be processed on a single machine. The jobs are delivered in batches and the delivery date of a batch equals the completion time of the last job in the batch. The delivery cost depends on the number of deliveries. The objective is to minimize the sum of the total weighted flow time and delivery cost. We first show that the problem is strongly NP-hard. Then we show that, if the number of batches is B, the problem remains strongly NP-hard when B ? U for a variable U ? 2 or B ? U for any constant U ? 2. For the case of B ? U, we present a dynamic programming algorithm that runs in pseudo-polynomial time for any constant U ? 2. Furthermore, optimal algorithms are provided for two special cases: (i) jobs have a linear precedence constraint, and (ii) jobs satisfy the agreeable ratio assumption, which is valid, for example, when all the weights or all the processing times are equal.     

Bounds for increasing multi-state consecutive k-out-of-r-from-n: F system with equal components probabilities

The consecutive k-out-of-r-from-n: F system was generalized to multi-state case. This system consists of n linearly ordered components which are at state below j if and only if at least k_j components out of any r consecutive are in state below j. In this paper we suggest bounds of increasing multi-state consecutive-k-out-of-r-from-n: F system (k₁ ? k₂ ? ? ? k_M) by applying second order Boole–Bonferroni bounds and applying Hunter–Worsley upper bound. Also numerical results are given. The programs in V.B.6 of the algorithms are available upon request from the authors.     

The domination numbers of cylindrical grid graphs

Let γ(P_m □ C_n) denote the domination number of the cylindrical grid graph formed by the Cartesian product of the graphs P_m, the path of length m, m ? 2 and the graph C_n, the cycle of length n, n ? 3. In this paper, methods to find the domination numbers of graphs of the form P_m □ C_n with n ? 3 and m = 2, 3 and 4 are proposed. Moreover, bounds on domination numbers of the graphs P₅ □ C_n, n ? 3 are found. The methods that are used to prove that results readily lead to algorithms for finding minimum dominating sets of the above mentioned graphs.     

A reduction approach to the repeated assignment problem

We consider the repeated assignment problem (RAP), which is a K-fold repetition of the n × n linear assignment problem (LAP), with the additional requirement that no assignment can be repeated more than once. In actual applications K is typically much smaller than n. First, we derive upper and lower bounds respectively by a heuristic together with local search, and an efficient method solving the continuous relaxation. The latter also solves a Lagrangian relaxation, such that the related pegging test, to fix variables at zero or one, decomposes into K independent pegging tests to LAPs. These can be solved exactly by transforming them into all-pairs shortest path problems. Together with these procedures, we also employ a virtual pegging test and reduce RAP in size. Numerical experiments show that the reduced instances, with K ? n, can be solved exactly using standard MIP solvers.     

Bounding the gap between extremal Laplacian eigenvalues of graphs

Let G be a graph whose Laplacian eigenvalues are 0 = λ₁ ? λ₂ ? ? ? λ_n. We investigate the gap (expressed either as a difference or as a ratio) between the extremal non-trivial Laplacian eigenvalues of a connected graph (that is λ_n and λ₂). This gap is closely related to the average density of cuts in a graph. We focus here on the problem of bounding the gap from below.     

Fault-tolerant edge and vertex pancyclicity in alternating group graphs

In [J.-M. Chang, J.-S. Yang. Fault-tolerant cycle-embedding in alternating group graphs, Appl. Math. Comput. 197 (2008) 760-767] the authors claim that every alternating group graph AG_n is (n − 4)-fault-tolerant edge 4-pancyclic. Which means that if the number of faults ∣F∣ ? n − 4, then every edge in AG_n − F is contained in a cycle of length ?, for every 4 ? ? ? n!/2 − ∣F∣. They also claim that AG_n is (n − 3)-fault-tolerant vertex pancyclic. Which means that if ∣F∣ ? n − 3, then every vertex in AG_n − F is contained in a cycle of length ?, for every 3 ? ? ? n!/2 − ∣F∣. Their proofs are not complete. They left a few important things unexplained. In this paper we fulfill these gaps and present another proofs that AG_n is (n − 4)-fault-tolerant edge 4-pancyclic and (n − 3)-fault-tolerant vertex pancyclic.     

Characterization of the trace by monotonicity inequalities

Let ?be a positive linear functional on the algebra of n × n complex matrices and p be a number greater than 1. The main result of the paper says that if for any pair A, B of positive semi-definite n × n matrices with A ? B the inequality ?(A^p) ? ?(B^p) holds true, then ?is a nonnegative scalar multiple of the trace.     

Bipanconnectivity of faulty hypercubes with minimum degree

In this paper, we consider the conditionally faulty hypercube Q_n with n ? 2 where each vertex of Q_n is incident with at least m fault-free edges, 2 ? m ? n − 1. We shall generalize the limitation m ? 2 in all previous results of edge-bipancyclicity. We also propose a new edge-fault-tolerant bipanconnectivity called k-edge-fault-tolerant bipanconnectivity. A bipartite graph is k-edge-fault-tolerant bipanconnected if G − F remains bipanconnected for any F ⊂ E(G) with ∣F∣ ? k. For every integer m, under the same hypothesis, we show that Q_n is (n − 2)-edge-fault-tolerant edge-bipancyclic and bipanconnected, and the results are optimal with respect to the number of edge faults tolerated. This not only improves some known results on edge-bipancyclicity and bipanconnectivity of hypercubes, but also simplifies the proof.     

k-Potence preserving maps without the linearity and surjectivity assumptions

Let M_n be the space of all n × n complex matrices, and let Γ_n be the subset of M_n consisting of all n × n k-potent matrices. We denote by Ψ_n the set of all maps on M_n satisfying A − λB ∈ Γ_n if and only if ?(A) − λ?(B) ∈ Γ_n for every A,B ∈ M_n and λ ∈ C. It was shown that ? ∈ Ψ_n if and only if there exist an invertible matrix P ∈ M_n and c ∈ C with c^k−1 = 1 such that either ?(A) = cPAP⁻¹ for every A ∈ M_n, or ?(A) = cPA^TP⁻¹ for every A ∈ M_n.     

Classification of small (0, 1) matrices

Denote by A_n the set of square (0, 1) matrices of order n. The set A_n, n ? 8, is partitioned into row/column permutation equivalence classes enabling derivation of various facts by simple counting. For example, the number of regular (0, 1) matrices of order 8 is 10160459763342013440. Let D_n, S_n denote the set of absolute determinant values and Smith normal forms of matrices from A_n. Denote by a_n the smallest integer not in D_n. The sets D₉ and S₉ are obtained; especially, a₉ = 103. The lower bounds for a_n, 10 ? n ? 19 (exceeding the known lower bound a_n ? 2f_n − 1, where f_n is nth Fibonacci number) are obtained. Row/permutation equivalence classes of A_n correspond to bipartite graphs with n black and n white vertices, and so the other applications of the classification are possible.     

Haplotyping populations by pure parsimony based on compatible genotypes and greedy heuristics

The population haplotype inference problem based on the pure parsimony criterion (HIPP) infers an m × n genotype matrix for a population by a 2m × n haplotype matrix with the minimum number of distinct haplotypes. Previous integer programming based HIPP solution methods are time-consuming, and their practical effectiveness remains unevaluated. On the other hand, previous heuristic HIPP algorithms are efficient, but their theoretical effectiveness in terms of optimality gaps has not been evaluated, either. We propose two new heuristic HIPP algorithms (MGP and GHI) and conduct more complete computational experiments. In particular, MGP exploits the compatible relations among genotypes to solve a reduced integer linear programming problem so that a solution of good quality can be obtained very quickly; GHI exploits a weight mechanism to selects better candidate haplotypes in a greedy fashion. The computational results show that our proposed algorithms are efficient and effective, especially for solving cases with larger recombination rates.     

Approximate methods for convex minimization problems with series–parallel structure

Consider a problem of minimizing a separable, strictly convex, monotone and differentiable function on a convex polyhedron generated by a system of m linear inequalities. The problem has a series–parallel structure, with the variables divided serially into n disjoint subsets, whose elements are considered in parallel. This special structure is exploited in two algorithms proposed here for the approximate solution of the problem. The first algorithm solves at most min{m, ν − n + 1} subproblems; each subproblem has exactly one equality constraint and at most n variables. The second algorithm solves a dynamically generated sequence of subproblems; each subproblem has at most ν − n + 1 equality constraints, where ν is the total number of variables. To solve these subproblems both algorithms use the authors’ Projected Newton Bracketing method for linearly constrained convex minimization, in conjunction with the steepest descent method. We report the results of numerical experiments for both algorithms.     

Bounds on convex reliability functions with known first moments

In this paper, upper and lower bounds are derived for convex reliability functions (or survival functions) with known first n moments. The case where the mean and the variance are given (n = 2) is discussed in details and explicit expressions are provided. Extensions for n ? 3 moments are described. Comparisons with existing bounds are performed.     

A comparison of two methods for solving 0–1 integer programs using a general purpose simulated annealing algorithm

0–1 problems are often difficult to solve. Although special purpose algorithms (exact as well as heuristic) exist for solving particular problem classes or problem instances, there are few general purpose algorithms for solving practical-sized instances of 0–1 problems. This paper deals with a general purpose heuristic algorithm for 0–1 problems. In this paper, we compare two methods based on simulated annealing for solving general 0–1 integer programming problems. The two methods differe in the scheme used for neighbourhood transitions in the simulated annealing framework. We compare the performance of the two methods on the set partitioning problem.     

On extremal matrices of second largest exponent by Boolean rank

Let b = b(A) be the Boolean rank of an n × n primitive Boolean matrix A and exp(A) be the exponent of A. Then exp(A) ? (b − 1)² + 2, and the matrices for which equality occurs have been determined in [D.A. Gregory, S.J. Kirkland, N.J. Pullman, A bound on the exponent of a primitive matrix using Boolean rank, Linear Algebra Appl. 217 (1995) 101-116]. In this paper, we show that for each 3 ? b ? n − 1, there are n × n primitive Boolean matrices A with b(A) = b such that exp(A) = (b − 1)² + 1, and we explicitly describe all such matrices.     

Super connectivity of k-regular interconnection networks

Super connectivity is an important issue in interconnection networks. It has been shown that if a network possesses the super connectivity property, it has a high reliability and a small vertex failure rate. Many interconnection networks, like the hypercubes, twisted-cubes, crossed-cubes, möbius cubes, split-stars, and recursive circulant graphs, are proven to be super connected; and the augmented cubes are maximum connected. However, each network vertex has a higher degree as long as the number of vertices increases exponentially. For example, each vertex of the hypercube Q_n has a degree of n, and each vertex of the augmented cube AQ_n has a degree of 2n − 1. In this paper, we not only show that the augmented cube AQ_n is super connected for n = 1, 2 and n ? 4, but also propose a variation of AQ_n, denoted by AQ_n,i, such that V(AQ_n,i) = V(AQ_n), E(AQ_n,i) ⊆ E(AQ_n), and AQ_n,i is i-regular with n ? 3 and 3 ? i ? 2n − 1, in which AQ_n,i is also super connected. In addition, we state the diameter of AQ_n,i.     

Probability of unique integer solution to a system of linear equations

We consider a system of m linear equations in n variables Ax = d and give necessary and sufficient conditions for the existence of a unique solution to the system that is integer: x ∈ {−1, 1}ⁿ. We achieve this by reformulating the problem as a linear program and deriving necessary and sufficient conditions for the integer solution to be the unique primal optimal solution. We show that as long as m is larger than n/2, then the linear programming reformulation succeeds for most instances, but if m is less than n/2, the reformulation fails on most instances. We also demonstrate that these predictions match the empirical performance of the linear programming formulation to very high accuracy.     

Optimal algorithms for the α-neighbor p-center problem

Assigning multiple service facilities to demand points is important when demand points are required to withstand service facility failures. Such failures may result from a multitude of causes, ranging from technical difficulties to natural disasters. The α-neighbor p-center problem deals with locating p service facilities. Each demand point is assigned to its nearest α service facilities, thus it is able to withstand up to α − 1 service facility failures. The objective is to minimize the maximum distance between a demand point and its αth nearest service facility. We present two optimal algorithms for both the continuous and discrete α-neighbor p-center problem. We present experimental results comparing the performance of the two optimal algorithms for α = 2. We also present experimental results showing the performance of the relaxation algorithm for α = 1, 2, 3.