A branch‐and‐price approach for the stochastic generalized assignment problem

In this article, we address a stochastic generalized assignment machine scheduling problem in which the processing times of jobs are assumed to be random variables. We develop a branch‐and‐price (B&P) approach for solving this problem wherein the pricing problem is separable with respect to each machine, and has the structure of a multidimensional knapsack problem. In addition, we explore two other extensions of this method—one that utilizes a dual‐stabilization technique and another that incorporates an advanced‐start procedure to obtain an initial feasible solution. We compare the performance of these methods with that of the branch‐and‐cut (B&C) method within CPLEX. Our results show that all B&P‐based approaches perform better than the B&C method, with the best performance obtained for the B&P procedure that includes both the extensions aforementioned. We also utilize a Monte Carlo method within the B&P scheme, which affords the use of a small subset of scenarios at a time to estimate the “true” optimal objective function value. Our experimental investigation reveals that this approach readily yields solutions lying within 5% of optimality, while providing more than a 10‐fold savings in CPU times in comparison with the best of the other proposed B&P procedures. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 131–143, 2014     

The knapsack problem with a minimum filling constraint

We study a knapsack problem with an additional minimum filling constraint, such that the total weight of selected items cannot be less than a given threshold. The problem has several applications in shipping, e‐commerce, and transportation service procurement. When the threshold equals the knapsack capacity, even finding a feasible solution to the problem is NP‐hard. Therefore, we consider the case when the ratio α of threshold to capacity is less than 1. For this case, we develop an approximation scheme that returns a feasible solution with a total profit not less than (1 ‐ ε) times the total profit of an optimal solution for any ε > 0, and with a running time polynomial in the number of items, 1/ε, and 1/(1‐α). © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Concise RLT forms of binary programs: A computational study of the quadratic knapsack problem

The reformulation‐linearization technique (RLT) is a methodology for constructing tight linear programming relaxations of mixed discrete problems. A key construct is the multiplication of “product factors” of the discrete variables with problem constraints to form polynomial restrictions, which are subsequently linearized. For special problem forms, the structure of these linearized constraints tends to suggest that certain classes may be more beneficial than others. We examine the usefulness of subsets of constraints for a family of 0–1 quadratic multidimensional knapsack programs and perform extensive computational tests on a classical special case known as the 0–1 quadratic knapsack problem. We consider RLT forms both with and without these inequalities, and their comparisons with linearizations derived from published methods. Interestingly, the computational results depend in part upon the commercial software used. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

The minmax multidimensional knapsack problem with application to a chance‐constrained problem

In this paper we present a new combinatorial problem, called minmax multidimensional knapsack problem (MKP), motivated by a military logistics problem. The logistics problem is a two‐period, two‐level, chance‐constrained problem with recourse. We show that the MKP is NP‐hard and develop a practically efficient combinatorial algorithm for solving it. We also show that under some reasonable assumptions regarding the operational setting of the logistics problem, the chance‐constrained optimization problem is decomposable into a series of MKPs that are solved separately. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

A sequential scheduling problem with impatient jobs

There are n customers that need to be served. Customer i will only wait in queue for an exponentially distributed time with rate λ_i before departing the system. The service time of customer i has distribution F_i, and on completion of service of customer i a positive reward r_i is earned. There is a single server and the problem is to choose, after each service completion, which currently in queue customer to serve next so as to maximize the expected total return. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 659–663, 2015     

Analysis of a machine repair problem with an unreliable server and phase type repairs and services

In this paper we study a machine repair problem in which a single unreliable server maintains N identical machines. The breakdown times of the machines are assumed to follow an exponential distribution. The server is subject to failure and the failure times are exponentially distributed. The repair times of the machine and the service times of the repairman are assumed to be of phase type. Using matrix‐analytic methods, we perform steady state analysis of this model. The time spent by a failed machine in service and the total time in the repair facility are shown to be of phase type. Several performance measures are evaluated. An optimization problem to determine the number of machines to be assigned to the server that will maximize the expected total profit per unit time is discussed. An illustrative numerical example is presented. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 462–480, 2003     

An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns

We consider the stochastic linear knapsack problem in which costs are known with certainty but returns are independent, normally distributed random variables. The objective is to maximize the probability that the overall return equals or exceeds a specified target value. A previously proposed preference order dynamic programming-based algorithm has been shown to be potentially suboptimal. We offer an alternative hybrid DP/branch-and-bound algorithm that both guarantees optimality and significantly outperforms generating the set of Pareto optimal returns.© 1993 John Wiley & Sons, Inc.     

