An Interval Linear Tolerance Problem

This paper is concerned with a tolerance problem for an interval linear system A x = b requiring inner estimation of the admissible solution set {x ⁿ | (A A)(Ax b)} formed by vectors x for which the product Ax remains within b for any possible A A. Methods for verifying the emptiness and nonemptiness of admissible solution sets are developed. Formulas for the dimensions of the interval solution of a tolerance problem with known center are derived.     

Efficient Interval Linear Equality Solving in Constraint Logic Programming

Existing interval constraint logic programming languages, such as BNR Prolog, work under the framework of interval narrowing and are deficient in solving systems of linear constraints over real numbers, which constitute an important class of problems in engineering and other applications. In this paper, we suggest to separate linear equality constraint solving from inequality and non-linear constraint solving. The implementation of an efficient interval linear constraint solver, which is based on the preconditioned interval Gauss-Seidel method, is proposed. We show how the solver can be adapted to incremental execution and incorporated into a constraint logic programming language already equipped with a non-linear solver based on interval narrowing. The two solvers share common interval variables, interact and cooperate in a round-robin fashion during computation, resulting in an efficient interval constraint arithmetic language CIAL. The CIAL prototypes, based on CLP(R), are constructed and compared favorably against several major interval constraint logic programming languages.     

基于Matlab的线性规划问题求解

线性规划是运筹学中研究较早、发展较快、应用广泛、方法成熟的一个重要分支,它是辅助人们进行科学管理的一种重要的数学方法.文章首先介绍了线性规划的基本概念及标准形式,着重讨论了线性规划问题的三种常用解法:单纯形法、直接搜索法以及遗传算法,最后在Matlab R2009a环境下进行了仿真.通过结果可以看出,用Matlab求解线性规划问题,可以避免手工的烦琐计算,大大地提高工作效率和结果的准确性.     

求解SAT问题的线性半定规划算法

将线性半定规划应用到SAT问题的求解过程中。首先将SAT实例转化为整数规划问题,然后松弛为线性规划模型,最后再转化为一般的线性半定规划模型去求解。用SDPA-M软件求解线性半定规划问题后,规定了如何根据目标函数值去判定SAT实例和当CNF公式可满足时如何根据最优指派的概率X^＊i（i=1,…,n）去进行变元赋值,以期求得该公式的可满足指派。上述算法不仅可以判定SAT问题,而且对于符合算法规定可满足的CNF公式皆可给出一个可满足指派。求解SAT问题的线性半定规划算法在文章中被描述并被给予相应算例。     

Inverse Problem of the Interval Linear System of Equations

Given a nonsingular central matrix , a central vector and a prescribed interval solution vector , it is required to find the maximum allowable deviation or so that the solution of the interval linear system is contained in . Special cases for and are considered and bounds on the entries of and are obtained either in a closed form, whenever possible, or via solving a specially designed constrained optimization problem. Received: August 25, 1997; revised February 20, 1999     

Saddle Point Optimality Criteria of Interval Valued Non-Linear Programming Problem

The present paper aims to develop the Kuhn-Tucker and Fritz John criteria for saddle point optimality of interval-valued nonlinear programming problem. To achieve the study objective, we have proposed the definition of minimizer and maximizer of an interval-valued non-linear programming problem. Also, we have introduced the interval-valued Fritz-John and Kuhn Tucker saddle point problems. After that, we have established both the necessary and sufficient optimality conditions of an interval-valued non-linear minimization problem. Next, we have shown that both the saddle point conditions (Fritz-John and Kuhn-Tucker) are sufficient without any convexity requirements. Then with the convexity requirements, we have established that these saddle point optimality criteria are the necessary conditions for optimality of an interval-valued non-linear programming with real-valued constraints. Here, all the results are derived with the help of interval order relations. Finally, we illustrate all the results with the help of a numerical example.     

一种结合多目标免疫算法和线性规划的双行设备布局方法

设备布局对于提高生产效率和降低运营成本具有重要意义. 本文针对半导体加工制造中常见的双行设备布局问题, 提出了一种结合多目标免疫算法和线性规划的双行设备布局方法来同时优化物料流成本和布局面积两个目标. 首先, 建立了问题的混合整数规划模型;其次, 针对问题既含有组合方面(机器排序)又含有连续方面(机器精确位置)的特点, 分别设计了一种多目标免疫算法来获取非支配的机器排序集合, 提出了一种基于线性规划的方法来构造任一非支配机器排序对应的连续的非支配解集;最后, 由所有连续的非支配解来构造最后Pareto解. 实验结果表明, 该方法对于小规模问题能获得最优Pareto解, 对于大规模问题能够获得具有良好分布性的Pareto解且其质量远好于NSGA-II和精确算法获得的解.     

Algebraic Approach in the "Outer Problem" for Interval Linear Equations

