Optimization with additional variables and constraints

Norton, Plotkin and Tardos proved that—loosely spoken, an LP problem is solvable in time O(Tq^k+1) if deleting k fixed columns or rows, we obtain a problem which can be solved by an algorithm that makes at most T steps and q comparisons. This paper improves this running time to O(Tq^k).     

The single item uncapacitated lot-sizing problem with time-dependent batch sizes: NP-hard and polynomial cases

This paper considers the uncapacitated lot sizing problem with batch delivery, focusing on the general case of time-dependent batch sizes. We study the complexity of the problem, depending on the other cost parameters, namely the setup cost, the fixed cost per batch, the unit procurement cost and the unit holding cost. We establish that if any one of the cost parameters is allowed to be time-dependent, the problem is NP-hard. On the contrary, if all the cost parameters are stationary, and assuming no unit holding cost, we show that the problem is polynomially solvable in time O(T³), where T denotes the number of periods of the horizon. We also show that, in the case of divisible batch sizes, the problem with time varying setup costs, a stationary fixed cost per batch and no unit procurement nor holding cost can be solved in time O(T³ logT).     

On the commuting extensions of subnormal operators

We give some results concerning the following problem: Given a linear bounded operatorA which is subnormal on a Hilbert spaceH, andB its minimal normal extension on a Hilbert spaceK ～H, when can a quasi-normal operatorT commuting withA be extended to an operatorT ^e onK such thatT ^e commutes withB andT ^e is quasi-normal onK?     

An efficient approach for solving the lot-sizing problem with time-varying storage capacities

We address the dynamic lot size problem assuming time-varying storage capacities. The planning horizon is divided into T periods and stockouts are not allowed. Moreover, for each period, we consider a setup cost, a holding unit cost and a production/ordering unit cost, which can vary through the planning horizon. Although this model can be solved using O(T³) algorithms already introduced in the specialized literature, we show that under this cost structure an optimal solution can be obtained in O(T log T) time. In addition, we show that when production/ordering unit costs are assumed to be constant (i.e., the Wagner–Whitin case), there exists an optimal plan satisfying the Zero Inventory Ordering (ZIO) property.     

A single-machine scheduling problem with maintenance activities to minimize makespan

We study a single-machine scheduling problem with periodic maintenance activity under two maintenance stratagems. Although the scheduling problem with single or periodic maintenance and nonresumable jobs has been well studied, most of past studies considered only one maintenance stratagem. This research deals with a single-machine scheduling problem where the machine should be stopped for maintenance after a fixed periodic interval (T) or after a fixed number of jobs (K) have been processed. The objective is to minimize the makespan for the addressed problem. A two-stage binary integer programming (BIP) model is provided for driving the optimal solution up to 350-job instances. For the large-sized problems, two efficient heuristics are provided for the different combinations of T and K. Computational results show that the proposed algorithm Best-Fit-Butterfly (BBF) performs well because the total average percentage error is below 1%. Once the constraint of the maximum number of jobs (K) processed in the machine’s available time interval (T) is equal or larger than half of jobs, the heuristic Best-Fit-Decreasing (DBF) is strongly recommended.     

Finding the K best policies in a finite-horizon Markov decision process

Directed hypergraphs represent a general modelling and algorithmic tool, which have been successfully used in many different research areas such as artificial intelligence, database systems, fuzzy systems, propositional logic and transportation networks. However, modelling Markov decision processes using directed hypergraphs has not yet been considered.In this paper we consider finite-horizon Markov decision processes (MDPs) with finite state and action space and present an algorithm for finding the K best deterministic Markov policies. That is, we are interested in ranking the first K deterministic Markov policies in non-decreasing order using an additive criterion of optimality. The algorithm uses a directed hypergraph to model the finite-horizon MDP. It is shown that the problem of finding the optimal policy can be formulated as a minimum weight hyperpath problem and be solved in linear time, with respect to the input data representing the MDP, using different additive optimality criteria.     

LELONG-DEMAILLY NUMBERS IN TERMS OF CAPACITY AND WEAK CONVERGENCE FOR CLOSED POSITIVE CURRENTS