Limiting behavior of the stochastic sequential assignment problem

The stochastic sequential assignment problem (SSAP) considers how to allocate available distinct workers to sequentially arriving tasks with stochastic parameters such that the expected total reward obtained from the sequential assignments is maximized. Implementing the optimal assignment policy for the SSAP involves calculating a new set of breakpoints upon the arrival of each task (i.e., for every time period), which is impractical for large‐scale problems. This article studies two problems that are concerned with obtaining stationary policies, which achieve the optimal expected reward per task as the number of tasks approaches infinity. The first problem considers independent and identically distributed (IID) tasks with a known distribution function, whereas in the second problem tasks are derived from r different unobservable distributions governed by an ergodic Markov chain. The convergence rate of the expected reward per task to the optimal value is also obtained for both problems. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

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.     

A mathematical programming approach for improving the robustness of least sum of absolute deviations regression

This paper discusses a novel application of mathematical programming techniques to a regression problem. While least squares regression techniques have been used for a long time, it is known that their robustness properties are not desirable. Specifically, the estimators are known to be too sensitive to data contamination. In this paper we examine regressions based on Least‐sum of Absolute Deviations (LAD) and show that the robustness of the estimator can be improved significantly through a judicious choice of weights. The problem of finding optimum weights is formulated as a nonlinear mixed integer program, which is too difficult to solve exactly in general. We demonstrate that our problem is equivalent to a mathematical program with a single functional constraint resembling the knapsack problem and then solve it for a special case. We then generalize this solution to general regression designs. Furthermore, we provide an efficient algorithm to solve the general nonlinear, mixed integer programming problem when the number of predictors is small. We show the efficacy of the weighted LAD estimator using numerical examples. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Dynamic programming approaches to the multiple criteria knapsack problem

We study the integer multiple criteria knapsack problem and propose dynamic‐programming‐based approaches to finding all the nondominated solutions. Different and more complex models are discussed, including the binary multiple criteria knapsack problem, problems with more than one constraint, and multiperiod as well as time‐dependent models. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 57–76, 2000     

A branch‐and‐price algorithm for a targeting problem

In this paper, we consider a new weapon‐target allocation problem with the objective of minimizing the overall firing cost. The problem is formulated as a nonlinear integer programming model, but it can be transformed into a linear integer programming model. We present a branch‐and‐price algorithm for the problem employing the disaggregated formulation, which has exponentially many columns denoting the feasible allocations of weapon systems to each target. A greedy‐style heuristic is used to get some initial columns to start the column generation. A branching strategy compatible with the pricing problem is also proposed. Computational results using randomly generated data show this approach is promising for the targeting problem. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Generalized orienteering problem with resource dependent rewards

We introduce a generalized orienteering problem (OP) where, as usual, a vehicle is routed from a prescribed start node, through a directed network, to a prescribed destination node, collecting rewards at each node visited, to maximize the total reward along the path. In our generalization, transit on arcs in the network and reward collection at nodes both consume a variable amount of the same limited resource. We exploit this resource trade‐off through a specialized branch‐and‐bound algorithm that relies on partial path relaxation problems that often yield tight bounds and lead to substantial pruning in the enumeration tree. We present the smuggler search problem (SSP) as an important real‐world application of our generalized OP. Numerical results show that our algorithm applied to the SSP outperforms standard mixed‐integer nonlinear programming solvers for moderate to large problem instances. We demonstrate model enhancements that allow practitioners to represent realistic search planning scenarios by accounting for multiple heterogeneous searchers and complex smuggler motion. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

A lost sales (S — 1, S) perishable inventory system with renewal demand

This article analyzes a one-to-one ordering perishable inventory model with renewal demands and exponential lifetimes. The leadtimes are independently and exponentially distributed and the demands that occur during stock out periods are lost. Although the items are assumed to decay at a constant rate, the output process is not renewal and the Markov renewal techniques are successfully employed to obtain the operating characteristics. The problem of minimizing the long run expected cost rate is discussed and numerical values of optimal stock level are also provided. © 1996 John Wiley & Sons, Inc.     

Decentralized admission control of a queueing system: A game‐theoretic model

