Primal-Dual Interior-Point Algorithms with Dynamic Step-Size Based on Kernel Functions for Linear Programming

In this paper, primal-dual interior-point algorithm with dynamic step size is implemented for linear programming （LP） problems. The algorithms are based on a few kernel functions, including both serf-regular functions and non-serf-regular ones. The dynamic step size is compared with fixed step size for the algorithms in inner iteration of Newton step. Numerical tests show that the algorithms with dynaraic step size are more efficient than those with fixed step size.

Randomized Objective Function Linear Programming in Risk Management

The traditional linear programming model is deterministic. The way that uncertainty is handled is to compute the range of optimality. After the optimal solution is obtained, typically by the simplex method, one considers the effect of varying each objective function coefficient, one at a time. This yields the range of optimality within which the decision variables remain constant. This sensitivity analysis is useful for helping the analyst get a sense for the problem. However, it is unrealistic because objective function coefficients tend not to stand still. They are typically profit contributions from products sold and are subject to randomly varying selling prices. In this paper, a realistic linear program is created for simultaneously randomizing the coefficients from any probability distribution. Furthermore, we present a novel approach for designing a copula of random objective function coefficients according to a specified rank correlation. The corresponding distribution of objective function values is created. This distribution is examined directly for central tendency, spread, skewness and extreme values for the purpose of risk analysis. This enables risk analysis and business analytics, emerging topics in education and preparation for the knowledge economy.

A new heuristic algorithm for general integer linear programming problems

A new heuristic algorithm is proposed for solving general integer linear programming problems. In the algorithm, the objective function hyperplane is used as a cutting plane, and then by introducing a special set of assistant sets, an efficient heuristic search for the solution to the integer linear program is carried out in the sets on the objective function hyperplane. A simple numerical example shows that the algorithm is efficient for some problems, and therefore, of practical interest.

Max-plus-linear model-based predictive control for constrained hybrid systems: linear programming solution

In this paper, a linear programming method is proposed to solve model predictive control for a class of hybrid systems. Firstly, using the （max, ＋） algebra, a typical subclass of hybrid systems called max-plus-linear （MPL） systems is obtained. And then, model predictive control （MPC） framework is extended to MPL systems. In general, the nonlinear optimization approach or extended linear complementarity problem （ELCP） were applied to solve the MPL-MPC optimization problem. A new optimization method based on canonical forms for max-min-plus-scaling （MMPS） functions （using the operations maximization, minimization, addition and scalar multiplication） with linear constraints on the inputs is presented. The proposed approach consists in solving several linear programming problems and is more efficient than nonlinear optimization. The validity of the algorithm is illustrated by an example.

A New Method to Evaluate Linear Programming Problem in Bipolar Single-Valued Neutrosophic Environment

A bipolar single-valued neutrosophic set can deal with the hesitation relevant to the information of any decision making problem in real life scenarios,where bipolar fuzzy sets may fail to handle those hesitation problems.In this study,we first develop a new method for solving linear programming problems based on bipolar singlevalued neutrosophic sets.Further,we apply the score function to transform bipolar single-valued neutrosophic problems into crisp linear programming problems.Moreover,we apply the proposed technique to solve fully bipolar single-valued neutrosophic linear programming problems with non-negative triangular bipolar single-valued neutrosophic numbers(TBSvNNs)and non-negative trapezoidal bipolar single-valued neutrosophic numbers(TrBSvNNs).

Solving the Binary Linear Programming Model in Polynomial Time

The paper presents a technique for solving the binary linear programming model in polynomial time. The general binary linear programming problem is transformed into a convex quadratic programming problem. The convex quadratic programming problem is then solved by interior point algorithms. This settles one of the open problems of whether P = NP or not. The worst case complexity of interior point algorithms for the convex quadratic problem is polynomial. It can also be shown that every liner integer problem can be converted into binary linear problem.

AN IMPROVEMENT ON UNCONSTRAINED CONVEX PROGRAMMING APPROACH TO LINEAR PROGRAMMING

For satate form linear gram as Fang and sao deined and approach which would find an optimal solution by solving an anconstrained convex dual programming.Thedual was construcied by applying an emropic peturbation and a simple Inequality Inz【z-1 for z】0n,In this paper,we suggest than a paperbation functiontake the place of Inx such that the new approdt has good numerical stability andhas all properties of the original

An Approach to Formulation of FNLP with Complex Piecewise Linear Membership Functions

Traditionally, extra binary variables are demanded to formulate a fuzzy nonlinear programming(FNLP) problem with piecewise linear membership functions(PLMFs). However, this kind of methodology usually suffers increasing computational burden associated with formulation and solution, particularly in the face of complex PLMFs. Motivated by these challenges, this contribution introduces a novel approach free of additional binary variables to formulate FNLP with complex PLMFs, leading to superior performance in reducing computational complexity as well as simplifying formulation. A depth discussion about the approach is conducted in this paper, along with a numerical case study to demonstrate its potential benefits.

Multistep Linear Programming Approaches for Decoding Low-Density Parity-Check Codes

The problem of improving the performance of linear programming（LP） decoding of low-density parity-check（LDPC） codes is considered in this paper.A multistep linear programming（MLP） algorithm was developed for decoding LDPC codes that includes a slight increase in computational complexity.The MLP decoder adaptively adds new constraints which are compatible with a selected check node to refine the results when an error is reported by the original LP decoder.The MLP decoder result is shown to have the maximum-likelihood（ML） certificate property.Simulations with moderate block length LDPC codes suggest that the MLP decoder gives better performance than both the original LP decoder and the conventional sum-product（SP） decoder.

