Protein Threading by Linear Programming: Theoretical Analysis and Computational Results

In a previous paper (Xu, Li, Kim, and Xu, Journal of Bioinformatics and Computational Biology, vol. 1, no. 1, pp. 95–117, 2003), we have used an integer programming approach to implement a protein threading program RAPTOR for protein 3D structure prediction, based on the threading model treating pairwise contacts rigorously and allowing variable gaps. We have solved the integer program by the canonical branch-and-bound method. In this paper we present a branch-and-cut method, a careful theoretical analysis of our formulation and why our approach is so effective. The result of cutting plane analysis is that two types of well-known cuts for this problem are already implied in the constraint set, which provides us some intuition that our formulation would be very effective. Experimental results show that for about 99 percent of real threading instances, the linear relaxations of their integer programs solve to integral optimal solutions directly. For the rest one percent of real instances, the integral solutions can be obtained with only several branch nodes. Experimental results also show that no special template or sequence features result in more possibilities of fractional solutions. This indicates that extra effort to seek for cutting planes to strengthen the existing formulation is unnecessary.     

A flight scheduling model for Taiwan airlines under market competitions

In this research, we develop a short-term flight scheduling model with variable market shares in order to help a Taiwan airline to solve for better fleet routes and flight schedules in today's competitive markets. The model is formulated as a non-linear mixed integer program, characterized as an NP-hard problem, which is more difficult to solve than the traditional fixed market share flight scheduling problems, often formulated as integer/mixed integer linear programs. We develop a heuristic method to efficiently solve the model. The test results, mainly using the data from a major Taiwan airline's operations, show the good performance of the model and the solution algorithm.     

由TCL吸收合并案引发的对定向发行方式的思考

本文阐述了定向发行方式的基本概念及在我国资本市场上的应用状况,并结合TCL的吸收合并案,分析了定向发行方式对集团公司整体上市和ST②公司公允重组的导向意义,指出了在此过程中存在的不足和应该注意的问题。     

二次松弛法求解资源配置型整数规划

针对资源配置型整数规划问题,将与优化机制无关的两类约束条件作二次松弛处理,应用领域整点搜索法求解资源配置型整数规划,大大地降低了运算规模和求解难度,为在管理实践中应用整数规划方法求解规模较大的复杂问题创造了有利条件.     

Erlang–Lindley distribution

In this paper, Erlang–Lindley distribution (ErLD) is proposed which offers a more flexible model for waiting time data. It has the property that it can accommodate increasing, bathtub, and inverted bathtub shapes. Several statistical and reliability properties are derived and studied. The moments, its associated measures, and the limiting distributions of order statistics are derived. The model parameters are estimated by maximum likelihood and method of moments. An application of the proposed distribution to some waiting time data shows that it can give a better fit than other important lifetime models.     

Fix-and-optimize and variable neighborhood search approaches for multi-level capacitated lot sizing problems

In this paper, a new fix-and-optimize (FO) approach is proposed for two dynamic multi-level capacitated lot sizing problems (MLCLSP), the MLCLSP without setup carryover and the MLCLSP with setup carryover. Given an MIP model of a lot sizing problem, the approach iteratively solves a series of sub-problems of the model until no better solution can be found. Each sub-problem re-optimizes a subset of binary decision variables determined based on the interrelatedness of binary variables in the constraints of the model, while fixing the values of the other binary variables. Based on the FO, a variable neighbourhood search (VNS) approach for the MLCLSP without setup carryover is also developed, which can further improve the solution obtained by the FO by diversifying the search space. Numerical experiments on benchmark instances show that both our FO and VNS approaches can obtain a better solution for most instances compared with that found by the fix-and-optimize approach proposed by Helber and Sahling (International Journal of Production Economics 2010;123:247–256).     

装卸工人调配问题新解法及其证明

阐述了现代物流技术中装卸工人调配问题、装卸工问题、限制情况下装卸工问题及其数学模型,证明了装卸工人调配问题与限制情况下装卸工问题的数学模型是等价的.通过分析装卸工人调配问题的数学性质得出该问题的一种新解法并给出其证明.新解法给出了该问题的所有最优解.     

关于广义Fibonacci函数的整数值

设a是正整数，数列满足遍推关系u0＝1，u1＝a，um＋2＝aum1＋um（m≥0），函数本。文证明了：对于任何正整数a，当且仅当X＝0或者X＝u2n-1／u2n（n∈N）时，U（x）是正整数上述结果完整地解决了Brugia、DiPorto和Filipponi提出的一个公开问题     

Scheduling aerial resource operations for the extinction of large-scale wildfires

