An algorithm for separable piecewise convex programming problems

We present a branch and bound algorithm to solve mathematical programming problems of the form: Find x =|(x₁,…x_n) to minimize Σ?_i0(x₁) subject to x?G, l≦x≦L and Σ?_i0(x₁)≦0, j=1,…,m. With l=(l₁,…,l_n) and L=(L₁,…,L_n), each ?_ij is assumed to be lower aemicontinuous and piecewise convex on the finite interval [l_i.L_i]. G is assumed to be a closed convex set. The algorithm solves a finite sequence of convex programming problems; these correspond to successive partitions of the set C={x|l ≦ x ≦L} on the bahis of the piecewise convexity of the problem functions ?_ij. Computational considerations are discussed, and an illustrative example is presented.     

Readiness and the optimal redeployment of resources

This paper considers the problem of the optimal redeployment of a resource among different geographical locations. Initially, it is assumed that at each location i, i = 1,…, n, the level of availability of the resource is given by a₁ ≧ 0. At time t > 0, requirements R_f(t) ≧ 0 are imposed on each location which, in general, will differ from the a₁. The resource can be transported from any one location to any other in magnitudes which will depend on t and the distance between these locations. It is assumed that ΣR_j > Σa_t The objective function consideis, in addition to transportation costs incurred by reallocation, the degree to which the resource availabilities after redeployment differ from the requirements. We shall associate the unavailabilities at the locations with the unreadiness of the system and discuss the optimal redeployment in terms of the minimization of the following functional forms: \documentclass{article}\pagestyle{empty}\begin{document}$ \sum\limits_{j = 1}^n {kj(Rj - yj) + } $\end{document} transportation costs, Max \documentclass{article}\pagestyle{empty}\begin{document}$ \mathop {Max}\limits_j \,[kj(Rj - yj)] + $\end{document} transportation costs, and \documentclass{article}\pagestyle{empty}\begin{document}$ \sum\limits_{j = 1}^n {kj(Rj - yj)^2 + } $\end{document} transportation costs. The variables y_j represent the final amount of the resource available at location j. No benefits are assumed to accrue at any location if y_j > R_j. A numerical three location example is given and solved for the linear objective.     

Pseudo-monotonic interval programming

A pseudo-monotonic interval program is a problem of maximizing f(x) subject to x ε X = {x ε Rⁿ | a < Ax < b, a, b ε R^m} where f is a pseudomonotonic function on X, the set defined by the linear interval constraints. In this paper, an algorithm to solve the above program is proposed. The algorithm is based on solving a finite number of linear interval programs whose solutions techniques are well known. These optimal solutions then yield an optimal solution of the proposed pseudo-monotonic interval program.     

Characterizations of the exponential distribution by higher-order gap

Suppose X₁,X₂, ?,X_n is a random sample of size n from a continuous distribution function F(x) and let X_1,n, ≦ X_2,n ≦ ? ≦ X_n,n be the corresponding order statistics. We define the jth-order gap g_i,j as g_i,j = X_i+j,n ? X_i,n, 1 ≦ i < n, 1 ≦ j ≦ n ? i. In this article characterizations of the exponential distribution are given by considering the distributional properties of g_k,n-k, 1 ≦ k ≦ n.     

Testing fit with nuisance location and scale parameters

For each n, X₁(n),…, X_n(n) are independent and identically distributed random variables, each with cumulative distribution function F(x) which is known to be absolutely continuous but is otherwise unknown. The problem is to test the hypothesis that \documentclass{article}\pagestyle{empty}\begin{document}$ F(x) = G\left( {{\textstyle{{x - \theta _1 } \over {\theta _2 }}}} \right) $\end{document}, where the cumulative distribution function G_x is completely specified and satisfies certain regularity conditions, and the parameters θ₁, θ₂ are unknown and unspecified, except that the scale parameter θ₂, is positive. Y₁ (n) ≦ Y₂ (n) ≦ … ≦ Y_n (n)are the ordered values of X₁(n),…, X_n(n). A test based on a certain subset of {Y_i(n)} is proposed, is shown to have asymptotically a normal distribution when the hypothesis is true, and is shown to be consistent against all alternatives satisfying a mild regularity condition.     

Nonlinear one-parametric linear programming and t-norm transportation problems

Previous methods for solving the nonlinear one-parametric linear programming problem min {c(t)^Tx |Ax = b, x ≥ 0} for t ? [α,β] were based on the simplex method using a considerably extended tableau. The proposed method avoids such an extension. A finite sequence of feasible bases (B^k | k = 1, 2, …, r) optimal in [t^k, t^k+1] for k = 1, 2, …,^r with α = t¹ < t² < … < t^r+1 = β is determined using the zeroes of a set of nonlinear functions. Computational experience is discussed in the special case of t-norm transportation problems.     