The subject of our work is the classical "outer" problem for the interval linear algebraic System Ax = b with the square interval matrix A: find "outer" coordinate-wise estimates of the united solution set formed by all solutions to the point systems Ax = b with A A and b b. The purpose of this work is to advance a new algebraic approach to the formulated problem, in which it reduces to solving one noninterval (point) equation in the Euclidean space of double dimension. We construct a specialized algorithm (subdifferential Newton method) that implements the new approach, then present results of the numerical tests with it. These results demonstrate that the proposed algebraic approach combines unique computational efficiency with high quality enclosures of the solution set.     

一种线性规划问题的自动化建模方法研究

提出了一种基于自然语言理解及XML的线性规划问题自动化建模方法,并给出实例。实践证明,该方法具有灵活性、通用性及可行性。     

R~m凸域包含与相交性判定的一个线性规划算法

该文提出了凸域包含与相交性判定的一个新的基于线性规划的分析型算法。该算法具有通用性，适用于任意维欧氏空间凸域的包含与相交性判定；且由于利用了成熟的线性规划方法，效率亦较高，文中研究了凸域包含与相交问题的两种线性规划表述形式，并考察了它们之间的关系，给出了算法的实现策略。     

An Integer Linear Programming approach to the single and bi-objective Next Release Problem

ContextThe Next Release Problem involves determining the set of requirements to implement in the next release of a software project. When the problem was first formulated in 2001, Integer Linear Programming, an exact method, was found to be impractical because of large execution times. Since then, the problem has mainly been addressed by employing metaheuristic techniques.ObjectiveIn this paper, we investigate if the single-objective and bi-objective Next Release Problem can be solved exactly and how to better approximate the results when exact resolution is costly.MethodsWe revisit Integer Linear Programming for the single-objective version of the problem. In addition, we integrate it within the Epsilon-constraint method to address the bi-objective problem. We also investigate how the Pareto front of the bi-objective problem can be approximated through an anytime deterministic Integer Linear Programming-based algorithm when results are required within strict runtime constraints. Comparisons are carried out against NSGA-II. Experiments are performed on a combination of synthetic and real-world datasets.FindingsWe show that a modern Integer Linear Programming solver is now a viable method for this problem. Large single objective instances and small bi-objective instances can be solved exactly very quickly. On large bi-objective instances, execution times can be significant when calculating the complete Pareto front. However, good approximations can be found effectively.ConclusionThis study suggests that (1) approximation algorithms can be discarded in favor of the exact method for the single-objective instances and small bi-objective instances, (2) the Integer Linear Programming-based approximate algorithm outperforms the NSGA-II genetic approach on large bi-objective instances, and (3) the run times for both methods are low enough to be used in real-world situations.     

Bi-Objective Optimization Method for Horizontal Fragmentation Problem in Relational Data Warehouses as a Linear Programming Problem

ABSTRACT

In this work, we relied on a particular exact method to solve NP-Hard problem of determining a horizontal fragmentation scheme in relational data warehouses. The method used is that of linear programming which is distinguished by other methods by the existence of practical methods that facilitate the resolution of problems that may be described in linear form. We quote the Simplex method and the interior points. To meet the linearity of the objective function and constraints, we used initially “De Morgan” theorem, which is based on properties of sets to transform and optimize decision queries, from any form to a linear one.

In addition to designing and solving the selection problem of horizontal fragmentation technique, we considered the problem in two simultaneous objectives, namely: the number of Inputs/Outputs needed to run the global workload, and number of fragments generated to identify the best solutions compared to the concept of Pareto dominance.

In addition, to carry out our work, we used the Benchmark APB1 invoked by a workload, to achieve satisfactory results.     

An Integer Linear Programming Problem with Multi-Criteria and Multi-Constraint Levels: a Branch-and-Partition Algorithm

In this paper, we propose a branch-and-partition algorithm to solve the integer linear programming problem with multi-criteria and multi-constraint levels (MC-ILP). The procedure begins with the relaxation problem that is formed by ignoring the integer restrictions. In this branch-and-partition procedure, an MC linear programming problem is adopted by adding a restriction according to a basic decision variable that is not integer. Then the MC-simplex method is applied to locate the set of all potential solutions over possible changes of the objective coefficient parameter and the constraint parameter for a regular MC linear programming problem. We use parameter partition to divide the (λ, γ) space for integer solutions of MC problem. The branch-and-partition procedure terminates when every potential basis for the relaxation problem is a potential basis for the MC-ILP problem. A numerical example is used to demonstrate the proposed algorithm in solving the MC-ILP problems. The comparison study and discussion on the applicability of the proposed method are also provided.     

Learning Linear and Nonlinear PCA with Linear Programming