The significant increase in large-scale wildfire events in recent decades, caused primarily by climate change, has resulted in a growing number of aerial resources being used in suppression efforts. Present-day management lacks efficient and scalable algorithms for complex aerial resource allocation and scheduling for the extinction of such fires, which is crucial to ensuring safety while maximizing the efficiency of operations. In this work, we present a Mixed Integer Linear Programming (MILP) optimization model tailored to large-scale wildfires for the daily scheduling of aerial operations. The main objective is to achieve a prioritized target water flow over all areas of operation and all time periods. Minimal target completion across individual areas and time periods and total water output are also maximized as secondary and ternary objectives, respectively. An efficient and scalable multi-start heuristic, combining a randomized greedy approach with simulated annealing employing large neighborhood search techniques, is proposed for larger instances. A diverse set of problem instances is generated with varying sizes and extinction strategies to test the approaches. Results indicate that the heuristic can achieve (near)-optimal solutions for smaller instances solvable by the MILP, and gives solutions approaching target water flows for larger problem sizes. The algorithm is parallelizable and has been shown to give promising results in a small number of iterations, making it applicable for both night-before planning and, more time-sensitive, early-morning scheduling.     

Optimum Multivariate Stratified Sampling Designs with Travel Cost: A Multiobjective Integer Nonlinear Programming Approach

The problem of optimum allocation in stratified sampling and its solution is well known in sampling literature for univariate populations (see Cochran, 1977 Cochran , W. G. ( 1977 ). Sampling Techniques. , 3rd ed. New York : Wiley . [Google Scholar]; Sukhatme et al., 1984 Sukhatme , P. V. , Sukhatme , B. V. , Sukhatme , S. , Ashok , C. ( 1984 ). Sampling Theory of Surveys With Applications. , 3rd ed. Ames , and New Delhi : Iowa State University Press and Indian Society of Agricultural Statistics . [Google Scholar]). In multivariate populations where more than one characteristics are to be studied on every selected unit of the population the problem of finding an optimum allocation becomes more complex due to conflicting behaviour of characteristics. Various authors such as Dalenius (1953 Dalenius , T. ( 1953 ). The multivariate sampling problem . Skandinavisk Actuarietidskrift 36 : 92 – 102 . [Google Scholar], 1957 Dalenius , T. ( 1957 ). Sampling in Sweden. Contributions to the Methods and Theories of Sample Survey Practice . Stockholm : Almqvist and Wicksell . [Google Scholar]), Ghosh (1958 Ghosh , S. P. ( 1958 ). A note on stratified random sampling with multiple characters . Calcutta Statistical Association Bulletin 8 : 81 – 89 . [Google Scholar]), Yates (1960 Yates , F. ( 1960 ). Sampling Methods for Censuses and Surveys. , 3rd ed. London : Charles Griffin . [Google Scholar]), Aoyama (1963 Aoyama , H. ( 1963 ). Stratified random sampling with optimum allocation for multivariate populations . Annals of the Institute of Statistical Mathematics 14 : 251 – 258 .[Crossref], [Web of Science ®] , [Google Scholar]), Gren (1964 Gren , J. ( 1964 ). Some methods of sample allocation in multivariate stratified sampling . Przeglad Statystyczny 11 : 361 – 369 (in Polish) . [Google Scholar], 1966 Gren , J. ( 1966 ). Some application of non-linear programming in sampling methods . Przeglad Statystyczny 13 : 203 – 217 (in Polish) . [Google Scholar]), Folks and Antle (1965 Folks , J. L. , Antle , C. E. ( 1965 ). Optimum allocation of sampling units to the strata when there are r responses of interest . Journal of American Statistical Association 60 : 225 – 233 .[Taylor & Francis Online], [Web of Science ®] , [Google Scholar]), Hartley (1965 Hartley , H. O. (1965). Multiple purpose optimum allocation in stratified sampling. Proc. Amer. Statist. Assoc. Social Statist. Sec. 258–261. [Google Scholar]), Kokan and Khan (1967 Kokan , A. R. , Khan , S. U. ( 1967 ). Optimum allocation in multivariate surveys: An analytical solution . Journal of Royal Statistical Society, Ser. B 29 : 115 – 125 . [Google Scholar]), Chatterjee (1972 Chatterjee , S. ( 1972 ). A study of optimum allocation in multivariate stratified surveys . Skandinavisk Actuarietidskrift 55 : 73 – 80 . [Google Scholar]), Ahsan and Khan (1977 Ahsan , M. J. , Khan , S. U. ( 1977 ). Optimum allocation in multivariate stratified random sampling using prior information . Journal of Indian Statistical Association 15 : 57 – 67 . [Google Scholar], 1982 Ahsan , M. J. , Khan , S. U. ( 1982 ). Optimum allocation in multivariate stratified random sampling with overhead cost . Metrika 29 : 71 – 78 .[Crossref] , [Google Scholar]), Chromy (1987 Chromy , J. R. ( 1987 ). Design optimization with multiple objectives. Proceedings of the Survey Research Methods, 194–199 . [Google Scholar]), Wywial (1988 Wywial , J. ( 1988 ). Minimizing the spectral radius of means vector from sample variance-covariance matrix sample allocation between strata. Prace Naukowe Akademii Ekonomicznej we Wroclawiu 404:223–235 (in Polish) . [Google Scholar]), Bethel (1989 Bethel , J. ( 1989 ). Sample allocation in multivariate surveys . Survey Methodology 15 : 47 – 57 . [Google Scholar]), Kreienbrock (1993 Kreienbrock , L. ( 1993 ). Generalized measures of dispersion to solve the allocation problem in multivariate stratified random sampling . Communication in Statistics—Theory and Methds 22 : 219 – 239 .[Taylor & Francis Online], [Web of Science ®] , [Google Scholar]), Jahan et al. (1994 Jahan , N. , Khan , M. G. M. , Ahsan , M. J. ( 1994 ). A generalized compromise allocation . Journal of the Indian Statistical Association 32 : 95 – 101 . [Google Scholar]), Khan et al. (1997 Khan , M. G. M. , Ahsan , M. J. , Jahan , N. ( 1997 ). Compromise allocation in multivariate stratified sampling: An integer solution . Naval Research Logistics 44 : 69 – 79 .[Crossref], [Web of Science ®] , [Google Scholar]), Khan et al. (2003 Khan , M. G. M. , Khan , E. A. , Ahsan , M. J. ( 2003 ). An optimal multivariate stratified sampling design using dynamic programming . Australian & New Zealand J. Statist. 45 : 107 – 113 .[Crossref], [Web of Science ®] , [Google Scholar]), Ahsan et al. (2005 Ahsan , M. J. , Najmussehar, Khan , M. G. M. ( 2005 ). Mixed allocation in stratified sampling . Aligarh Journal of Statistics 25 : 87 – 97 . [Google Scholar]), Díaz-García and Ulloa (2006 Díaz-García , J. A. , Ulloa , C. L. ( 2006 ). Optimum allocation in multivariate stratified sampling: Multi-objective programming. Comunicación Técnica No. I-06-07/28-03-206 (PE/CIMAT), Guanajuato, México . [Google Scholar], 2008 Díaz-García , J. A. , Ulloa , C. L. ( 2008 ). Multi-objective optimization for optimum allocation in multivariate stratified sampling . Survey Methodology 34 : 215 – 222 .[Web of Science ®] , [Google Scholar]), Ahsan et al. (2009 Ansari , A. H. , Najmussehar, Ahsan , M. J. ( 2009 ). On multiple response stratified random sampling design . International Journal of Statistical Sciences , Kolkata, India, 1(1):1–11 . [Google Scholar]) etc. used different compromise criteria to work out a compromise allocation that is optimum for all characteristics in some sense.

