Optimal stochastic single-machine-tardiness scheduling by stochastic branch-and-bound

A stochastic branch-and-bound technique for the solution of stochastic single-machine-tardiness problems with job weights is presented. The technique relies on partitioning the solution space and estimating lower and upper bounds by sampling. For the lower bound estimation, two different types of sampling (“within” and “without” the minimization) are combined. Convergence to the optimal solution (with probability one) can be demonstrated. The approach is generalizable to other discrete stochastic optimization problems. In computational experiments with the single-machine-tardiness problem, the technique worked well for problem instances with a relatively small number of jobs; due to the enormous complexity of the problem, only approximate solutions can be expected for a larger number of jobs. Furthermore, a general precedence rule for the single-machine scheduling of jobs with uncertain processing times has been derived, essentially saying that “safe” jobs are to be scheduled before “unsafe” jobs.     

Linear programming for weighted deviation problems using compact basis techniques

Weighted deviation problems are linear programs in which weights (or penalties) are attached to deviations from upper and lower bounds on particular linear expressions. In turn the deviations may be bracketed by secondary bounds. These problems include statistical problems of minimizing weighted sums of absolute deviations, standard and extended “goal programming” problems, problems with upper bounds on absolute values of linear affine functions, problems with arbitrarily bounded variables, and combinations of these.Previous specialized linear programming methods for related problems have been restricted to specialized cases that involve only a single basis configuration, or else, by means of “extended GUB” techniques, accommodate a diverse variety of basis structures at the cost of substantially increased computation. We show that, of the several basis configurations that can arise for this problem, precisely three are essential. Special rules are identified to allow transitions between these three structures, to yield valid compact versions of both the primal and the dual simplex methods. Finally, we show how these results lead to improved efficiency as well as reduced problem size.     

A Bridge Between Bilevel Programs and Nash Games

We study connections between optimistic bilevel programming problems and generalized Nash equilibrium problems. We remark that, with respect to bilevel problems, we consider the general case in which the lower level program is not assumed to have a unique solution. Inspired by the optimal value approach, we propose a Nash game that, transforming the so-called implicit value function constraint into an explicitly defined constraint function, incorporates some taste of hierarchy and turns out to be related to the bilevel programming problem. We provide a complete theoretical analysis of the relationship between the vertical bilevel problem and our “uneven” horizontal model: in particular, we define classes of problems for which solutions of the bilevel program can be computed by finding equilibria of our game. Furthermore, by referring to some applications in economics, we show that our “uneven” horizontal model, in some sense, lies between the vertical bilevel model and a “pure” horizontal game.     

A remark on multiobjective stochastic optimization via strongly convex functions

Many economic and financial applications lead (from the mathematical point of view) to deterministic optimization problems depending on a probability measure. These problems can be static (one stage), dynamic with finite (multistage) or infinite horizon, single objective or multiobjective. We focus on one-stage case in multiobjective setting. Evidently, well known results from the deterministic optimization theory can be employed in the case when the “underlying” probability measure is completely known. The assumption of a complete knowledge of the probability measure is fulfilled very seldom. Consequently, we have mostly to analyze the mathematical models on the data base to obtain a stochastic estimate of the corresponding “theoretical” characteristics. However, the investigation of these estimates has been done mostly in one-objective case. In this paper we focus on the investigation of the relationship between “characteristics” obtained on the base of complete knowledge of the probability measure and estimates obtained on the (above mentioned) data base, mostly in the multiobjective case. Consequently we obtain also the relationship between analysis (based on the data) of the economic process characteristics and “real” economic process. To this end the results of the deterministic multiobjective optimization theory and the results obtained for stochastic one objective problems will be employed.     

Designing a recovery-orientated system of care: A community operational research perspective

