Project selection,scheduling and resource allocation with time dependent returns

In this paper we formulate and analyze the joint problem of project selection and task scheduling. We study the situation where a manager has many alternative projects to pursue such as developing new product platforms or technologies, incremental product upgrades, or continuing education of human resources. Project return is assumed to be a known function of project completion time. Resources are limited and renewable. The objective is to maximize present worth of profit. A general mathematical formulation that can address several versions of the problem is presented. An implicit enumeration procedure is then developed and tested to provide good solutions based on project ordering and a prioritization rule for resource allocation. The algorithm uses an imbedded module for solving the resource-constrained project scheduling problem at each stage. The importance of integrating the impact of resource constraints into the selection of projects is demonstrated.     

Locating and staffing service centers under service level constraints

Many firms experience demand from geographically dispersed customers. This demand is satisfied by mobile servers that travel to the site of the customer. To achieve this in a cost-effective manner, the firm needs to decide where to locate its service centers, which customer regions to assign to the centers and the staffing level   at each center so that customers experience a defined level of service at minimum cost. To determine adequate staffing levels, we approximate a service center and the customer regions assigned to it as an M/G/s$M/G/s$ queueing system. Based on this queueing model, we explore properties of two different staffing level functions. The queueing model is embedded in a large-scale integer program. Using the concept of column generation, we develop an algorithm that can efficiently solve moderate-sized problems.     

Exact and heuristic solution approaches for the mixed integer setup knapsack problem

We consider a class of knapsack problems that include setup costs for families of items. An individual item can be loaded into the knapsack only if a setup cost is incurred for the family to which it belongs. A mixed integer programming formulation for the problem is provided along with exact and heuristic solution methods. The exact algorithm uses cross decomposition. The proposed heuristic gives fast and tight bounds. In addition, a Benders decomposition algorithm is presented to solve the continuous relaxation of the problem. This method for solving the continuous relaxation can be used to improve the performance of a branch and bound algorithm for solving the integer problem. Computational performance of the algorithms are reported and compared to CPLEX.     

The splitting of variables and constraints in the formulation of integer programming models

The splitting of variables in an integer programming model into the sum of other variables can allow the constraints to be disaggregated, leading to a more constrained (tighter) linear programming relaxation. Well known examples of such reformulations are quoted from the literature. They can be viewed as instances of some general methods of performing such reformulations, namely disjunctive formulations, partial network reformulations and a method based on the introduction of auxiliary variables.     

Zero-one integer programs with few constraints —Efficient branch and bound algorithms

The 0–1 integer programming problem and its special case, the 0–1 knapsack problem are frequently encountered in modeling various design and decision making processes. This paper is a follow-up paper to [4] and deals with the development of an effective solution procedure for 0–1 integer programs with few constraints. Detailed computational experiments are carried out and different separation, branching and bounding rules are compared using an experimental branch and bound code. An efficient branch and bound procedure is developed, tested and compared with previously developed optimal algorithms. It is suggested that this procedure may also be used as a heuristic method for large problems by early termination of the tree search. This scheme is tested and found to be very effective.     

On multistage Stochastic Integer Programming for incorporating logical constraints in asset and liability management under uncertainty

We present a model for optimizing a mean-risk function of the terminal wealth for a fixed income asset portfolio restructuring with uncertainty in the interest rate path and the liabilities along a given time horizon. Some logical constraints are considered to be satisfied by the assets portfolio. Uncertainty is represented by a scenario tree and is dealt with by a multistage stochastic mixed 0-1 model with complete recourse. The problem is modelled as a splitting variable representation of the Deterministic Equivalent Model for the stochastic model, where the 0-1 variables and the continuous variables appear at any stage. A Branch-and-Fix Coordination approach for the multistage 0–1 program solving is proposed. Some computational experience is reported.      

Exploiting nested inequalities and surrogate constraints

The exploitation of nested inequalities and surrogate constraints as originally proposed in Glover [Glover, F., 1965. A multiphase-dual algorithm for the zero–one integer programming problem. Operations Research 13, 879–919; Glover, F., 1971. Flows in arborescences. Management Science 17, 568–586] has been specialized to multidimensional knapsack problems in Osorio et al. [Osorio, M.A., Glover, F., Hammer, P., 2002. Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions. Annals of Operations Research 117, 71–93]. We show how this specialized exploitation can be strengthened to give better results. This outcome results by a series of observations based on surrogate constraint duality and properties of nested inequalities. The consequences of these observations are illustrated by numerical examples to provide insights into uses of surrogate constraints and nested inequalities that can be useful in a variety of problem settings.     

