Operations Research Letters

We propose a sample average approximation (SAA) method for stochastic programming problems with expected value constraints. Such problems arise, for example, in portfolio selection with constraints on conditional value-at-risk (CVaR). We provide a ...

We study a collaborative multicommodity flow game where individual players own capacity on the edges of the network and share this capacity to deliver commodities. We present membership mechanisms, by adopting a rationality based approach using notions ...

We answer an open question by Herings et al. [J.J. Herings, G. van der Laan, D. Talman, Z. Yang, A fixed point theorem for discontinuous functions, Operations Research Letters 36 (1) (2008) 89-93], by proving that their fixed point theorem for ...

The Unichain classification problem detects whether a finite state and action MDP is unichain under all deterministic policies. This problem is NP-hard. This paper provides polynomial algorithms for this problem when there is a state that is either ...

Negative dynamic programming for risk-sensitive control is studied. Under some compactness and semicontinuity assumptions the following results are proved: the convergence of the value iteration algorithm to the optimal expected total reward, the Borel ...

We use kernel density with correction of boundary effects to study the strong stability of the M/M/1 system after perturbation of arrival flow (respectively service times), to evaluate the proximity of G/M/1 (respectively M/G/1) and M/M/1 systems when ...

We consider supplier diversification in an EOQ type inventory setting with multiple suppliers and binomial yields. We characterize the optimal policy for the model and show that, in this case, it does not pay to diversify, in contrast to previous ...

We consider a two-level vendor-managed system in which external demand occurs only at a retailer and a supplier replenishes the retailer employing an order-up-to S policy over T periods. We present an O(T^3) algorithm to coordinate the system when S is ...

We present a new proof of the optimality of echelon order-up-to policies in serial inventory systems, first proved by Clark and Scarf. Our proof is based on a sample-path analysis as opposed to the original proof based on dynamic programming induction.

We consider a stochastic serial inventory system with a given fixed batch size per stage and linear inventory holding and penalty costs. For this system, echelon stock (R,nQ) policies are known to be optimal. On the basis of new average costs formulas, ...

For different reliability importance measures we prove that the criticality relation between nodes can completely determine the most important component in a system. In particular, we prove that in k-out-of-n systems, the ranking of component ...

This work considers a combined maintenance strategy in which the repair of the system failures is performed only in an interval of time of the working period. The objective of this paper is to find the optimal interval in which the repairs can be ...

The variable lifetime of assets is analyzed in a serial replacement problem. Technological change impacts the maintenance cost and new asset cost. The optimal asset lifetime appears to be constant only when both costs decrease with the same rate. We ...

If the cost of borrowing is not too high, the capital-constrained newsvendor borrows funds to procure an amount that is less than would be ideal. The lender charges an interest rate that decreases in the newsvendor's equity. Furthermore, we derived a ...

We consider the High-Multiplicity Cyclic Job Shop Scheduling Problem. There are two objectives of interest: the cycle time and the flow time. We give several approximation algorithms after showing that a very restricted case is APX-hard.

We consider the problem of on-line scheduling with non-crossing constraints. The objective is to minimize the latest completion time. We provide optimal competitive ratio heuristics for the on-line list and on-line time problems with unit processing ...

We consider the problem of on-line scheduling a set of n jobs on two parallel batch processing machines. The objective is to minimize the makespan. We provide an algorithm for the problem that is better than one given in the literature, improving the ...

We analyze steady-state characteristics of batch production time for a constant-demand lot sizing problem with learning and forgetting in production time. We report a new type of convergence, the alternating convergence, in which the batch production ...

The following minimization problem is shown to be NP-hard: Given a graphic degree sequence, find a realization of this degree sequence as loopless multigraph that minimizes the number of edges in the underlying support graph. The corresponding ...

We provide bounds on the performance of back-to-front airplane boarding policies. In particular, we show that no back-to-front policy can be more than 20% better than the policy which boards passengers randomly.

We present a simple 3-approximation algorithm for the feedback vertex set problem in a bipartite tournament, improving on the approximation ratio of 3.5 achieved by the best previous algorithms.

The Wireless Gathering Problem is to find an interference-free schedule for data gathering in a wireless network in minimum time. We present a 4-approximate polynomial-time on-line algorithm for this NP-hard problem. We show that no shortest path ...

We consider the problem of pricing (digital) items in order to maximize the revenue obtainable from a set of bidders. We suggest a natural monotonicity constraint on bundle prices, show that the problem remains NP-hard, and we derive a PTAS. We also ...

Barahona and Mahjoub found a defining system of the stable set polytope for a graph with a cut-set of cardinality 2. We extend this result to cut-sets composed of a complete graph minus an edge and use the new theorem to derive a class of facets.

We study discrete optimization problems with a submodular mean-risk minimization objective. For 0-1 problems a linear characterization of the convex lower envelope is given. For mixed 0-1 problems we derive an exponential class of conic quadratic valid ...

We show that using max-algebraic techniques it is possible to generate the set of all solutions to a system of inequalities x"i-x"j>=b"i"j, i,j=1,...,n using n generators. This efficient description enables us to develop a pseudopolynomial algorithm ...

In this paper, the chance-constrained knapsack problem (CKP) is addressed. Relying on robust optimization, a tractable combinatorial algorithm is proposed to solve approximately CKP. For two specific classes of uncertain knapsack problems, it is proved ...

In this paper, the expression for the cost of capital is derived when capacity expansion investments and replacement investments exhibit differences in their effective prices. It is shown that the cost of capital derived by perturbing the optimal stock ...

We consider the projected subgradient method for solving generalized mixed variational inequalities. In each step, we choose an @e"k-subgradient u^k of the function f and w^k in a set-valued mapping T, followed by an orthogonal projection onto the ...