Theory suggests health focused Community Operational Research (COR) projects and their participants can benefit from balancing a “glass half empty” concern for deficits, problems and weaknesses with a “glass half full” concern for identifying health assets and bringing them into use. We present a COR systemic intervention in the care of persons with addiction and substance use/ misuse problems in Clydeplace, Scotland (anonymised). Our research reveals how the Whole Person Recovery System is situated within a wider General Community Recovery System that offers a variety of health assets that can be mobilised to create and increase recovery capital. The project involved 20 semi-structured interviews, two asset mapping workshops, a certificated “health issues” course completed by seven “champions”, and action planning and implementation. In the interviews participants found gaps were more easily identified than assets. During the workshops participants identified 388 discrete assets and gaps, prioritised these using a simple voting system and developed a series of actions to mobilise health assets including bringing into use local facilities and amenities and involving a number of individuals and groups in local events and activities. Our study suggests that even in the impoverished system of Clydeplace, a “Community Catalyst” in the form of a Community Operational Researcher can act to stimulate the co-development of health assets, build relationships and enable the creation of social capital. It is not clear though when such systems become “self-catalysing.”     

Optimal Stopping with a Probabilistic Constraint

We present an efficient method for solving optimal stopping problems with a probabilistic constraint. The goal is to optimize the expected cumulative cost, but constrained by an upper bound on the probability that the cost exceeds a specified threshold. This probabilistic constraint causes optimal policies to be time-dependent and randomized, however, we show that an optimal policy can always be selected with “piecewise-monotonic” time-dependence and “nearly-deterministic” randomization. We prove these properties using the Bellman optimality equations for a Lagrangian relaxation of the original problem. We present an algorithm that exploits these properties for computational efficiency. Its performance and the structure of optimal policies are illustrated on two numerical examples.     

Nonlinear Questions in Clamped Plate Models

The linear clamped plate boundary value problem is a classical model in mechanics. The underlying differential equation is elliptic and of fourth order. The latter is a peculiar feature with respect to which this equation differs from numerous equations in physics and engineering which are of second order. Concerning the clamped plate boundary value problem, “linear questions” may be considered as well understood. This changes completely as soon as one poses the simplest “nonlinear question”: What can be said about positivity preserving? Does a plate bend upwards when being pushed upwards? It is known that the answer is “no” in general. However, there are many positivity issues as e.g. “almost positivity” to be discussed. Boundary value problems for the “Willmore equation” are nonlinear counterparts for the linear clamped plate equation. The corresponding energy functional involves curvature integrals over the unknown surface. The Willmore equation is of interest in mechanics, membrane physics and, in particular, in differential geometry. Quite far reaching results were achieved concerning closed surfaces. As for boundary value problems, by far less is known. These will be discussed in symmetric situations. This survey article reports upon joint works with A. Dall’Acqua, K. Deckelnick (Magdeburg), S. Fröhlich (Free University of Berlin), F. Gazzola (Milan), F. Robert (Nice), Friedhelm Schieweck (Magdeburg) and G. Sweers (Cologne).     

基于互惠动机公平均衡的投资项目决策模型及数值模拟分析

针对博弈主体互惠动机公平偏好的证据和特征,本文从理论上描绘了首席执行官和项目经理在信息对称与非对称条件下的资本配置行为和激励合约的设计,在理论模型构建及均衡分析中发现:项目经理互惠动机公平偏好可以提高其努力水平,带来与显性激励合约一样的激励效果,即互惠动机公平偏好产生了“挤进激励效应”;互惠动机公平偏好使得项目经理真实地汇报项目质量状况,优化了公司对项目资本配置的计划,避免了非对称信息下的道德风险问题,即互惠动机公平偏好产生了“信号显示机制”的作用。由于项目经理互惠动机公平偏好的“挤进激励效应”,使得投资项目资本配置决策临界点不会很低,从而抑制了投资不足的严重性。本文的研究结果为具有异质性的项目经理提供了不同合约选择,把“自利”假设下委托代理决策的分析框架拓展到“非自利”的行为委托代理决策的分析框架。     

Reconstructing basic ideas in geometry—an empirical approach

“Basic ideas” (or “fundamental ideas” etc.) have been discussed in mathematical curriculum theory for about forty years. This paper will centre on the hypothesis that this concept can only be applied successfully by using it as a category for the analysis of concrete mathematical problems. This hypothesis will be illustrated by means of a sample problem from the Austrian Standards for Mathematics Education (“Bildungsstandards”). In this example, basic ideas are used in a content matter analysis which takes students' solutions to the problem as a starting point for the creation of a potentially substantial learning environment in trigonometry.     