Covariance of weibull order statistics

Let X₁ < X₂ <… < X_n denote an ordered sample of size n from a Weibull population with cdf F(x) = 1 - exp (?x^p), x > 0. Formulae for computing Cov (X_i, X_j) are well known, but they are difficult to use in practice. A simple approximation to Cov(X_i, X_j) is presented here, and its accuracy is discussed.     

Optimal allocation of unreliable components for maximizing expected profit over time

In the present paper, we solve the following problem: Determine the optimum redundancy level to maximize the expected profit of a system bringing constant returns over a time period T; i. e., maximize the expression \documentclass{article}\pagestyle{empty}\begin{document}$ P\int_0^T {Rdt - C} $\end{document}, where P is the return of the system per unit of time, R the reliability of this system, C its cost, and T the period for which the system is supposed to work We present theoretical results so as to permit the application of a branch and bound algorithm to solve the problem. We also define the notion of consistency, thereby determining the distinction of two cases and the simplification of the algorithm for one of them.     

A note on a paper by W. Szwarc

In this note the authors call for a change of the optimality criteria given by Theorem 3 in section 5 of the paper of W. Szwarc “On Some Sequencing Problems” in NRLQ Vol. 15, No. 2 [2]. Further, two cases of the three machine problem, namely, (i) ≦ and (ii) ≦ are considered, and procedures for obtaining optimal sequences in these cases are given. In these cases the three-machine problem is solved by solving n (the number of jobs) two-machine problems.     

Optimal replacement policies with two or more loaded sliding standbys

This article defines optimal replacement policies for identical components performing different functions in a given system, when more than one spare part is available. The problem is first formulated for two components and any number of spare parts and the optimal replacement time y(x) at time x is found to have a certain form. Sufficient conditions are then provided for y(x) to be a constant y* for x > y*, and y(x) = x for x > y* (single-critical-number policy). Under the assumption that the optimal policies are of the single-critical-number type, the results are extended to the n-component case, and a theorem is provided that reduces the required number of critical numbers. Finally, the theory is applied to the case of the exponential and uniform failure laws, in which single-critical-number policies are optimal, and to another failure law in which they are not.     

Branch‐and‐price‐and‐cut for the manpower routing problem with synchronization constraints

In this article, we propose a branch‐and‐price‐and‐cut (BPC) algorithm to exactly solve the manpower routing problem with synchronization constraints (MRPSC). Compared with the classical vehicle routing problems (VRPs), the defining characteristic of the MRPSC is that multiple workers are required to work together and start at the same time to carry out a job, that is, the routes of the scheduling subjects are dependent. The incorporation of the synchronization constraints increases the difficulty of the MRPSC significantly and makes the existing VRP exact algorithm inapplicable. Although there are many types of valid inequalities for the VRP or its variants, so far we can only adapt the infeasible path elimination inequality and the weak clique inequality to handle the synchronization constraints in our BPC algorithm. The experimental results at the root node of the branch‐and‐bound tree show that the employed inequalities can effectively improve the lower bound of the problem. Compared with ILOG CPLEX, our BPC algorithm managed to find optimal solutions for more test instances within 1 hour. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 138–171, 2016     

A network isolation algorithm

A set of edges D called an isolation set, is said to isolate a set of nodes R from an undirected network if every chain between the nodes in R contains at least one edge from the set D. Associated with each edge of the network is a positive cost. The isolation problem is concerned with finding an isolation set such that the sum of its edge costs is a minimum. This paper formulates the problem of determining the minimal cost isolation as a 0–1 integer linear programming problem. An algorithm is presented which applies a branch and bound enumerative scheme to a decomposed linear program whose dual subproblems are minimal cost network flow problems. Computational results are given. The problem is also formulated as a special quadratic assignment problem and an algorithm is presented that finds a local optimal solution. This local solution is used for an initial bound.     

Efficient algorithms for flexible job shop scheduling with parallel machines

Job shop scheduling with a bank of machines in parallel is important from both theoretical and practical points of view. Herein we focus on the scheduling problem of minimizing the makespan in a flexible two-center job shop. The first center consists of one machine and the second has k parallel machines. An easy-to-perform approximate algorithm for minimizing the makespan with one-unit-time operations in the first center and k-unit-time operations in the second center is proposed. The algorithm has the absolute worst-case error bound of k − 1 , and thus for k = 1 it is optimal. Importantly, it runs in linear time and its error bound is independent of the number of jobs to be processed. Moreover, the algorithm can be modified to give an optimal schedule for k = 2 .     

Computational techniques for optimizing systems with standby redundancy

