An exact algorithm for solving a capacitated location-routing problem

In location-routing problems, the objective is to locate one or many depots within a set of sites (representing customer locations or cities) and to construct delivery routes from the selected depot or depots to the remaining sites at least system cost. The objective function is the sum of depot operating costs, vehicle acquisition costs and routing costs. This paper considers one such problem in which a weight is assigned to each site and where sites are to be visited by vehicles having a given capacity. The solution must be such that the sum of the weights of sites visited on any given route does not exceed the capacity of the visiting vehicle. The formulation of an integer linear program for this problem involves degree constraints, generalized subtour elimination constraints, and chain barring constraints. An exact algorithm, using initial relaxation of most of the problem constraints, is presented which is capable of solving problems with up to twenty sites within a reasonable number of iterations.     

Predicting experimental yields as an index to rank synthesis routes II: application to the Curtius rearrangement

Synthesis yields of organic reactions are one of the most important factors in ranking synthesis routes created by synthesis route design systems such as Transform‐Oriented Synthesis Planning and Knowledge base‐Oriented Synthesis Planning. If it is possible to predict the yields of synthesis reactions before starting experiments, one can easily determine an order of synthesis routes for experimental works. In the present study, the reaction profiles of the Curtius rearrangement with different substituents were calculated to generate an equation predicting experimental yields of this reaction. Reactions followed by the formation of isocyanates were also analyzed to consider the relationship between reaction times and experimental yields. A partial least squares (PLS) regression was used to correlate the experimental yields with the calculated activation energies, E_a(calc), together with experimental conditions such as dielectric constants of solvents, reaction times, and reaction temperatures as explanatory variables. Although the PLS regression using all the data gave very poor results, we succeeded in making a model equation with R² = 0.887 using a modified data set. However, there is a conflict between the predictability and the interpretability on the reaction time. This discrepancy mainly comes from unnecessarily long reaction times in the experiments for azides with calculated E_a values of less than 33 kcal mol^–1. To construct a good model equation for the experimental yields of the Curtius reaction, we have to use data sets obtained from within 90 min of the reaction for the PLS regression. Copyright © 2011 John Wiley & Sons, Ltd.     

利用近红外及中红外融合技术对小麦产地和烘干程度的同时鉴别

小麦是制作馒头的主要原料之一,小麦中水、蛋白质、淀粉会因产地以及烘干程度的差异而不同,进而影响到加工成馒头的品质。所以实现对小麦产地和烘干程度的快速鉴别就显得尤为重要。感官评定是鉴别小麦产地和烘干程度常用的方法,对比感官评定,光谱分析可以识别样品中的分子结构等信息。基于此,尝试利用近红外和中红外光谱融合技术实现对不同产地和不同烘干程度的小麦同时鉴别。首先选取了两个不同产地的小麦,再利用微波干燥法对两个不同产地的小麦做烘干预处理,使烘干的小麦水含量为12%±0.5%,原麦水含量为18%±0.5%。分别标记为原麦A,烘干A,原麦B,烘干B,再将小麦研磨成粉末,过100目筛网筛选后,置于自封袋中备用。随后分别采集四种小麦样品的近红外和中红外光谱信息,在Matlab 7.10的环境下使用标准正态变量变换(standard normal variable transformation, SNVT)对采集到的原始光谱数据进行预处理,利用主成分分析对预处理后的数据进行降维处理,再结合线性判别分析（linear discriminant analysis,LDA）和支持向量机（support vector machine, SVM）分别建立小麦近红外、中红外光谱数据识别模型。另外利用联合区间偏最小二乘法（synergy interval partial least square, SiPLS）筛选出利用标准正态变量变换(SNVT)预处理后的小麦近红外和中红外光谱数据特征光谱区间,将筛选出的近红外和中红外光谱数据特征光谱区间融合后再结合线性判别分析（LDA）和支持向量机（SVM）建立小麦融合光谱信息的识别模型。然后比较同种光谱数据下利用线性判别分析（LDA）和支持向量机（SVM）建立的小麦识别模型识别率、比较同种建模方法下近红外和中红外光谱数据建立小麦识别模型识别率、比较同种建模方法下光谱数据融合和单一光谱数据建立小麦识别模型识别率。结果表明,同种光谱分析方法,利用SVM建立的四种小麦识别模型识别率高于利用LDA建立的小麦识别模型识别率。同种建模方法,近红外光谱数据建立的小麦识别模型识别率优于中红外光谱数据建立的小麦识别模型识别率。而在同种建模方法下,利用SiPLS筛选出近红外和中红外光谱数据的特征光谱区间数据融合后建立小麦识别模型识别率最高,光谱数据融合后结合LDA建立的小麦识别模型校正集识别率为98.75%,预测集识别率为97.50%;而将此选择的变量结合SVM建立的小麦识别模型的校正集和预测集识别率都达到100.0%。对比利用单一光谱数据建立的小麦识别模型识别率,光谱数据融合之后建立的小麦识别模型识别率得到显著提高,该研究从纵向和横向上全面地比较了光谱数据建立的小麦模型识别率,结果可为更准确地运用光谱融合技术建立小麦产地以及烘干程度识别模型提供参考。     

