Optimal project selection: Stochastic knapsack with finite time horizon

A time-constrained capital-budgeting problem arises when projects, which can contribute to achieving a desired target state before a specified deadline, arrive sequentially. We model such problems by treating projects as randomly arriving requests, each with a funding cost, a proposed benefit, and a known probability of success. The problem is to allocate a non-renewable initial budget to projects over time so as to maximise the expected benefit obtained by a certain time, T, called the deadline, where T can be either a constant or a random variable. Each project must be accepted or rejected as soon as it arrives. We developed a stochastic dynamic programming formulation and solution of this problem, showing that the optimal strategy is to dynamically determine ‘acceptance intervals’ such that a project of type i is accepted when, and only when, it arrives during an acceptance interval for projects of type i.     

Approximating min-cost chain-constrained spanning trees: a reduction from weighted to unweighted problems

We study the min-cost chain-constrained spanning-tree (MCCST) problem: find a min-cost spanning tree in a graph subject to degree constraints on a nested family of node sets. We devise the first polytime algorithm that finds a spanning tree that (i) violates the degree constraints by at most a constant factor and (ii) whose cost is within a constant factor of the optimum. Previously, only an algorithm for unweighted CCST was known (Olver and Zenklusen in Proceedings of the 16th IPCO, pp 324–335, 2013), which satisfied (i) but did not yield any cost bounds. This also yields the first result that obtains an O(1)-factor for both the cost approximation and violation of degree constraints for any spanning-tree problem with general degree bounds on node sets, where an edge participates in a super-constant number of degree constraints. A notable feature of our algorithm is that we reduce MCCST to unweighted CCST (and then utilize Olver and Zenklusen in Proceedings of the 16th IPCO, pp 324–335, 2013) via a novel application of Lagrangian duality to simplify the cost structure of the underlying problem and obtain a decomposition into certain uniform-cost subproblems. We show that this Lagrangian-relaxation based idea is in fact applicable more generally and, for any cost-minimization problem with packing side-constraints, yields a reduction from the weighted to the unweighted problem. We believe that this reduction is of independent interest. As another application of our technique, we consider the k -budgeted matroid basis problem, where we build upon a recent rounding algorithm of Bansal and Nagarajan (Proceedings of IPCO 2016. arXiv:1512.02254, 2015) to obtain an improved \(n^{O(k^{1.5}/\epsilon )}\)-time algorithm that returns a solution that satisfies (any) one of the budget constraints exactly and incurs a \((1+\epsilon )\)-violation of the other budget constraints.     

Deterministic hierarchical substitution inventory models

In this paper, we consider a deterministic nested substitution problem where there are multiple products which can be substituted one for the other, if necessary, at a certain cost. We consider the case when there are n products, and product j can substitute products j + 1,…,n at certain costs. The trade-off is the cost of storing products (for example, customised products) at a higher inventory holding stage versus the cost of transferring downwards from a lower inventory holding cost (generic product) stage. The standard approach to solving the problem yields an intractable formulation, but by reformulating the problem to determine the optimal run-out times, we are able to determine the optimal order and substitution quantities. Numerical examples showing the effect of various system parameters on the optimal order and substitution policy are also presented.     

An Improved Formulation for the Job-Shop Scheduling Problem

This paper presents an extension of an earlier integer programming model developed by other authors to formulate a general n-job, m-machine job-shop problem. The new formulation involves substantially fewer functional constraints at the expense of an increase in the number of upper bound variables. This reduction of functional constraints, together with the imposition of upper and lower bounds on the objective value, significantly reduces the computation time for solving the integer model for the job-shop scheduling problem.     

Project cost dynamics for development policy-making

Cost and time overruns have been a common characteristic of development projects in many countries. This paper presents a theory of cost and time overruns based on project cost structure. The cost of a development project consists of base cost and progress cost. Base cost keeps a project ready for physical progress. Progress cost creates real physical progress on the project. This cost structure has an important inherent dynamic characteristic with implications for the efficiency and effectiveness of project management. An imbalance between annual budget and ongoing projects results in an increasing inefficiency and ineffectiveness unrelated to the quality of management of individual projects. The policy governing the starting rate of the new projects becomes very important in improving project performances. The paper also suggests some policy recommendations for commencing new projects.     

Continuous and Discrete Age-Replacement Policies

This paper considers the combined continuous and discrete age-replacement policies when units deteriorate with age and use: a unit is replaced preventively before failure at time T of age or at number N of uses, whichever occurs first. The expected cost rate C (T,N) is derived, and both optimum time T* and number N* to minimize C (T,N) are discussed. There exist finite and unique T* and N* when the use occurs in a Poisson process under suitable conditions.     