Arbres de Markov couplePairwise Markov trees

The Hidden Markov Chain (HMC) models are widely applied in various problems. This succes is mainly due to the fact that the hidden model distribution conditional on observations remains a Markov chain distribution, and thus different processings, like Bayesian restorations, are handleable. These models have been recetly generalized to “Pairwise” Markov chains, which admit the same processing power and a better modeling one. The aim of this Note is to show that the Hidden Markov trees, which can be seen as extensions of the HMC models, can also be generalized to “Pairwise” Markov trees, which present the same processing advantages and better modelling power. To cite this article: W. Pieczynski, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 79–82.     

Least squares regression principal component analysis: A supervised dimensionality reduction method

Dimensionality reduction is an important technique in surrogate modeling and machine learning. In this article, we propose a supervised dimensionality reduction method, “least squares regression principal component analysis” (LSR-PCA), applicable to both classification and regression problems. To show the efficacy of this method, we present different examples in visualization, classification, and regression problems, comparing it with several state-of-the-art dimensionality reduction methods. Finally, we present a kernel version of LSR-PCA for problems where the inputs are correlated nonlinearly. The examples demonstrate that LSR-PCA can be a competitive dimensionality reduction method.     

Automatic Optimal Regularization for Ill-Posed Problems with Stochastical Noise without Imposing Smoothness Assumptions

We consider the compact operator A : 𝒳 → 𝒴 for the separable Hilbert spaces 𝒳 and 𝒴. The problem Ax = y is called ill-posed when the singular values s_k , k = 1, 2, … of the operator A tend to zero. Classically one assumes that y is biased with “deterministic noise”; we will also consider “stochastic noise” where the noise element is a weak Gaussian random variable. There classical stopping rules (e.g. Morozov) do not work. We will show that both for the “deterministic noise” case as well for the “stochastical noise” case we can regularize in an (asymptotically almost) optimal way without knowledge of the smoothness of the solution using Lepskij's method. Furthermore the method also works for estimated error levels and error behavior. So we can assure regularization which is just dependent on measurements obtainable in reality, e.g. satellite problems. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Asymptotic expansions of multiply scattered surface currents

We have recently uncovered the convergence characteristics of multiple scattering iterations for “two-dimensional” as well as “three-dimensional scalar (acoustics)” scattering models in the high-frequency regime. As we have demonstrated, a most distinctive property of these latermodels, compared to their two-dimensional counterparts, is the dependence of corresponding asymptotic expansions on the relative angle of rotation between the principal axes of the successive reflection points of the optical rays. Concerning the case of fully “three-dimensional vector (electromagnetic)” scattering problems, here we show that the vectorial nature of the problem, in turn, gives rise to new additional complex structure. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Substitutes and complements in network flow problems

If f is a function of several variables, one calls a pair of variables substitutes(complements) if the change of the value of the function when both variables are increased is at most (at least) equal to the sum of the changes when each is increased separately. We here consider the case where f is the value of a maximum weight circulation on a network and the variables are the upper and lower bounds and the weights of a pair of arcs. We introduce a simple combinatorial criterion for two arcs to be in “series” or “parallel” and show that these two cases correspond to the variables being complements or substitutes respectively. This generalizes results of Shapley for the special case of the maximum flow and optimal assignment problems. We also show that our result is best possible in that if two arcs are neither in series nor parallel, then the corresponding variables can be either substitutes or complements or both.     

A two-bottleneck system with binomial yields and rigid demand

This study considers multistage production systems where production is in lots and only two stages have non-zero setup costs. Yields are binomial and demand, needing to be satisfied in its entirety, is “rigid”. We refer to a stage with non-zero setup cost as a “bottleneck” (BN) and thus to the system as “a two-bottleneck system” (2-BNS). A close examination of the simplest 2-BNS reveals that costs corresponding to a particular level of work in process (WIP) depend upon costs for higher levels of WIP, making it impossible to formulate a recursive solution.For each possible configuration of intermediate inventories a production policy must specify at which stage to produce next and the number of units to be processed. We prove that any arbitrarily “fixed” production policy gives rise to a finite set of linear equations, and develop algorithms to solve the two-stage problem. We also show how the general 2-BNS can be reduced to a three-stage problem, where the middle stage is a non-BN, and that the algorithms developed can be modified to solve this problem.     