高光谱成像的土壤剖面水分含量反演及制图

传统土壤水分的获取方法仅可获得离散的土壤水分点位数据,难以获得剖面上精细且连续的水分含量分布图。研究了野外条件下利用近红外高光谱（882～1 709 nm）成像反演剖面土壤水分含量（SMC）,并实现精细制图的可行性。研究剖面位于江苏省东台市,我们利用近红外高光谱成像仪对剖面进行了5天原位连续观测,共采集了280个土样用于烘干法测定SMC。原始高光谱图像经数字量化值（DN）校正、黑白校正、拼接、几何校正、剪切和掩膜等一系列预处理后,提取各采样点的平均光谱反射率。提取光谱（Raw）经吸光度[LOG₁₀(1/R)],Savitzky-Golay平滑（SG）、一阶微分（FD）、二阶微分（SD）、多元散射校正（MSC）和标准正态变量（SNV）转换后,采用偏最小二乘回归（PLSR）和最小二乘支持向量机（LS-SVM）方法建立SMC预测模型,并对比分析不同光谱预处理方法与建模方法组合条件下SMC的预测精度。结果表明,光谱反射率随SMC增加逐渐降低,不同光谱预处理方法的预测精度有所差异,除MSC方法外,同一光谱预处理方法的LS-SVM模型预测精度均高于PLSR模型,并且基于LOG₁₀(1/R)光谱的LS-SVM模型对SMC预测精度最高,其建模集的决定系数（R2_c）和均方根误差（RMSE_c）分别为0.96和0.65%,预测集的决定系数（R2_p）、均方根误差（RMSE_p）和相对分析误差（RPD_p）分别为0.88,1.05%和2.88。利用最优模型进行剖面SMC的高空间分辨率精细制图,通过比较SMC反演图中提取的预测值与实测值关系发现预测精度较高（R2: 0.85～0.95, RMSE: 0.94%～1.02%）,且两者在剖面中的变化趋势基本一致,说明SMC反演图不仅能很好地反映出土壤水分在整个剖面中毫米级的含量分布信息,也可反映出同一位置处不同天数间的含量差异。因此,利用近红外高光谱成像结合优化的预测模型,能够实现土壤剖面SMC的定量预测及精细制图,有助于快速、有效监测田间剖面土壤水分状况。     

On the solutions of the equation AXB = C under Toeplitz‐like and Hankel matrices constraint

In this paper, we are mainly concerned with 2 types of constrained matrix equation problems of the form AXB=C, the least squares problem and the optimal approximation problem, and we consider several constraint matrices, such as general Toeplitz matrices, upper triangular Toeplitz matrices, lower triangular Toeplitz matrices, symmetric Toeplitz matrices, and Hankel matrices. In the first problem, owing to the special structure of the constraint matrix , we construct special algorithms; necessary and sufficient conditions are obtained about the existence and uniqueness for the solutions. In the second problem, we use von Neumann alternating projection algorithm to obtain the solutions of problem. Then we give 2 numerical examples to demonstrate the effectiveness of the algorithms.     

A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms

The main goals of this paper are to: i) relate two iteration-complexity bounds derived for the Mizuno-Todd-Ye predictor-corrector (MTY P-C) algorithm for linear programming (LP), and; ii) study the geometrical structure of the LP central path. The first iteration-complexity bound for the MTY P-C algorithm considered in this paper is expressed in terms of the integral of a certain curvature function over the traversed portion of the central path. The second iteration-complexity bound, derived recently by the authors using the notion of crossover events introduced by Vavasis and Ye, is expressed in terms of a scale-invariant condition number associated with m × n constraint matrix of the LP. In this paper, we establish a relationship between these bounds by showing that the first one can be majorized by the second one. We also establish a geometric result about the central path which gives a rigorous justification based on the curvature of the central path of a claim made by Vavasis and Ye, in view of the behavior of their layered least squares path following LP method, that the central path consists of long but straight continuous parts while the remaining curved part is relatively “short”. R. D. C. Monteiro was supported in part by NSF Grants CCR-0203113 and CCF-0430644 and ONR grant N00014-05-1-0183. T. Tsuchiya was supported in part by Japan-US Joint Research Projects of Japan Society for the Promotion of Science “Algorithms for linear programs over symmetric cones” and the Grants-in-Aid for Scientific Research (C) 15510144 of Japan Society for the Promotion of Science.     

A nullstellensatz and a positivstellensatz for ordered differential fields

We use the model completeness and axiomatisation of the theory of closed ordered differential fields to give a differential version of Dubois, Krivine and Risler's nullstellensatz and Stengle's positivstellensatz for ordered fields.     

A brief historical introduction to Euler's formula for polyhedra,topology, graph theory and networks