Consider a distributed system where many gatekeepers share a single server. Customers arrive at each gatekeeper according to independent Poisson processes with different rates. Upon arrival of a new customer, the gatekeeper has to decide whether to admit the customer by sending it to the server, or to block it. Blocking costs nothing. The gatekeeper receives a reward after a customer completes the service, and incurs a cost if an admitted customer finds a busy server and therefore has to leave the system. Assuming an exponential service distribution, we formulate the problem as an n‐person non‐zero‐sum game in which each gatekeeper is interested in maximizing its own long‐run average reward. The key result is that each gatekeeper's optimal policy is that of a threshold type regardless what other gatekeepers do. We then derive Nash equilibria and discuss interesting insights. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 702–718, 2003.     

Balancing and optimizing a portfolio of R&D projects

A mathematical formulation of an optimization model designed to select projects for inclusion in an R&D portfolio, subject to a wide variety of constraints (e.g., capital, headcount, strategic intent, etc.), is presented. The model is similar to others that have previously appeared in the literature and is in the form of a mixed integer programming (MIP) problem known as the multidimensional knapsack problem. Exact solution of such problems is generally difficult, but can be accomplished in reasonable time using specialized algorithms. The main contribution of this paper is an examination of two important issues related to formulation of project selection models such as the one presented here. If partial funding and implementation of projects is allowed, the resulting formulation is a linear programming (LP) problem which can be solved quite easily. Several plausible assumptions about how partial funding impacts project value are presented. In general, our examples suggest that the problem might best be formulated as a nonlinear programming (NLP) problem, but that there is a need for further research to determine an appropriate expression for the value of a partially funded project. In light of that gap in the current body of knowledge and for practical reasons, the LP relaxation of this model is preferred. The LP relaxation can be implemented in a spreadsheet (even for relatively large problems) and gives reasonable results when applied to a test problem based on GM's R&D project selection process. There has been much discussion in the literature on the topic of assigning a quantitative measure of value to each project. Although many alternatives are suggested, no one way is universally accepted as the preferred way. There does seem to be general agreement that all of the proposed methods are subject to considerable uncertainty. A systematic way to examine the sensitivity of project selection decisions to variations in the measure of value is developed. It is shown that the solution for the illustrative problem is reasonably robust to rather large variations in the measure of value. We cannot, however, conclude that this would be the case in general. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 18–40, 2001     

A heuristic routine for solving large loading problems

The loading problem involves the optimal allocation of n objects, each having a specified weight and value, to m boxes, each of specified capacity. While special cases of these problems can be solved with relative ease, the general problem having variable item weights and box sizes can become very difficult to solve. This paper presents a heuristic procedure for solving large loading problems of the more general type. The procedure uses a surrogate procedure for reducing the original problem to a simpler knapsack problem, the solution of which is then employed in searching for feasible solutions to the original problem. The procedure is easy to apply, and is capable of identifying optimal solutions if they are found.     

Note: The economic manufacturing lot-sizing problem with imperfect production processes: Bounds and optimal solutions

In this paper, we consider the economic production quantity problem in the presence of imperfect processes. In the literature, the time to shift from the in-control state to the out-of-control state is assumed to be exponentially distributed. In this study, we consider general time to shift distributions and provide distribution-based and distribution-free bounds on the optimal cost. For the exponential case, we compare the optimal solutions to approximate solutions proposed in the literature. A numerical example is used to illustrate the analysis presented and to conduct a sensitivity analysis in order to see the effect of the input parameters on the various solutions to the problem. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 423–433, 1998     

Bicriteria multiresource generalized assignment problem

In this study, we consider a bicriteria multiresource generalized assignment problem. Our criteria are the total assignment load and maximum assignment load over all agents. We aim to generate all nondominated objective vectors and the corresponding efficient solutions. We propose several lower and upper bounds and use them in our optimization and heuristic algorithms. The computational results have shown the satisfactory behaviors of our approaches. © 2014 Wiley Periodicals, Inc. Naval Research Logistics, 61: 621–636, 2014     

Solving the generalized knapsack problem with variable coefficients

In this article we present methods based on Lagrangian duality and decomposition techniques for the generalized knapsack problem with variable coefficients. The Lagrangian dual is solved with subgradient optimization or interval bisection. We also describe a heuristic that yields primal feasible solutions. Combining the Lagrangian relaxation with a primal (Benders) subproblem yields the subproblem phase in cross decomposition. By using averages in this procedure, we get the new mean-value cross-decomposition method. Finally, we describe how to insert this into a globally convergent generalized Benders decomposition framework, in the case that there is a duality gap. Encouraging computational results for the optimal generating unit commitment problem are presented. © 1996 John Wiley & Sons, Inc.