The purpose of this paper is to introduce a new pivot rule of the simplex algorithm. The simplex algorithm first presented by George B. Dantzig, is a widely used method for solving a linear programming problem (LP). O...The purpose of this paper is to introduce a new pivot rule of the simplex algorithm. The simplex algorithm first presented by George B. Dantzig, is a widely used method for solving a linear programming problem (LP). One of the important steps of the simplex algorithm is applying an appropriate pivot rule to select the basis-entering variable corresponding to the maximum reduced cost. Unfortunately, this pivot rule not only can lead to a critical cycling (solved by Bland’s rules), but does not improve efficiently the objective function. Our new pivot rule 1) solves the cycling problem in the original Dantzig’s simplex pivot rule, and 2) leads to an optimal improvement of the objective function at each iteration. The new pivot rule can lead to the optimal solution of LP with a lower number of iterations. In a maximization problem, Dantzig’s pivot rule selects a basis-entering variable corresponding to the most positive reduced cost;in some problems, it is well-known that Dantzig’s pivot rule, before reaching the optimal solution, may visit a large number of extreme points. Our goal is to improve the simplex algorithm so that the number of extreme points to visit is reduced;we propose an optimal improvement in the objective value per unit step of the basis-entering variable. In this paper, we propose a pivot rule that can reduce the number of such iterations over the Dantzig’s pivot rule and prevent cycling in the simplex algorithm. The idea is to have the maximum improvement in the objective value function: from the set of basis-entering variables with positive reduced cost, the efficient basis-entering variable corresponds to an optimal improvement of the objective function. Using computational complexity arguments and some examples, we prove that our optimal pivot rule is very effective and solves the cycling problem in LP. We test and compare the efficiency of this new pivot rule with Dantzig’s original pivot rule and the simplex algorithm in MATLAB environment.展开更多
Various trading strategies are applied in intraday high-frequency market to provide investors with reference signals to be on the right side of market at the right time. In this paper, we apply a trading strategy base...Various trading strategies are applied in intraday high-frequency market to provide investors with reference signals to be on the right side of market at the right time. In this paper, we apply a trading strategy based on the combination of ACD rules and pivot points system, which is first proposed by Mark B. Fisher, into Chinese market. This strategy has been used by millions of traders to achieve substantial profits in the last two decades, however, discussions concerning on the methods of calculating specific entry point in this trading strategy are rare, which is crucial to this strategy. We suggest an improvement to this popular strategy, providing the calculating and optimizing methods in detail to verify its effectiveness in recent Chinese futures market. Because of the high liquidity and low commissions in stock index futures market, this trading strategy achieves substantial profits .However, given the less liquidity in commodity futures market, profits decrease and even be neutralized by the relatively high commissions.展开更多
Based on the existing pivot rules,the simplex method for linear programming is not polynomial in the worst case.Therefore,the optimal pivot of the simplex method is crucial.In this paper,we propose the optimal rule to...Based on the existing pivot rules,the simplex method for linear programming is not polynomial in the worst case.Therefore,the optimal pivot of the simplex method is crucial.In this paper,we propose the optimal rule to find all the shortest pivot paths of the simplex method for linear programming problems based on Monte Carlo tree search.Specifically,we first propose the SimplexPseudoTree to transfer the simplex method into tree search mode while avoiding repeated basis variables.Secondly,we propose four reinforcement learning models with two actions and two rewards to make the Monte Carlo tree search suitable for the simplex method.Thirdly,we set a new action selection criterion to ameliorate the inaccurate evaluation in the initial exploration.It is proved that when the number of vertices in the feasible region is C_(n)^(m),our method can generate all the shortest pivot paths,which is the polynomial of the number of variables.In addition,we experimentally validate that the proposed schedule can avoid unnecessary search and provide the optimal pivot path.Furthermore,this method can provide the best pivot labels for all kinds of supervised learning methods to solve linear programming problems.展开更多
To gain superior computational efficiency, it might be necessary to change the underlying philosophy of the simplex method. In this paper, we propose a Phase-1 method along this line. We relax not only the conventiona...To gain superior computational efficiency, it might be necessary to change the underlying philosophy of the simplex method. In this paper, we propose a Phase-1 method along this line. We relax not only the conventional condition that some function value increases monotonically, but also the condition that all feasible variables remain feasible after basis change in Phase-1. That is, taking a purely combinatorial approach to achieving feasibility. This enables us to get rid of ratio test in pivoting, reducing computational cost per iteration to a large extent. Numerical results on a group of problems are encouraging.展开更多
目的:探讨"胃癌前病变"治疗用药规律。方法:广泛收集了1978年"胃癌前病变"命名以来至2017年的该病治疗方药,采取"Excel 2013数据透视表","SQL Server 2012"频数分析、关联分析等方法进行数据...目的:探讨"胃癌前病变"治疗用药规律。方法:广泛收集了1978年"胃癌前病变"命名以来至2017年的该病治疗方药,采取"Excel 2013数据透视表","SQL Server 2012"频数分析、关联分析等方法进行数据分析。结果:"胃癌前病变"治法是补气养血,提高机体免疫力,如黄芪、白术、当归等,治其本;解毒散结、活血消痈,转变肠上皮化生,消散异型增生,如白花蛇舌草、莪术、蒲公英等,治其标。同时补中偏重于行,偏重于活血、祛湿,如偏重丹参、白术、茯苓的配伍,结合疾病本身特点,可以看出中医药治疗该病时补而不滞,补中寓散,补以促行是其重要治疗思路。展开更多
文章以《中医方剂大辞典》为线索,筛选治疗"脾虚证"方剂850首,采取"Excel数据透视表"、"SQL Server 2005_DMAddin关联规则"、"spss17.0因子分析"等方法,探讨"脾气血两虚证"存在情况...文章以《中医方剂大辞典》为线索,筛选治疗"脾虚证"方剂850首,采取"Excel数据透视表"、"SQL Server 2005_DMAddin关联规则"、"spss17.0因子分析"等方法,探讨"脾气血两虚证"存在情况及其用药配伍规律。结果显示,"脾气血两虚证"存在,其治疗方剂主要由补气药、补血药配伍利水渗湿药、补阴药、活血祛瘀药等组成,基础方为"人参、炙黄芪、山药、当归、白芍、炙甘草",核心配伍为"人参、当归"。展开更多
目的:探讨"脾胃阳虚证"方药配伍规律。方法:以《中医方剂大辞典》为线索,筛选治疗"脾胃阳虚证"方剂203首,采取"Excel数据透视表","SQL Server 2005_DMAddin关联规则","spss17.0因子分析&q...目的:探讨"脾胃阳虚证"方药配伍规律。方法:以《中医方剂大辞典》为线索,筛选治疗"脾胃阳虚证"方剂203首,采取"Excel数据透视表","SQL Server 2005_DMAddin关联规则","spss17.0因子分析"等方法,进行数据分析。结果:治疗"脾胃阳虚证"方剂中,温里药、补气药分别占整个用药23%、20%,而补阳药仅占用药2%;出现频次超过60次的药物是炙甘草、白术、人参、干姜、厚朴、附子等;关联性较为重要的药物是干姜、白术、人参、炙甘草、附子等;排名较前公因子分别代表"补气药"集合,"理气活血化湿药"集合,"温里药"集合等。结论:"脾胃阳虚证"治疗方剂由"温里药"、"补气药"配伍"理气药","芳香化湿药"等而成,基础方为"人参、白术、干姜、炙甘草、附子、诃子、茯苓、厚朴"。展开更多
Despite it is often available in practice, information of optimal value of linear programming problems is ignored by conventional simplex algorithms. To speed up solution process, we propose in this paper some vari...Despite it is often available in practice, information of optimal value of linear programming problems is ignored by conventional simplex algorithms. To speed up solution process, we propose in this paper some variants of the bisection algorithm, explo展开更多
Recently, computational results demonstrated remarkable superiority of a so-called ＂largest-distance＂ rule and ＂nested pricing＂ rule to other major rules commonly used in practice, such as Dantzig＇s original rule...Recently, computational results demonstrated remarkable superiority of a so-called ＂largest-distance＂ rule and ＂nested pricing＂ rule to other major rules commonly used in practice, such as Dantzig＇s original rule, the steepest-edge rule and Devex rule. Our computational experiments show that the simplex algorithm using a combination of these rules turned out to be even more efficient.展开更多
文摘The purpose of this paper is to introduce a new pivot rule of the simplex algorithm. The simplex algorithm first presented by George B. Dantzig, is a widely used method for solving a linear programming problem (LP). One of the important steps of the simplex algorithm is applying an appropriate pivot rule to select the basis-entering variable corresponding to the maximum reduced cost. Unfortunately, this pivot rule not only can lead to a critical cycling (solved by Bland’s rules), but does not improve efficiently the objective function. Our new pivot rule 1) solves the cycling problem in the original Dantzig’s simplex pivot rule, and 2) leads to an optimal improvement of the objective function at each iteration. The new pivot rule can lead to the optimal solution of LP with a lower number of iterations. In a maximization problem, Dantzig’s pivot rule selects a basis-entering variable corresponding to the most positive reduced cost;in some problems, it is well-known that Dantzig’s pivot rule, before reaching the optimal solution, may visit a large number of extreme points. Our goal is to improve the simplex algorithm so that the number of extreme points to visit is reduced;we propose an optimal improvement in the objective value per unit step of the basis-entering variable. In this paper, we propose a pivot rule that can reduce the number of such iterations over the Dantzig’s pivot rule and prevent cycling in the simplex algorithm. The idea is to have the maximum improvement in the objective value function: from the set of basis-entering variables with positive reduced cost, the efficient basis-entering variable corresponds to an optimal improvement of the objective function. Using computational complexity arguments and some examples, we prove that our optimal pivot rule is very effective and solves the cycling problem in LP. We test and compare the efficiency of this new pivot rule with Dantzig’s original pivot rule and the simplex algorithm in MATLAB environment.
文摘Various trading strategies are applied in intraday high-frequency market to provide investors with reference signals to be on the right side of market at the right time. In this paper, we apply a trading strategy based on the combination of ACD rules and pivot points system, which is first proposed by Mark B. Fisher, into Chinese market. This strategy has been used by millions of traders to achieve substantial profits in the last two decades, however, discussions concerning on the methods of calculating specific entry point in this trading strategy are rare, which is crucial to this strategy. We suggest an improvement to this popular strategy, providing the calculating and optimizing methods in detail to verify its effectiveness in recent Chinese futures market. Because of the high liquidity and low commissions in stock index futures market, this trading strategy achieves substantial profits .However, given the less liquidity in commodity futures market, profits decrease and even be neutralized by the relatively high commissions.
基金supported by National Key R&D Program of China(Grant No.2021YFA1000403)National Natural Science Foundation of China(Grant No.11991022)+1 种基金the Strategic Priority Research Program of Chinese Academy of Sciences(Grant No.XDA27000000)the Fundamental Research Funds for the Central Universities。
文摘Based on the existing pivot rules,the simplex method for linear programming is not polynomial in the worst case.Therefore,the optimal pivot of the simplex method is crucial.In this paper,we propose the optimal rule to find all the shortest pivot paths of the simplex method for linear programming problems based on Monte Carlo tree search.Specifically,we first propose the SimplexPseudoTree to transfer the simplex method into tree search mode while avoiding repeated basis variables.Secondly,we propose four reinforcement learning models with two actions and two rewards to make the Monte Carlo tree search suitable for the simplex method.Thirdly,we set a new action selection criterion to ameliorate the inaccurate evaluation in the initial exploration.It is proved that when the number of vertices in the feasible region is C_(n)^(m),our method can generate all the shortest pivot paths,which is the polynomial of the number of variables.In addition,we experimentally validate that the proposed schedule can avoid unnecessary search and provide the optimal pivot path.Furthermore,this method can provide the best pivot labels for all kinds of supervised learning methods to solve linear programming problems.
文摘To gain superior computational efficiency, it might be necessary to change the underlying philosophy of the simplex method. In this paper, we propose a Phase-1 method along this line. We relax not only the conventional condition that some function value increases monotonically, but also the condition that all feasible variables remain feasible after basis change in Phase-1. That is, taking a purely combinatorial approach to achieving feasibility. This enables us to get rid of ratio test in pivoting, reducing computational cost per iteration to a large extent. Numerical results on a group of problems are encouraging.
文摘目的:探讨"胃癌前病变"治疗用药规律。方法:广泛收集了1978年"胃癌前病变"命名以来至2017年的该病治疗方药,采取"Excel 2013数据透视表","SQL Server 2012"频数分析、关联分析等方法进行数据分析。结果:"胃癌前病变"治法是补气养血,提高机体免疫力,如黄芪、白术、当归等,治其本;解毒散结、活血消痈,转变肠上皮化生,消散异型增生,如白花蛇舌草、莪术、蒲公英等,治其标。同时补中偏重于行,偏重于活血、祛湿,如偏重丹参、白术、茯苓的配伍,结合疾病本身特点,可以看出中医药治疗该病时补而不滞,补中寓散,补以促行是其重要治疗思路。
文摘文章以《中医方剂大辞典》为线索,筛选治疗"脾虚证"方剂850首,采取"Excel数据透视表"、"SQL Server 2005_DMAddin关联规则"、"spss17.0因子分析"等方法,探讨"脾气血两虚证"存在情况及其用药配伍规律。结果显示,"脾气血两虚证"存在,其治疗方剂主要由补气药、补血药配伍利水渗湿药、补阴药、活血祛瘀药等组成,基础方为"人参、炙黄芪、山药、当归、白芍、炙甘草",核心配伍为"人参、当归"。
文摘目的:探讨"脾胃阳虚证"方药配伍规律。方法:以《中医方剂大辞典》为线索,筛选治疗"脾胃阳虚证"方剂203首,采取"Excel数据透视表","SQL Server 2005_DMAddin关联规则","spss17.0因子分析"等方法,进行数据分析。结果:治疗"脾胃阳虚证"方剂中,温里药、补气药分别占整个用药23%、20%,而补阳药仅占用药2%;出现频次超过60次的药物是炙甘草、白术、人参、干姜、厚朴、附子等;关联性较为重要的药物是干姜、白术、人参、炙甘草、附子等;排名较前公因子分别代表"补气药"集合,"理气活血化湿药"集合,"温里药"集合等。结论:"脾胃阳虚证"治疗方剂由"温里药"、"补气药"配伍"理气药","芳香化湿药"等而成,基础方为"人参、白术、干姜、炙甘草、附子、诃子、茯苓、厚朴"。
文摘Despite it is often available in practice, information of optimal value of linear programming problems is ignored by conventional simplex algorithms. To speed up solution process, we propose in this paper some variants of the bisection algorithm, explo
基金supported by National Natural Science Foundation of China under the Projects 10871043 and 70971136
文摘Recently, computational results demonstrated remarkable superiority of a so-called ＂largest-distance＂ rule and ＂nested pricing＂ rule to other major rules commonly used in practice, such as Dantzig＇s original rule, the steepest-edge rule and Devex rule. Our computational experiments show that the simplex algorithm using a combination of these rules turned out to be even more efficient.