An SVM-like framework provides a novel way to learn linear principal component analysis (PCA). Actually it is a weighted PCA and leads to a semi-definite optimization problem (SDP). In this paper, we learn linear and nonlinear PCA with linear programming problems, which are easy to be solved and can obtain the unique global solution. Moreover, two algorithms for learning linear and nonlinear PCA are constructed, and all principal components can be obtained. To verify the performance of the proposed method, a series of experiments on artificial datasets and UCI benchmark datasets are accomplished. Simulation results demonstrate that the proposed method can compete with or outperform the standard PCA and kernel PCA (KPCA) in generalization ability but with much less memory and time consuming.     

Dual Regularization, Marginal (Repeated) Values of the Linear Programming Problem

Regularizing transformations of the linear programming problem were proposed and used to construct the regularizing family for the dual problem. Repeated dual regularization becomes possible at that. The repeated marginal value for linear programming was introduced and constructively calculated: the marginal value for the Leontief balance model was calculated.     

A Linear Two-Stage Stochastic Programming Problem with Quantile Criterion: Its Discrete Approximation

Algorithms for solving a linear two-stage stochastic programming problem with quantile criterion are designed. They are based on the reduction of the initial nonlinear problem to a sequence of linear programming problems. The first algorithm applies the simplex and Monte Carlo methods sequentially, whereas the second utilizes the simplex method and varies the confidence set. Their advantages are demonstrated by forming the budget of a hospital.     

带多项式量级约束条件的多商品流BWTSP线性规划

黑白旅行商问题(BWTSP)是近年来出现的新NP-难解问题,根据图中边是否对称可以分为无向BWTSP和有向BWTSP两种.现有无向BWTSP的Ghiani线性规划中约束条件数目为指数多个.权值阈值等于+∞的有向BWTSP通过转换为RATSP问题而存在多项式个约束条件的线性规划.针对一般的有向BWTSP,提出了一种仅包含多项式个约束条件的新线性规划.其基本思想是首先将有向BWTSP问题归约为ATSP问题,然后利用ATSP包含n(n+4)个约束条件的Finke-Claus-Gunn线性规划,通过定义剩余和消耗基数商品流,分析了环路上的弧应满足的约束条件,并证明这些n\\+2+2|W|的约束条件即是基数约束条件;类似地通过定义剩余和消耗权值商品流,得到n\\+2+n+2|B|个权值约束条件. 最终得到原始问题仅包含3n\\+2+7n个约束条件的线性规划.由于无向BWTSP问题和权值阈值等于+∞的有向BWTSP均是一般有向BWTSP的特例,故此结果对于它们同样有效.     

Concurrent Programming Technologies and Techniques

Intensive use of computer experiments in modern science introduces qualitative changes into experimental resources. This implies the change in techniques used to solve relevant problems. An analysis of technological chains (from the problem statement to its solution) shows that often a particular problem can be solved in a variety of ways with the use of modern multiprocessor computers, which are also called supercomputers. The multiplicity of approaches to solving a problem requires that researches possess certain skills in using supercomputers. It is difficult for novice users of multiprocessor computers to find bearings when developing software for solving applied problems. The practice shows that main difficulties reveal themselves when it is required to develop portable and efficient parallel software. This is because tools that facilitate the development and provide full access to debugging information have yet to be elaborated. Actually, the problem is in the absence of standards for development and debugging tools for supercomputers, which is explained by the fact that computer science is yet young. For the same reason, no logically complete basic texts for concurrent programming courses for novices are available. On the basis of Russian-language literature, an attempt is made at setting up beacons that mark certain common and promising technologies in using supercomputers. The emphasis is made on problems encountered by programmers when solving applied problems with the use of supercomputers. The development of multiprocessor computers is closely related to concurrent programming technologies, both universal and oriented to specific supercomputer architectures. By programming technology, i.e., by memory management, we mean the use of tools designed for managing a particular computer system. It should be noted that when developing software for supercomputers (both management software and programs for solving applied problems), one must pay special attention to programming technique, i.e., to designing the logical architecture of a program. This implies the development and extending parallelizing algorithms, which enhances the efficiency of execution on multiprocessor computers. This review was compiled on the basis of publications in Russian journals and in the Russian Internet zone.     

分片线性规划及应用

提出通过分片线性逼近和分片线性规划,将非线性优化问题转化为一系列的线性规划进行求解的方法。讨论了分片线性规划的性质,证明了分片线性规划问题可以通过有限次线性规划得到求解,同时,给出了分片线性规划问题局部最优解的充要条件,并基于此构造了求解分片线性规划问题的下降算法。该算法与自适应链接超平面模型相结合,成功地对离心式冷水机组的工作点进行了优化。通过优化,机组的能耗比之当前工作点有了明显的下降,表明通过分片线性规划求解非线性优化问题的有效性。