Three methods are used to solve the following problem: For P, a positive constant, maximize (P. Reliability-cost) of a system with standby redundancy. The results show that a method which rounds a noninteger solution to the nearest integer solution can lead to tremendous mistakes. However, neither a well known dynamic programming algorithm nor a previously developed branch and bound technique are able to solve large size problems. The solution of problems of large dimension thus requires the use of the noninteger solution of the first method to limit the number of possible solutions when using either the dynamic programming algorithm or a modified branch and bound technique. With this assistance, the branch and bound technique is able to solve large problems in a short amount of computational time.     

An algorithm for 0-1 multiple-knapsack problems

The 0-1 multiple-knapsack problem is an extension of the well-known 0-1 knapsack problem. It is a problem of assigning m objects, each having a value and a weight, to n knapsacks in such a way that the total weight in each knapsack is less than its capacity limit and the total value in the knapsacks is maximized. A branch-and-bound algorithm for solving the problem is developed and tested. Branching rules that avoid the search of redundant partial solutions are used in the algorithm. Various bounding techniques, including Lagrangean and surrogate relaxations, are investigated and compared.     

Bayesian estimation and optimal designs in partially accelerated life testing

A method of life testing is proposed which combines both ordinary and accelerated life-testing procedures. It is assumed that an item can be tested either in a standard environment or under stress. The amount of stress is fixed in advance and is the same for all items to be tested However, the time x at which an item on lest is taken out of the standard environment and put under stress can be chosen by the experimenter subject to a given cost structure. When an item is put under stress its lifetime is changed by the factor α. Let the random variable T denote the lifetime of an item in the standard environment, and let γ denote its lifetime under the partially accelerated test procedure just described. Then Y = T if T ≦ x, and Y = x + α (T > x) if T > x. It is assumed that T has an exponential distribution with parameter θ. The estimation of θ and α and the optimal design of a partially accelerated life test are studied in the framework of Bayesian decision theory.     

The knapsack problem: A survey

A unifying survey of the literature related to the knapsack problem; that is, maximize \documentclass{article}\pagestyle{empty}\begin{document}$ \sum\limits_i {v_i x_{i,} } $\end{document}, subject to \documentclass{article}\pagestyle{empty}\begin{document}$ \sum\limits_j {w_i x_i W} $\end{document} and x_i ? 0, integer; where v_i, w_i and W are known integers, and w_i (i = 1, 2, …, N) and W are positive. Various uses, including those in group theory and in other integer programming algorithms, as well as applications from the literature, are discussed. Dynamic programming, branch and bound, search enumeration, heuristic methods, and other solution techniques are presented. Computational experience, and extensions of the knapsack problem, such as to the multi-dimensional case, are also considered.     

Algorithms for the minimax transportation problem

In this paper, we consider a variant of the classical transportation problem as well as of the bottleneck transportation problem, which we call the minimax transportation problem. The problem considered is to determine a feasible flow x_ij from a set of origins I to a set of destinations J for which max_(i,j)εIxJ{c_ijx_ij} is minimum. In this paper, we develop a parametric algorithm and a primal-dual algorithm to solve this problem. The parametric algorithm solves a transportation problem with parametric upper bounds and the primal-dual algorithm solves a sequence of related maximum flow problems. The primal-dual algorithm is shown to be polynomially bounded. Numerical investigations with both the algorithms are described in detail. The primal-dual algorithm is found to be computationally superior to the parametric algorithm and it can solve problems up to 1000 origins, 1000 destinations and 10,000 arcs in less than 1 minute on a DEC 10 computer system. The optimum solution of the minimax transportation problem may be noninteger. We also suggest a polynomial algorithm to convert this solution into an integer optimum solution.     

Aggregating courier deliveries

We consider the problem of efficiently scheduling deliveries by an uncapacitated courier from a central location under online arrivals. We consider both adversary‐controlled and Poisson arrival processes. In the adversarial setting we provide a randomized (3βΔ/2δ ? 1) ‐competitive algorithm, where β is the approximation ratio of the traveling salesman problem, δ is the minimum distance between the central location and any customer, and Δ is the length of the optimal traveling salesman tour overall customer locations and the central location. We provide instances showing that this analysis is tight. We also prove a 1 + 0.271Δ/δ lower‐bound on the competitive ratio of any algorithm in this setting. In the Poisson setting, we relax our assumption of deterministic travel times by assuming that travel times are distributed with a mean equal to the excursion length. We prove that optimal policies in this setting follow a threshold structure and describe this structure. For the half‐line metric space we bound the performance of the randomized algorithm in the Poisson setting, and show through numerical experiments that the performance of the algorithm is often much better than this bound.