Formulations and valid inequalities for the node capacitated graph partitioning problem

We investigate the problem of partitioning the nodes of a graph under capacity restriction on the sum of the node weights in each subset of the partition. The objective is to minimize the sum of the costs of the edges between the subsets of the partition. This problem has a variety of applications, for instance in the design of electronic circuits and devices. We present alternative integer programming formulations for this problem and discuss the links between these formulations. Having chosen to work in the space of edges of the multicut, we investigate the convex hull of incidence vectors of feasible multicuts. In particular, several classes of inequalities are introduced, and their strength and robustness are analyzed as various problem parameters change.     

Mobility allowance shuttle transit (MAST) services: MIP formulation and strengthening with logic constraints

We study a hybrid transportation system referred to as mobility allowance shuttle transit (MAST) where vehicles may deviate from a fixed path consisting of a few mandatory checkpoints to serve demand distributed within a proper service area. In this paper we propose a mixed integer programming (MIP) formulation for the static scheduling problem of a MAST type system. Since the problem is NP-Hard, we develop sets of logic cuts, by using reasonable assumptions on passengers’ behavior. The purpose of these constraints is to speed up the search for optimality by removing inefficient solutions from the original feasible region. Experiments show the effectiveness of the developed inequalities, achieving a reduction up to 90% of the CPU solving time for some of the instances.     

Portfolio selection with transaction costs under expected shortfall constraints

An investor subject to proportional transaction costs allocates funds to multiple stocks and a bank account, to maximise the expected growth rate of the portfolio value under Expected Shortfall (ES) constraints. In a numerical example with ten time steps and one stock important innovations are caused by the introduction of the Expected Shortfall constraint: First, expected returns are reduced by less than one-tenth when the ES constraint is introduced. In comparison, economic capital as measured by ES, is reduced to amounts between one-half and three-quarters, when the ES constraint is introduced. Second, the dependence of expected return and ES on the initial portfolio, in particular when transaction costs are high, is largely removed by the introduction of the ES constraint.     

The transportation problem with exclusionary side constraints and two branch-and-bound algorithms

The transportation problem with exclusionary side constraints, a practical distribution and logistics problem, is formulated as a 0–1 mixed integer programming model. Two branch-and-bound (B&B) algorithms are developed and implemented in this study to solve this problem. Both algorithms use the Driebeek penalties to strengthen the lower bounds so as to fathom some of the subproblems, to peg variables, and to guide the selection of separation variables. One algorithm also strongly exploits the problem structure in selecting separation variables in order to find feasible solutions sooner. To take advantage of the underlying network structure of the problem, the algorithms employ the primal network simplex method to solve network relaxations of the problem. A computational experiment was conducted to test the performance of the algorithms and to characterize the problem difficulty. The commercial mixed integer programming software CPLEX and an existing special purpose algorithm specifically designed for this problem were used as benchmarks to measure the performance of the algorithms. Computational results show that the new algorithms completely dominate the existing special purpose algorithm and run from two to three orders of magnitude faster than CPLEX.     

A deterministic,multi-item inventory model with supplier selection and imperfect quality

This paper considers the scenario of supply chain with multiple products and multiple suppliers, all of which have limited capacity. We assume that received items from suppliers are not of perfect quality. Items of imperfect quality, not necessarily defective, could be used in another inventory situation. Imperfect items are sold as a single batch, prior to receiving the next shipment, at a discounted price. The demand over a finite planning horizon is known, and an optimal procurement strategy for this multi-period horizon is to be determined. Each of products can be sourced from a set of approved suppliers, a supplier-dependent transaction cost applies for each period in which an order is placed on a supplier. A product-dependent holding cost per period applies for each product in the inventory that is carried across a period in the planning horizon. Also a maximum storage space for the buyer in each period is considered. The decision maker, the buyer, needs to decide what products to order, in what quantities, with which suppliers, and in which periods. Finally, a genetic algorithm (GA) is used to solve the model.     

Portfolio selection under downside risk measures and cardinality constraints based on DC programming and DCA