Publish or Perish? — A Case Study

This paper describes and discusses a consultancy project which was concerned with identifying a successful future for an ailing journal. The paper emphasises that part of the project which involved problem construction and discusses the use of cognitive mapping as an aid to defining the nature of a policy problem which involves conflicting and qualitative views of the problem.     

Analysis of algorithms for an online version of the convoy movement problem

In the convoy movement problem (CMP), a set of convoys must be routed from specified origins to destinations in a transportation network, represented by an undirected graph. Two convoys may not cross each other on the same edge while travelling in opposing directions, a restriction referred to as blocking. However, convoys are permitted to follow each other on the same edge, with a specified headway separating them, but no overtaking is permitted. Further, the convoys to be routed are distinguished based on their length. Particle convoys have zero length and are permitted to traverse an edge simultaneously, whereas convoys with non-zero length have to follow each other, observing a headway. The objective is to minimize the total time taken by convoys to travel from their origins to their destinations, given the travel constraints on the edges. We consider an online version of the CMP where convoy demands arise dynamically over time. For the special case of particle convoys, we present an algorithm that has a competitive ratio of 3 in the worst case and (5/2) on average. For the particle convoy problem, we also present an alternate, randomized algorithm that provides a competitive ratio of (√13?1). We then extend the results to the case of convoys with length, which leads to an algorithm with an O(T+CL) competitive ratio, where T={Max _e t(e)}/{Min _e t(e)}, C is the maximum congestion (the number of distinct convoy origin–destination pairs that use any edge e) and L={Max _c L(c)}/{Min _c L(c)}; here L(c)>0 represents the time-headway to be observed by any convoy that follows c and t(e) represents the travel time for a convoy c on edge e.     

An FPTAS for minimizing the product of two non-negative linear cost functions

We consider a quadratic programming (QP) problem (Π) of the form min x ^T C x subject to Ax ≥ b, x ≥ 0 where \({C\in {\mathbb R}^{n \times n}_+, {\rm rank}(C)=1}\) and \({A\in {\mathbb R}^{m \times n}, b\in {\mathbb R}^m}\) . We present an fully polynomial time approximation scheme (FPTAS) for this problem by reformulating the QP (Π) as a parameterized LP and “rounding” the optimal solution. Furthermore, our algorithm returns an extreme point solution of the polytope. Therefore, our results apply directly to 0–1 problems for which the convex hull of feasible integer solutions is known such as spanning tree, matchings and sub-modular flows. They also apply to problems for which the convex hull of the dominant of the feasible integer solutions is known such as s, t-shortest paths and s, t-min-cuts. For the above discrete problems, the quadratic program Π models the problem of obtaining an integer solution that minimizes the product of two linear non-negative cost functions.     

The Shape of Orthogonal Cycles in Three Dimensions

Let σ be a directed cycle whose edges have each been assigned a desired direction in 3D (East, West, North, South, Up, or Down) but no length. We say that σ is a shape cycle. We consider the following problem. Does there exist an orthogonal representation Γ of σ in 3D space such that no two edges of Γ intersect except at common endpoints and such that each edge of Γ has the direction specified in σ? If the answer is positive, we say that σ is simple. This problem arises in the context of extending orthogonal graph drawing techniques from 2D to 3D. We give a combinatorial characterization of simple shape cycles that yields linear time recognition and drawing algorithms.     

Finite difference schemes for the singularly perturbed reaction-diffusion equation in the case of spherical symmetry

The boundary value problem for the singularly perturbed reaction-diffusion parabolic equation in a ball in the case of spherical symmetry is considered. The derivatives with respect to the radial variable appearing in the equation are written in divergent form. The third kind boundary condition, which admits the Dirichlet and Neumann conditions, is specified on the boundary of the domain. The Laplace operator in the differential equation involves a perturbation parameter ?², where ? takes arbitrary values in the half-open interval (0, 1]. When ? → 0, the solution of such a problem has a parabolic boundary layer in a neighborhood of the boundary. Using the integro-interpolational method and the condensing grid technique, conservative finite difference schemes on flux grids are constructed that converge ?-uniformly at a rate of O(N ^?2ln² N + N ₀ ^?1 ), where N + 1 and N ₀ + 1 are the numbers of the mesh points in the radial and time variables, respectively.     

The local lifting problem for <Emphasis Type="Italic">D</Emphasis><Subscript>4</Subscript>

