A note on an optimal choice problem

An item has probabilityp ₀ of not being workable. Before, going into use it has to be controlled by some deliberately chosen checksC _i which costsc _i 0,1in. Total checking costs must be not larger thanc ₀>0. It may happen that a check breaks a workable item, and failures may be overlooked. The problem is to determine an optimal sequence of checks subject to the cost constraints, such that the probability is maximized that an item leaving the checks is workable. In [1] this problem is solved by W. Stadje, but numerically the solution method only is applicable to problems of modest size.In this paper a simple reformulation of the original problem is presented. This first allows a simpler derivation of some of the results in [1]. Further, a dynamic programming algorithm is presented, which is pseudopolynomial, if costsc _i are integers. It then requiresO(n·c ₀) time.     

Evolutionary,constructive and hybrid procedures for the bi-objective set packing problem

The bi-objective set packing problem is a multi-objective combinatorial optimization problem similar to the well-known set covering/partitioning problems. To our knowledge and surprise, this problem has not yet been studied whereas several applications have been reported. Unfortunately, solving the problem exactly in a reasonable time using a generic solver is only possible for small instances. We designed three alternative procedures for approximating solutions to this problem. The first is derived from the original ‘Strength Pareto Evolutionary Algorithm’, which is a population-based metaheuristic. The second is an adaptation of the ‘Greedy Randomized Adaptative Search Procedure’, which is a constructive metaheuristic. As underlined in the overview of the literature summarized here, almost all the recent, effective procedures designed for approximating optimal solutions to multi-objective combinatorial optimization problems are based on a blend of techniques, called hybrid metaheuristics. Thus, the third alternative, which is the primary subject of this paper, is an original hybridization of the previous two metaheuristics. The algorithmic aspects, which differ from the original definition of these metaheuristics, are described, so that our results can be reproduced. The performance of our procedures is reported and the computational results for 120 numerical instances are discussed.     

On the general inverse problem of optimal control theory

The general inverse problem of optimal control is considered from a dynamic programming point of view. Necessary and sufficient conditions are developed which two integral criteria must satisfy if they are to yield the same optimal feedback law, the dynamics being fixed. Specializing to the linear-quadratic case, it is shown how the general results given here recapture previously obtained results for quadratic criteria with linear dynamics.Dedicated to R. Bellman     

An adaptive O(log n)‐optimal policy for the online selection of a monotone subsequence from a random sample

Given a sequence of n independent random variables with common continuous distribution, we propose a simple adaptive online policy that selects a monotone increasing subsequence. We show that the expected number of monotone increasing selections made by such a policy is within of optimal. Our construction provides a direct and natural way for proving the ‐optimality gap. An earlier proof of the same result made crucial use of a key inequality of Bruss and Delbaen [5] and of de‐Poissonization.     

An optimal sequential procedure for a multiple selling problem with independent observations

We consider a sequential problem of selling K identical assets over the finite time horizon with a fixed number of offers per time period and no recall of past offers. The objective is to find an optimal sequential procedure which maximizes the total expected revenue. In this paper, we derive an effective number of stoppings for an optimal sequential procedure for the selling problem with independent observations.     

The problem of optimal stopping in a partially observable Markov chain

The optimal-stopping problem in a partially observable Markov chain is considered, and this is formulated as a Markov decision process. We treat a multiple stopping problem in this paper. Unlike the classical stopping problem, the current state of the chain is not known directly. Information about the current state is always available from an information process. Several properties about the value and the optimal policy are given. For example, if we add another stop action to thek-stop problem, the increment of the value is decreasing ink.The author wishes to thank Professor M. Sakaguchi of Osaka University for his encouragement and guidance. He also thanks the referees for their careful readings and helpful comments.     

Penalty computations for the set partitioning problem