Almost all the previous authors used some function of the sampling variances of the estimators of various characteristics to be measured as an objective that is to be minimized for a fixed cost given as a linear function of sample allocations. Because the variances are not unit free it is more logical to consider the minimization of some function of squared coefficient of variations as an objective. Previously this concept was used by Kozok (2006 Kozok , M. ( 2006 ). On sample allocation in multivariate surveys . Communication in Statistics—Simulation and Computation 35 : 901 – 910 .[Taylor & Francis Online], [Web of Science ®] , [Google Scholar]).

Furthermore, investigators have to approach the sampled units in order to get the observations. This involves some travel cost. Usually this cost is neglected while constructing a cost function. This travel cost may be significant in some surveys. For example if the strata consist of some geographically difficult-to-approach areas.

The authors problem of optimum allocation in multivariate stratified sampling is discussed with an objective to minimize simultaneously the coefficients of variation of the estimators of various characteristics under a cost constraint that includes the measurement as well as travel cost. The formulated problem of obtaining an optimum compromise allocation turns out to be a multiobjective all-integer nonlinear programming problem. Three different approaches are considered: the value function approach, ∈ –constraint method, and Distance–based method, to obtain compromise allocations. The cost function considered also includes the travel cost within stratum to reach the selected units. Additional restrictions are placed on the sample sizes to avoid oversampling and ensure the availability of the estimates of the strata variances. Numerical examples are also presented to illustrate the computational details of the proposed methods.