Noncommutative Generalizations of Theorems of Cohen and Kaplansky

This paper investigates situations where a property of a ring can be tested on a set of “prime right ideals.” Generalizing theorems of Cohen and Kaplansky, we show that every right ideal of a ring is finitely generated (resp. principal) iff every “prime right ideal” is finitely generated (resp. principal), where the phrase “prime right ideal” can be interpreted in one of many different ways. We also use our methods to show that other properties can be tested on special sets of right ideals, such as the right artinian property and various homological properties. Applying these methods, we prove the following noncommutative generalization of a result of Kaplansky: a (left and right) noetherian ring is a principal right ideal ring iff all of its maximal right ideals are principal. A counterexample shows that the left noetherian hypothesis cannot be dropped. Finally, we compare our results to earlier generalizations of Cohen’s and Kaplansky’s theorems in the literature.     

A high-order numerical manifold method with continuous stress/strain field

Recent attempts to solve solid mechanical problems using the numerical manifold method (NMM) are very fruitful. In the present work, a high-order numerical manifold method (HONMM) which is able to obtain continuous stress/strain field is proposed. By employing the same discretized model as the traditional NMM (TNMM), the proposed HONMM can yield much better accuracy without increasing the number of degrees of freedom (DOFs), and obtain continuous stress/strain field without recourse any stress smoothing operation in the post-processing stage. In addition, the “linear dependence” (LD) issue does not exist in the HONMM, and traditional equation solvers can be employed to solve the simultaneous algebraic equations. A number of numerical examples including four linear elastic continuous problems and five cracked problems are solved with the proposed method. The results show that the proposed HONMM performs much better than the TNMM.     

A cyclic projected gradient method

In recent years, convex optimization methods were successfully applied for various image processing tasks and a large number of first-order methods were designed to minimize the corresponding functionals. Interestingly, it was shown recently in Grewenig et al. (2010) that the simple idea of so-called “superstep cycles” leads to very efficient schemes for time-dependent (parabolic) image enhancement problems as well as for steady state (elliptic) image compression tasks. The “superstep cycles” approach is similar to the nonstationary (cyclic) Richardson method which has been around for over sixty years. In this paper, we investigate the incorporation of superstep cycles into the projected gradient method. We show for two problems in compressive sensing and image processing, namely the LASSO approach and the Rudin-Osher-Fatemi model that the resulting simple cyclic projected gradient algorithm can numerically compare with various state-of-the-art first-order algorithms. However, due to the nonlinear projection within the algorithm convergence proofs even under restrictive assumptions on the linear operators appear to be hard. We demonstrate the difficulties by studying the simplest case of a two-cycle algorithm in ?² with projections onto the Euclidean ball.     

What makes an optimization problem hand?

We address the question: “Are some classes of combinatorial optimization problems intrinsically harder than others, without regard to the algorithm one uses, or can difficulty only be assessed relative to particular algorithms?” We provide a measure of the hardness of a particular optimization problem for a particular optimization algorithm and present two algorithm-independent quantities that use this measure to provide answers to our question. In the first of these we average hardness over all possible algorithms and show that according to this quantity, there are no distinctions between optimization problems. In this sense no problems are intrinsically harder than others. For the second quantity, rather than average over all algorithms, we consider the level of hardness of a problem (or class of problems) for the associated optimal algorithm. By this criteria there are classes of problems that are intrinsically harder than others.     

There is no (46, 6, 1) block design*

Abstact: In this paper we show that a (46, 6, 1) design does not exist. This result was obtained by a computer search. In the incidence matrix of such a design, there must exist a “c4” configuration—6 rows and 4 columns, in which each pair of columns intersect exactly once, in distinct rows. There can also exist a “c5” configuration with 10 rows and 5 columns, in which each pair of columns intersect exactly once, in distinct rows. Thus the search for (46, 6, 1) designs can be subdivided into two cases, the first of which assumes there is no “c5”, and the second of which assumes there is a “c5”. After completing the searches for both cases, we found no (46, 6, 1) design. © 2000 John Wiley & Sons, Inc. J Combin Designs 9: 60–71, 2001