This article is essentially devoted to a brief historical introduction to Euler's formula for polyhedra, topology, theory of graphs and networks with many examples from the real-world. Celebrated Königsberg seven-bridge problem and some of the basic properties of graphs and networks for some understanding of the macroscopic behaviour of real physical systems are included. We also mention some important and modern applications of graph theory or network problems from transportation to telecommunications. Graphs or networks are effectively used as powerful tools in industrial, electrical and civil engineering, communication networks in the planning of business and industry. Graph theory and combinatorics can be used to understand the changes that occur in many large and complex scientific, technical and medical systems. With the advent of fast large computers and the ubiquitous Internet consisting of a very large network of computers, large-scale complex optimization problems can be modelled in terms of graphs or networks and then solved by algorithms available in graph theory. Many large and more complex combinatorial problems dealing with the possible arrangements of situations of various kinds, and computing the number and properties of such arrangements can be formulated in terms of networks. The Knight's tour problem, Hamilton's tour problem, problem of magic squares, the Euler Graeco-Latin squares problem and their modern developments in the twentieth century are also included.     

连续小波变换高光谱数据的土壤有机质含量反演模型构建

土壤有机质含量是反映土壤肥力的重要指标,对其进行动态监测是实施精准农业的重要措施。近年来,众多学者尝试采用土壤近地传感(proximal soil sensing),尤其是近地高光谱技术,在田间和实验室获取不同形态土壤的高光谱数据,不断引入新方法建立适用于不同地域和不同土壤类型的有机质含量的反演模型。该研究在实验室内利用ASD FS3采集了土壤高光谱数据,采用“重铬酸钾-外加热法”测得了土壤有机质含量;分析了土壤原始光谱反射率(R)与有机质含量的相关性,选取R2>0.15的敏感波段的反射率;利用CWT对土壤原始光谱反射率(R)、光谱反射率的连续统去除(CR)进行不同尺度的分解,分析小波系数与土壤有机质含量的相关性,选取R2>0.3的敏感波段的小波系数;利用R选取的波段信息和R-CWT,CR-CWT的选取的小波系数,分别建立偏最小二乘回归(PLSR)、BP神经网络(BPNN)、支持向量机回归(SVMR)三种不同的土壤有机质含量反演模型。结果表明：相比R与土壤有机质含量的决定系数R2,R-CWT,CR-CWT变换后得到的小波系数与土壤有机质含量的决定系数R2分别提高了0.15和0.2左右;CR-CWT-SVMR的模型效果最为显著,预测集的R2和RMSE分别为0.83,4.02,RPD值为2.48,具有较高的估测精度,能够全面稳定地估算土壤有机质含量;CR-CWT-PLSR的模型精度与CR-CWT-BPNN,CR-CWT-SVMR相比虽有一定差距,但是其计算量要明显小于非线性的BPNN和SVMR方法,具有模型简单、运算速度快等特点,对开发与设计田间传感器具有较大的应用价值。     

SPA-PLS的高含水原油近红外光谱含水率分析

准确及时的检测原油含水率对注水策略调整、原油开采能力评估、油井开发寿命预测等均具有重要意义。然而,当前我国大多数油田均已进入高含水的开发中晚期,含水率测量难度大且准确率不高。在此背景下,开展了高含水情况下利用近红外光谱进行原油含水率测量的研究。 首先介绍了目前原油含水率检测的常用方法,分析了它们的优劣。理论上,由于水的近红外光吸收带与原油中C-H键的吸收带有明显区别,根据Lambert-Beer吸收定律和吸光度线性叠加定律可知,不同含水率高含水原油近红外光谱会存在较强响应差异。为此,对高含水原油进行近红外光谱检测,建立原油含水率与近红外光谱响应间的非线性映射模型,可实现高含水原油含水率的精确测量。为了验证该方法的有效性,搭建了近红外光谱数据采集实验装置：采用白炽灯作为光源,经过光路调节成平行光后垂直射入样品池,用近红外光谱仪（海洋光学NIR512）采集光谱用于分析。其中,接收光谱仪带宽为900～1 700 nm,平均分成512个波段。光谱数据利用光谱仪配套软件储存在电脑中。样本采用相同厚度不同比例的油水混合物,样本含水率范围为70%～99%,共采集数据60组,每组重复3次取平均值。得到原始数据后,先进行原始数据预处理,以减少数据采集时来自高频随机噪音及温度不稳定、样本不均匀、基线漂移、光散射等不利因素的影响。分别选用了S-G滤波、一阶导数和S-G滤波+一阶导数作为数据预处理的方法,利用连续投影算法(SPA)对光谱数据进行降维,并利用偏最小二乘法（PLS）和多元线性回归（MLR）进行建模,模型精度通过计算均方根误差值（RMSE）和相关系数（r）来验证。对比发现,使用S-G滤波+一阶导数建立的模型RMSE值最小（RMSE=0.007 0,r=0.998 3）。使用SPA降维后的模型要优于全波段PLS模型（RMSE=0.083 3,r=0.920 6）与MLR模型（RMSE=0.099 9,r=0.967 1）。利用SPA提取出的31个特征波长建立的模型仅占全波段的6.05%,并获得了较好的精度。证明了利用光谱检测高含水原油含水率可行性,并且得到了满意的精度,为高含水原油的含水率检测提供了新的方法, 为进一步利用近红外光进行高含水原油的快速检测与在线监测提供参考。