In this paper we give a new definition of the Lelong-Demailly number in terms of the CT-capacity, where T is a closed positive current and CT is the capacity associated to T. This derived from some esimate on the growth of the CT-capacity of the sublevel sets of a weighted plurisubharmonic （psh for short） function. These estimates enable us to give another proof of the Demailly＇s comparaison theorem as well as a generalization of some results due to Xing concerning the characterization of bounded psh functions. Another problem that we consider here is related to the existence of a psh function v that satisfies the equality CT（K） ： fK T ∧ （dd^cu）^p, where K is a compact subset. Finally, we give some conditions on the capacity CT that guarantees the weak convergence ukTk → uT, for positive closed currents T, Tk and psh functions uk, u.     

A note on single-machine scheduling with job-dependent learning effects

Mosheiov and Sidney (2003) showed that the makespan minimization problem with job-dependent learning effects can be formulated as an assignment problem and solved in O(n³) time. We show that this problem can be solved in O(nlog n) time by sequencing the jobs according to the shortest processing time (SPT) order if we utilize the observation that the job-dependent learning rates are correlated with the level of sophistication of the jobs and assume that these rates are bounded from below. The optimality of the SPT sequence is also preserved when the job-dependent learning rates are inversely correlated with the level of sophistication of the jobs and bounded from above.     

An effective heuristic for the review period in an inventory model with staggered deliveries and normal demands

Consider a single-item, periodic review, infinite-horizon, undiscounted, inventory model with stochastic demands, proportional holding and shortage costs, and full backlogging. Orders can arrive in every period, and the cost of receiving them is negligible (as in JIT). Every T periods, one audits the stocks and chooses a delivery schedule for each of the next T periods, thus incurring a fixed audit cost and—when one schedules actual deliveries—a fixed order cost. The problem is to find a review period T and an ordering policy minimizing the average cost. An earlier article developed an algorithm for computing an optimal T, and undertook a numerical study to evaluate various approximations. Assuming normal demands, we characterize the asymptotic behavior (for large μ/σ) of the optimal T and establish the asymptotic optimality of a heuristic, calculable on a spreadsheet. A numerical study indicates that patterns established here for large μ/σ hold for σ/μ above 2.     

Random number of units for K-out-of-n systems

This paper takes up the reliability and preventive replacement problems for a K-out-of-n system, where K is a stochastic parameter provided. Firstly, we consider the case when K is predefined as constant numbers as is done with the traditional method, and obtain the system reliability R(t), mean time to failure (MTTF), and replacement policies, in which the number n of units for replacement and replacement time T of operation are, respectively, optimized. Secondly, we focus on the above discussions again when K cannot be predefined constantly, but it is a random variable with an estimated probability function. Furthermore, we give approximate computations in an easier way for MTTF, optimal number n* and replacement time T*, respectively.     

Capacitated dynamic lot-sizing problem with delivery/production time windows

In this paper we generalize the classical dynamic lot-sizing problem by considering production capacity constraints as well as delivery and/or production time windows. Utilizing an untraditional decomposition principle, we develop a polynomial-time algorithm for computing an optimal solution for the problem under the assumption of non-speculative costs. The proposed solution methodology is based on a dynamic programming algorithm that runs in O(nT⁴) time, where n is the number of demands and T is the length of the planning horizon.     

SVEP and compact perturbations

Let H be a complex separable infinite dimensional Hilbert space. In this paper, we prove that an operator T acting on H is a norm limit of those operators with single-valued extension property (SVEP for short) if and only if T^?, the adjoint of T, is quasitriangular. Moreover, if T^? is quasitriangular, then, given an ε>0, there exists a compact operator K on H with ‖K‖<ε such that T+K has SVEP. Also, we investigate the stability of SVEP under (small) compact perturbations. We characterize those operators for which SVEP is stable under (small) compact perturbations.     

Dynamic lot-sizing model with demand time windows and speculative cost structure

We consider a deterministic lot-sizing problem with demand time windows, where speculative motive is allowed. Utilizing an untraditional decomposition principle, we provide an optimal algorithm that runs in O(nT³) time, where n is the number of demands and T is the length of the planning horizon.     

Stability in the Rotating Bénard Problem and Its Optimal Lyapunov Functions

Stability analysis of the rotating Bénard problem gives a spectral instability threshold of the purely conducting solution that can be expressed as a critical Rayleigh number R ² depending on the Taylor number T ². The definition of a functional which can be used to prove Lyapunov stability up to the threshold of spectral instability (optimal Lyapunov function) is an important step forward both, for a proof of nonlinear stability and for the investigation of the basin of attraction of the equilibrium. In previous works a Lyapunov function was found, but its optimality could be proven only for small T ². In this work we describe the reason why this happens, and provide a weaker definition of Lyapunov function which allows to prove that, for the linearized system, the spectral instability threshold is also the Lyapunov stability threshold for every value of T ².     