The computation of penalties associated with the continuous relaxation of integer programming problems can be useful to derive conditional and relational tests which allow to fix some variables at their optimal value or to generate new constraints (cuts). We study in this paper the computation and the use of penalties as a tool to improve the efficiency of algorithms for solving set partitioning problems. This leads to a preprocessing scheme which can be embedded within any exact or approximate algorithm. The strength of these penalties is illustrated through computational results on some real-world set partitioning problems.This work was sponsored by FINEP (research contract number 4.3.86.0689-00), CNPq (research contract numbers 11.1592-84, 30.2281-85 and 40.2002-86.5), IBM Brazil and NSERC (grant # GP0036426).On leave from the Catholic University of Rio de Janeiro, Department of Electrical Engineering, Caixa Postal 38063, Gávea, Rio de Janeiro 22452, Brazil.     

An optimal control problem for the multidimensional diffusion equation with a generalized control variable

The present paper is concerned with an optimal control problem for then-dimensional diffusion equation with a sequence of Radon measures as generalized control variables. Suppose that a desired final state is not reachable. We enlarge the set of admissible controls and provide a solution to the corresponding moment problem for the diffusion equation, so that the previously chosen desired final state is actually reachable by the action of a generalized control. Then, we minimize an objective function in this extended space, which can be characterized as consisting of infinite sequences of Radon measures which satisfy some constraints. Then, we approximate the action of the optimal sequence by that of a control, and finally develop numerical methods to estimate these nearly optimal controls. Several numerical examples are presented to illustrate these ideas.     

Approximating the Pareto optimal set using a reduced set of objective functions

Real-world applications of multi-objective optimization often involve numerous objective functions. But while such problems are in general computationally intractable, it is seldom necessary to determine the Pareto optimal set exactly. A significantly smaller computational burden thus motivates the loss of precision if the size of the loss can be estimated. We describe a method for finding an optimal reduction of the set of objectives yielding a smaller problem whose Pareto optimal set w.r.t. a discrete subset of the decision space is as close as possible to that of the original set of objectives. Utilizing a new characterization of Pareto optimality and presuming a finite decision space, we derive a program whose solution represents an optimal reduction. We also propose an approximate, computationally less demanding formulation which utilizes correlations between the objectives and separates into two parts. Numerical results from an industrial instance concerning the configuration of heavy-duty trucks are also reported, demonstrating the usefulness of the method developed. The results show that multi-objective optimization problems can be significantly simplified with an induced error which can be measured.     

Portfolio choice and optimal hedging with general risk functions: A simplex-like algorithm

The minimization of general risk functions is becoming more and more important in portfolio choice theory and optimal hedging. There are two major reasons. Firstly, heavy tails and the lack of symmetry in the returns of many assets provokes that the classical optimization of the standard deviation may lead to dominated strategies, from the point of view of the second order stochastic dominance. Secondly, but not less important, many institutional investors must respect legal capital requirements, which may be more easily studied if one deals with a risk measure related to capital losses.     

An inverse optimal problem in discrete-time stochastic control

In this paper, we study an inverse optimal problem in discrete-time stochastic control. We give necessary and sufficient conditions for a solution to a system of stochastic difference equations to be the solution of a certain optimal control problem. Our results extend to the stochastic case the work of Dechert. In particular, we present a stochastic version of an important principle in welfare economics.     

A note on a symmetrical set covering problem: The lottery problem

In a lottery, n numbers are drawn from a set of m numbers. On a lottery ticket we fill out n numbers. Consider the following problem: what is the minimum number of tickets so that there is at least one ticket with at least p matching numbers? We provide a set-covering formulation for this problem and characterize its LP solution. The existence of many symmetrical alternative solutions, makes this a very difficult problem to solve, as our computational results indicate.     

A level set approach for the solution of a state-constrained optimal control problem

Summary. State constrained optimal control problems for linear elliptic partial differential equations are considered. The corresponding first order optimality conditions in primal-dual form are analyzed and linked to a free boundary problem resulting in a novel algorithmic approach with the boundary (interface) between the active and inactive sets as optimization variable. The new algorithm is based on the level set methodology. The speed function involved in the level set equation for propagating the interface is computed by utilizing techniques from shape optimization. Encouraging numerical results attained by the new algorithm are reported on.Mathematics Subject Classification (1991): 35R35, 49K20, 49Q10, 65K10Revised version received March 19, 2003     

MIP reformulations of the probabilistic set covering problem

In this paper, we address the following probabilistic version (PSC) of the set covering problem: where A is a 0-1 matrix, is a random 0-1 vector and is the threshold probability level. We introduce the concepts of p-inefficiency and polarity cuts. While the former is aimed at deriving an equivalent MIP reformulation of (PSC), the latter is used as a strengthening device to obtain a stronger formulation. Simplifications of the MIP model which result when one of the following conditions hold are briefly discussed: A is a balanced matrix, A has the circular ones property, the components of are pairwise independent, the distribution function of is a stationary distribution or has the disjunctive shattering property. We corroborate our theoretical findings by an extensive computational experiment on a test-bed consisting of almost 10,000 probabilistic instances. This test-bed was created using deterministic instances from the literature and consists of probabilistic variants of the set covering model and capacitated versions of facility location, warehouse location and k-median models. Our computational results show that our procedure is orders of magnitude faster than any of the existing approaches to solve (PSC), and in many cases can reduce hours of computing time to a fraction of a second. Anureet Saxena’s research was supported by the National Science Foundation through grant #DMI-0352885 and by the Office of Naval Research through contract N00014-03-1-0133. Vineet Goyal’s research was supported in part by NSF grant CCF-0430751 and ITR grant CCR-0122581.     

An approximate dynamic programming approach for the vehicle routing problem with stochastic demands

This paper examines approximate dynamic programming algorithms for the single-vehicle routing problem with stochastic demands from a dynamic or reoptimization perspective. The methods extend the rollout algorithm by implementing different base sequences (i.e. a priori solutions), look-ahead policies, and pruning schemes. The paper also considers computing the cost-to-go with Monte Carlo simulation in addition to direct approaches. The best new method found is a two-step lookahead rollout started with a stochastic base sequence. The routing cost is about 4.8% less than the one-step rollout algorithm started with a deterministic sequence. Results also show that Monte Carlo cost-to-go estimation reduces computation time 65% in large instances with little or no loss in solution quality. Moreover, the paper compares results to the perfect information case from solving exact a posteriori solutions for sampled vehicle routing problems. The confidence interval for the overall mean difference is (3.56%, 4.11%).     

Successive search methods for solving a canonical DC programming problem

In this article, we propose two successive search methods for solving a canonical DC programming problem constrained by the difference set between two compact convex sets in the case where the dimension number is greater than or equal to three. In order to find feasible solutions, the algorithms generate the directions based on a branch and bound procedure, successively. By exploring the provisional solutions throughout the intersection of the boundaries of two compact convex sets, both algorithms calculate an approximate solution.     

Second-order optimality conditions in a discrete optimal control problem

Discrete optimal control problems with variable endpoints and with inequality type constraints on control are considered. We derive first- and second-order necessary optimality conditions that are meaningful without a priori normality assumptions.     

Algorithm for cardinality-constrained quadratic optimization

This paper describes an algorithm for cardinality-constrained quadratic optimization problems, which are convex quadratic programming problems with a limit on the number of non-zeros in the optimal solution. In particular, we consider problems of subset selection in regression and portfolio selection in asset management and propose branch-and-bound based algorithms that take advantage of the special structure of these problems. We compare our tailored methods against CPLEX’s quadratic mixed-integer solver and conclude that the proposed algorithms have practical advantages for the special class of problems we consider. The research of D. Bertsimas was partially supported by the Singapore-MIT alliance. The research of R. Shioda was partially supported by the Singapore-MIT alliance, the Discovery Grant from NSERC and a research grant from the Faculty of Mathematics, University of Waterloo.