For a prime p, a cyclic-by-p group G and a G-extension L|K of complete discrete valuation fields of characteristic p with algebraically closed residue field, the local lifting problem asks whether the extension L|K lifts to characteristic zero. In this paper, we characterize D₄-extensions of fields of characteristic two, determine the ramification breaks of (suitable) D₄- extensions of complete discrete valuation fields of characteristic two, and solve the local lifting problem in the affirmative for every D₄-extension of complete discrete valuation fields of characteristic two with algebraically closed residue field; that is, we show that D₄ is a local Oort group for the prime 2.     

Approximation algorithms for the robust facility leasing problem

In this paper, we consider the robust facility leasing problem (RFLE), which is a variant of the well-known facility leasing problem. In this problem, we are given a facility location set, a client location set of cardinality n, time periods \(\{1, 2, \ldots , T\}\) and a nonnegative integer \(q < n\). At each time period t, a subset of clients \(D_{t}\) arrives. There are K lease types for all facilities. Leasing a facility i of a type k at any time period s incurs a leasing cost \(f_i^{k}\) such that facility i is opened at time period s with a lease length \(l_k\). Each client in \(D_t\) can only be assigned to a facility whose open interval contains t. Assigning a client j to a facility i incurs a serving cost \(c_{ij}\). We want to lease some facilities to serve at least \(n-q\) clients such that the total cost including leasing and serving cost is minimized. Using the standard primal–dual technique, we present a 6-approximation algorithm for the RFLE. We further offer a refined 3-approximation algorithm by modifying the phase of constructing an integer primal feasible solution with a careful recognition on the leasing facilities.     

Solvability of the problem of taking the discrete logarithm

It is proved that consideration of the solvability problem for taking the discrete logarithm in a residue ring modulo composite M can be reduced to consideration of a similar problem in residue rings modulo pq, where p and q are prime divisors of M. For moduli of form pq, necessary and sufficient conditions for solvability checking are obtained in some cases. In addition, the problem of raising a solution of an exponential comparison in a residue ring modulo p ^α is solved.     

Cost Analysis of the <Emphasis Type="Italic">M/M/R</Emphasis> Machine Repair Problem with Spares and Two Modes of Failure

In this paper we deal with the machine repair problem consisting of M operating machines with S spare machines, and R repairmen where machines have two failure modes under steady-state conditions. Spares are considered to be either cold-standby, warm-standby or hot-standby. The two failure modes have equal probability of repair. Failure time of the machines and repair time of the repairmen are assumed to follow a negative exponential distribution. A cost model is developed in order to determine the optimal values of the number of repairmen and the number of spares simultaneously, while maintaining a minimum specified level of system availability. Numerical results are presented in which several system characteristics are evaluated for three types of standby under optimal operating conditions.     

Univariate Stochastic Programming with Random Decision Variable

The problem of minimising E(X) subject to the constraints X ? 0, P(X ? b) ? a(0 < a < 1) has been considered, where b is a non-negative random variable with continuous probability distribution. A necessary and sufficient condition for randomised decisions to be superior to the non-randomised one has been derived.     

Alternative Formulations of a Flow-shop Scheduling Problem

This paper presents an alternative approach to an earlier model developed by other authors to formulate a problem of sequencing N jobs on M machines in a standard flow-shop. The objectives of the model are to minimize makespan and flow-time. The new formulation involves substantially fewer variables, at the expense of a rise in the number of constraints. Practical limitations of both approaches are discussed.     

Stability and convergence of a fully discrete local discontinuous Galerkin method for multi-term time fractional diffusion equations

In this paper, a fully discrete local discontinuous Galerkin method for a class of multi-term time fractional diffusion equations is proposed and analyzed. Using local discontinuous Galerkin method in spatial direction and classical L1 approximation in temporal direction, a fully discrete scheme is established. By choosing the numerical flux carefully, we prove that the method is unconditionally stable and convergent with order O(h ^k+1 + (Δt)^2?α ), where k, h, and Δt are the degree of piecewise polynomial, the space, and time step sizes, respectively. Numerical examples are carried out to illustrate the effectiveness of the numerical scheme.     

Mixed problem for the wave equation with integrable potential in the case of two-point boundary conditions of distinct orders

We study a mixed problem for the wave equation with integrable potential and with two-point boundary conditions of distinct orders for the case in which the corresponding spectral problem may have multiple spectrum. Based on the resolvent approach in the Fourier method and the Krylov convergence acceleration trick for Fourier series, we obtain a classical solution u(x, t) of this problem under minimal constraints on the initial condition u(x, 0) = ?(x). We use the Carleson–Hunt theorem to prove the convergence almost everywhere of the formal solution series in the limit case of ?(x) ∈ L _p[0, 1], p > 1, and show that the formal solution is a generalized solution of the problem.