The Optimal Conditions of the Linear Fractional Programming Problem with Constraint

In this article,the authors discuss the optimal conditions of the linear fractionalprogramming problem and prove that a locally optional solution is a globally optional solution and the locally optimal solution can be attained at a basic feasible solution withconstraint condition.

Solving the Interval-Valued Linear Fractional Programming Problem

This paper introduces an interval valued linear fractional programming problem (IVLFP). An IVLFP is a linear frac-tional programming problem with interval coefficients in the objective function. It is proved that we can convert an IVLFP to an optimization problem with interval valued objective function which its bounds are linear fractional functions. Also there is a discussion for the solutions of this kind of optimization problem.

Average number of iterations of some polynomial interior-point——Algorithms for linear programming

We study the behavior of some polynomial interior-point algorithms for solving random linear programming (LP) problems. We show that the average number of iterations of these algorithms, coupled with a finite termination technique, is bounded above by O( n1.5). The random LP problem is Todd’s probabilistic model with the standard Gauss distribution.

Determining Efficient Solutions of Multi-Objective Linear Fractional Programming Problems and Application

In this paper, a modified method to find the efficient solutions of multi-objective linear fractional programming (MOLFP) problems is presented. While some of the previously proposed methods provide only one efficient solution to the MOLFP problem, this modified method provides multiple efficient solutions to the problem. As a result, it provides the decision makers flexibility to choose a better option from alternatives according to their financial position and their level of satisfaction of objectives. A numerical example is provided to illustrate the modified method and also a real life oriented production problem is modeled and solved.

New Approach to Linear Stackelberg Problems with Multiple Leaders-followers

In this paper, we study linear static Stac kelberg problems with multiple leaders-followers in which each decision maker wi thin his group may or may not cooperate. An exact penalty function method is dev eloped. The duality gaps of the followers’ problems are appended to the leaders’ objective function with a penalty. The structure leads to the decomposition of the composite problem into a series of linear programmings leading to an efficie nt algorithm. We prove that local optimality is reached for an exact penalty fun ction and illustrate the method with three examples. The model in this paper ext ends the stackelberg leader-follower model.

求解LP问题的部分基变量算法

一般形式的线性规划问题在找不到基本可行解或对偶问题的基本可行解时,无法用传统的单纯形法或对偶单纯形法求解,即"两看一算"算法.为了解决这个问题,结合两种"两看一算"算法,提出了一种新的算法——部分基变量算法.该算法首先从部分基变量出发,由初等行变换将LP问题转化为准典式,然后由初等行变换找到全部可行基变量,最后用对偶单纯形法得到最优解.对算法的正确性和可行性进行了严格证明,提出算法的实现方式并举例进行了说明,对算法的特点进行了讨论.分析表明所提出的算法是实现线性规划问题求解的较为理想的算法.

基于局部密度的单类分类器LP改进算法

为了提高基于支持域的单类分类器识别率,提出将局部密度加入到分类器设计当中。在Campbe ll等的LP算法基础上,通过k近邻方法对每个样本点引入局部密度因子pi,重新刻画了原算法,使处于不同密度区的数据对分类器的作用不再被同等对待,高密度区的数据对分类超平面作用被强化,而低密度区的数据被削弱,结果使分类超平面自动靠近高密度区而提高了识别率。真实数据集上的实验结果表明,引入局部密度的D-LP算法其泛化性能较原算法有较大提高。

基于部分基变量的LP问题矩阵算法

基于部分基变量提出了LP问题的矩阵算法.该算法以最优基矩阵的一个充分必要条件为基础,首先将一个初始矩阵转化为右端项和检验数均满足要求的矩阵,再转化为检验数满足要求的基矩阵,最后转化为最优基矩阵.该算法具有使用范围广、计算规模小、计算过程简化、计算机易于实现的优势.矩阵算法的核心运算是求逆矩阵的运算,提出了矩阵算法的求逆问题,讨论并给出了求逆快速算法,该算法充分利用了矩阵算法迭代过程中提供的原来的逆矩阵的信息经过简单的变换得到新的逆矩阵,该算法比直接求逆法计算效率更高.

A hybrid algorithm based on ILP and genetic algorithm for time-aware test case prioritization

To solve the problem of time-awarc test case prioritization,a hybrid algorithm composed of integer linear programming and the genetic algorithm(ILP-GA)is proposed.First,the test case suite which cm maximize the number of covered program entities a d satisfy time constraints is selected by integer linea progamming.Secondly,the individual is encoded according to the cover matrices of entities,and the coverage rate of program entities is used as the fitness function and the genetic algorithm is used to prioritize the selected test cases.Five typical open source projects are selected as benchmark programs.Branch and method are selected as program entities,and time constraint percentages a e 25%and 75%.The experimental results show that the ILP-GA convergence has faster speed and better stability than ILP-additional and IP-total in most cases,which contributes to the detection of software defects as early as possible and reduces the software testing costs.

Szasz—Mirakjan—Durrmeyer算子的线性组合的加权Lp逼近

本文讨论了Ｓｚａｓｚ－Ｍｉｒａｋｊａｎ－Ｄｕｒｍｅｙｅｒ算子的线性组合算子加Ｊａｃｏｂｉ权的Ｌｐ（１〈ｐ≤∞）逼近问题，给出了逼近阶的特征刻划。

一类FLP模型在经济管理中的应用研究

文章分析了模糊线性规划模型的主要类型,介绍了约束模糊型模型的算法,通过实例探讨了约束模糊型线性规划在经济管理中的应用。