In this paper, we consider the case of downside risk measures with cardinality and bounding constraints in portfolio selection. These constraints limit the amount of capital to be invested in each asset as well as the number of assets composing the portfolio. While the standard Markowitz’s model is a convex quadratic program, this new model is a NP-hard mixed integer quadratic program. Realizing the computational intractability for this class of problems, especially large-scale problems, we first reformulate it as a DC program with the help of exact penalty techniques in Difference of Convex functions (DC) programming and then solve it by DC Algorithms (DCA). To check globality of computed solutions, a global method combining the local algorithm DCA with a Branch-and-Bound algorithm is investigated. Numerical simulations show that DCA is an efficient and promising approach for the considered problem.      

Integer programming, Barvinok's counting algorithm and Gomory relaxations

We propose an algorithm based on Barvinok's counting algorithm for . It runs in time polynomial in the input size of when n is fixed, and under a condition on c, provides the optimal value of . We also relate Barvinok's counting formula and Gomory relaxations.     

Flexible supply policy with options and capacity constraints

This paper considers a class of multi-period flexible supply policies with options and capacity constraints. The main results are to characterize the optimal ordering and purchasing options policy and the minimum expected cost in a period and thereafter under the assumptions about the options and ordering quantities.     

Integer matrices with constraints on leading partial row and column sums

Consider the problem of finding an integer matrix that satisfies given constraints on its leading partial row and column sums. For the case in which the specified constraints are merely bounds on each such sum, an integer linear programming formulation is shown to have a totally unimodular constraint matrix. This proves the polynomial-time solvability of this case. In another version of the problem, one seeks a zero-one matrix with prescribed row and column sums, subject to certain near-equality constraints, namely, that all leading partial row (respectively, column) sums up through a given column (respectively, row) are within unity of each other. This case admits a polynomial reduction to the preceding case, and an equivalent reformulation as a maximum-flow problem. The results are developed in a context that relates these two problems to consistent matrix rounding.     

Modeling methods and a branch and cut algorithm for pharmaceutical clinical trial planning using stochastic programming

We discuss methods for the solution of a multi-stage stochastic programming formulation for the resource-constrained scheduling of clinical trials in the pharmaceutical research and development pipeline. First, we present a number of theoretical properties to reduce the size and improve the tightness of the formulation, focusing primarily on non-anticipativity constraints. Second, we develop a novel branch and cut algorithm where necessary non-anticipativity constraints that are unlikely to be active are removed from the initial formulation and only added if they are violated within the search tree. We improve the performance of our algorithm by combining different node selection strategies and exploring different approaches to constraint violation checking.     

Selection of contract suppliers under price and demand uncertainty in a dynamic market

In this paper, we consider a supply contracting problem in which the buyer firm faces non-stationary stochastic price and demand. First, we derive analytical results to compare two pure strategies: (i) periodically purchasing from the spot market; and (ii) signing a long-term contract with a single supplier. The results from the pure strategies show that the selection of suppliers can be complicated by many parameters, and is particularly affected by price uncertainty. We then develop a stochastic dynamic programming model to incorporate mixed strategies, purchasing commitments and contract cancellations. Computational results show that increases in price (demand) uncertainty favor long-term (short-term) suppliers. By examining the two-way interactions of contract factors (price, demand, purchasing bounds, learning and technology effect, salvage values and contract cancellation), both intuitive and non-intuitive managerial insights in outsourcing strategies are derived.     

Survivable network design under optimal and heuristic interdiction scenarios

We examine the problem of building or fortifying a network to defend against enemy attacks in various scenarios. In particular, we examine the case in which an enemy can destroy any portion of any arc that a designer constructs on the network, subject to some interdiction budget. This problem takes the form of a three-level, two-player game, in which the designer acts first to construct a network and transmit an initial set of flows through the network. The enemy acts next to destroy a set of constructed arcs in the designer’s network, and the designer acts last to transmit a final set of flows in the network. Most studies of this nature assume that the enemy will act optimally; however, in real-world scenarios one cannot necessarily assume rationality on the part of the enemy. Hence, we prescribe optimal network design algorithms for three different profiles of enemy action: an enemy destroying arcs based on capacities, based on initial flows, or acting optimally to minimize our maximum profits obtained from transmitting flows.