19454602
Asymptotic Strong Duality for Bounded Integer Programming: A Logarithmic-Exponential Dual Formulation
A logarithmic-exponential dual formulation is proposed in this paper for bounded integer programming problems. This new dual formulation possesses an asymptotic strong duality property and guarantees the identification of an optimal solution of the primal problem. These prominent features are achieved by exploring a novel nonlinear Lagrangian function, deriving an asymptotic zero duality gap, investigating the unimodality of the associated dual function and ensuring the primal feasibility of optimal solutions in the dual formulation. One other feature of the logarithmicexponential dual formulation is that no actual dual search is needed when parameters are set above certain threshold-values.
207726898
Quick response policy with Bayesian information updates
Abstract In this paper we investigate the quick response (QR) policy with different Bayesian models. Under QR policy, a retailer can collect market information from the sales of a pre-seasonal product whose demand is closely related to a seasonal product’s demand. This information is then used to update the distribution for the seasonal product’s demand by a Bayesian approach. We study two information update models: one with the revision of an unknown mean, and the other with the revision of both an unknown mean and an unknown variance. The impacts of the information updates under both models are compared and discussed. We also identify the features of the pre-seasonal product which can bring more significant profit improvement. We conclude that an effective QR policy depends on a precise information update model as well as a selection of an appropriate pre-seasonal product as the observation target.
36670641
A nonlinear Lagrangian dual for integer programming
Nonlinear Lagrangian theory offers a success guarantee for the dual search via construction of a nonlinear support of the perturbation function at the optimal point. In this paper, a new nonlinear dual formulation of an exponential form is proposed for bounded integer programming. This new formulation possesses an asymptotic strong duality property and guarantees a success in identifying a primal optimum solution. No actual dual search is needed in the solution process when the parameter of the nonlinear Lagrangian formulation is set to be large enough.
7454095
On the relationship between the integer and continuous solutions of convex programs
Abstract A bound is obtained in this note for the distance between the integer and real solutions to convex quadratic programs. This bound is a function of the condition number of the Hessian matrix. We further extend this proximity result to convex programs and mixed-integer convex programs. We also show that this bound is achievable in certain situations and the distance between the integer and continuous minimizers may tend to infinity.
27085223
Normal vector identification and interactive tradeoff analysis using minimax formulation in multiobjective optimization
In multiobjective optimization, tradeoff analysis plays an important role in determining the best search direction to reach a most preferred solution. This paper presents a new explicit interactive tradeoff analysis method based on the identification of normal vectors on a noninferior frontier. The interactive process is implemented using a weighted minimax formulation by regulating the relative weights of objectives in a systematic manner. It is proved under a mild condition that a normal vector can be identified using the weights and Kuhn-Tucker (K-T) multipliers in the minimax formulation. Utility gradients can be estimated using local preference information such as marginal rates of substitution. The projection of a utility gradient onto a tangent plane of the noninferior frontier provides a descent direction of disutility and thereby a desirable tradeoff direction, along which tradeoff step sizes can be decided by the decision maker using an explicit tradeoff table. Necessary optimality conditions are established in terms of normal vectors and utility gradients, which can be used to guide the elicitation of local preferences and also to terminate an interactive process in a rigorous yet flexible way. This method is applicable to both linear and nonlinear (either convex or nonconvex) multiobjective optimization problems. Numerical examples are provided to illustrate the theoretical results of the paper and the implementation of the proposed interactive decision analysis process.
17504688
A statistical method for binary classification of images
The classification of documents with sparse text, and video analysis, relies on accurate image classification. We herein present a method for binary classification that accommodates any number of individual classifiers. Each individual classifier is defined by the critical point between its two means, and its relative weighting is inversely proportional to its expected error rate. Using 10 simple image analysis metrics, we distinguish a set of "natural" and "city" scenes, providing a "semantically meaningful" classification. The optimal combination of 5 of these 10 classifiers provides 85.8% accuracy on a small (120 image) feasibility corpus. When this feasibility corpus is then split into half training and half testing images, the mean accuracy of the optimum set of classifiers was 81.7%. Accuracy as high as 90% was obtained for the test set when training percentage was increased. These results demonstrate that an accurate classifier can be constructed from a large pool of simple classifiers through the use of the statistical ("Normal") classification method described herein.
17075751
A collaboration specification language
COCA (Collaborative Objects Coordination Architecture) was proposed as a novel means to model and support collaborations over the Internet. Our approach separates coordination policies from user interfaces and the policies are specified in a logic-based language. Over the past year, both the collaboration model and the specification language have been substantially refined and evaluated through our experience in building real-life collaboration systems. This paper presents the design of the specification language and illustrates the main ideas with a few simple design examples. Semantics, implementation, runtime support, and applications are also covered but not as the focus of this paper.
5115871
Temporal Knowledge Discovery with Infrequent Episodes
In this paper, we present an efficient algorithm which discovers rare episodes with a combination of bottom-up and top-down scanning schema. The information sharing between bottom-up and top-down scannings helps prune candidate episodes, and thus, efficiently find infrequent episodes that are interesting to user: We evaluate the performance of the algorithm using real-life weather databases. We observe from experimental results that our approach results in 30%-90% reduction in computation time and 25%-75% reduction in the number of candidates comparing with Apriori algorithm.
15275424
Blur identification based on kurtosis minimization
In this paper, we describe an algorithm for identifying a parametrically described blur based on kurtosis minimization. Using different choices for the parameters of the blur, the noisy blurred image is restored using Wiener filter. We use the kurtosis as a measurement of the quality of the restored image. From the set of the candidate deblurred images, the one with the minimum kurtosis is selected. The proposed technique is tested in a simulated experiment on a variety of blurs including atmospheric turbulence blurs, Gaussian blurs, and out-of-focus blurs. The proposed approach is also tested on real blurred images. Moreover, we test the performance when a wrong blur model is given. Our experiments show that the kurtosis minimization measurements match well with methods that maximize PSNR.
274260
Preserving operation effects relation in group editors
Consistency maintenance is a critical and challenging issue in many interactive groupware applications that can be modeled as group editors. This paper addresses two open consistency problems: divergence and operation effects relation violation. While the former has been partly solved, the latter has never been addressed in any published work. We propose a novel approach to solving both problems in the same framework. Particularly it preserves the effects relation of concurrent operations so that convergence is achieved automatically. Our work provides a new perspective into group editors and operational transformation algorithms.