An optimal replacement policy for a multistate degenerative simple system

In this paper, a degenerative simple system (i.e. a degenerative one-component system with one repairman) with k + 1 states, including k failure states and one working state, is studied. Assume that the system after repair is not “as good as new”, and the degeneration of the system is stochastic. Under these assumptions, we consider a new replacement policy T based on the system age. Our problem is to determine an optimal replacement policy T^∗ such that the average cost rate (i.e. the long-run average cost per unit time) of the system is minimized. The explicit expression of the average cost rate is derived, the corresponding optimal replacement policy can be determined, the explicit expression of the minimum of the average cost rate can be found and under some mild conditions the existence and uniqueness of the optimal policy T^∗ can be proved, too. Further, we can show that the repair model for the multistate system in this paper forms a general monotone process repair model which includes the geometric process repair model as a special case. We can also show that the repair model in the paper is equivalent to a geometric process repair model for a two-state degenerative simple system in the sense that they have the same average cost rate and the same optimal policy. Finally, a numerical example is given to illustrate the theoretical results of this model.     

Traces on the skein algebra of the torus

For a surface F, the Kauffman bracket skein module of F×[0,1], denoted K(F), admits a natural multiplication which makes it an algebra. When specialized at a complex number t, nonzero and not a root of unity, we have Kt(F), a vector space over C. In this paper, we will use the product-to-sum formula of Frohman and Gelca to show that the vector space Kt(T²) has five distinct traces. One trace, the Yang-Mills measure, is obtained by picking off the coefficient of the empty skein. The other four traces on Kt(T²) correspond to the four singular points of the moduli space of flat SU(2)-connections on the torus.     

Properties of random walks on discrete groups: Time regularity and off-diagonal estimates

In this paper we study some properties of the convolution powers K(n)=K∗K∗?∗K of a probability density K on a discrete group G, where K is not assumed to be symmetric. If K is centered, we show that the Markov operator T associated with K is analytic in Lp(G) for 1<p<∞, and prove Davies-Gaffney estimates in L² for the iterated operators Tn. This enables us to obtain Gaussian upper bounds for the convolution powers K(n). In case the group G is amenable, we discover that the analyticity and Davies-Gaffney estimates hold if and only if K is centered. We also estimate time and space differences, and use these to obtain a new proof of the Gaussian estimates with precise time decay in case G has polynomial volume growth.     

On spherically convex sets and Q-matrices

Let K be a closed spherically convex subset of S^n?1 that is contained in a hemisphere, and x?(K) the radial projection onto S^n?1 of the centroid of K. Then p^Tx?(K)>0 for all p ? K. A specialization of this result to spherical simplices is used to derive a necessary condition for Q-matrices, i.e., matrices for which every corresponding linear complementarity problem has at least one solution.     

On semicomplete multipartite digraphs whose king sets are semicomplete digraphs

Reid [Every vertex a king, Discrete Math. 38 (1982) 93-98] showed that a non-trivial tournament H is contained in a tournament whose 2-kings are exactly the vertices of H if and only if H contains no transmitter. Let T be a semicomplete multipartite digraph with no transmitters and let K_r(T) denote the set of r-kings of T. Let Q be the subdigraph of T induced by K₄(T). Very recently, Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249-258] proved that Q contains no transmitters and gave an example to show that the direct extension of Reid's result to semicomplete multipartite digraphs with 2-kings replaced by 4-kings is not true. In this paper, we (1) characterize all semicomplete digraphs D which are contained in a semicomplete multipartite digraph whose 4-kings are exactly the vertices of D. While it is trivial that K₄(Q)⊆K₄(T), Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249-258] showed that K₃(Q)⊆K₃(T) and K₂(Q)=K₂(T). Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249-258] also provided an example to show that K₃(Q) need not be the same as K₃(T) in general and posed the problem: characterize all those semicomplete multipartite digraphs T such that K₃(Q)=K₃(T). In the course of proving our result (1), we (2) show that K₃(Q)=K₃(T) for all semicomplete multipartite digraphs T with no transmitters such that Q is a semicomplete digraph.