A sequential linear programming approach to solve mixed integer programming problems

The optimal operation of pumps in a large water supply system under time-of-use electricity rates is formulated as a mixed integer programming (MIP) problem. The problem is solved using an iterative linear programming (LP) scheme. The scheme is applied to an actual world problem, the City of Inglewood Water Supply System. Computational results are presented and termination criteria for the solution scheme are discussed.     

Spectral approach to linear programming bounds on codes

We give new proofs of asymptotic upper bounds of coding theory obtained within the frame of Delsarte’s linear programming method. The proofs rely on the analysis of eigenvectors of some finite-dimensional operators related to orthogonal polynomials. Examples of the method considered in the paper include binary codes, binary constant-weight codes, spherical codes, and codes in projective spaces.     

A linear programming approach to reasoning about probabilities

We continue our study, initiated in [9], of the following computational problem proposed by Nilsson: Several clauses (Boolean functions of several variables) are given, and for each clause the probability that the clause is true is specified. We are asked whether these probabilities are consistent. They are if there is a probability distribution on the truth assignments such that the probability of each clause is the measure of its satisfying set of assignments. Since this is a generalization of the satisfiability problem of predicate calculus, it is immediately NP-hard. In [9] we showed certain restricted cases of the problem to be NP-complete, and used the Ellipsoid Algorithm to show that a certain special case is in P. In this paper we use the Simplex method, column generation techniques, and variable-depth local search to derive an effective heuristic for the general problem. Experiments show that our heuristic performs successfully on instances with many dozens of variables and clauses. We also prove several interesting complexity results that answer open questions in [9] and motivate our approach.     

A linear programming approach to constrained robust predictivecontrol

A receding horizon predictive control algorithm for systems with model uncertainty and input constraints is developed. The proposed algorithm adopts the receding horizon dual-mode (i.e., free control moves and invariant set) paradigm. The approach is novel in that it provides a convenient way of combining predictions of control moves, which are optimal in the sense of worst case performance, with large target invariant sets. Thus, the proposed algorithm has a large stabilizable set of states corresponding to a cautious state feedback law while enjoying the good performance of a tightly tuned but robust control law. Unlike earlier approaches which are based on QP or semidefinite programming, here computational complexity is reduced through the use of LP     

新的线性遗传程序设计方法

受其他多种线性编码的遗传程序设计算法的启发,提出一种新的编码方式的遗传程序设计——符号遗传程序设计。该编码方式具有简单、无语法限制并且能够在不增加计算量的情况下将染色体翻译成多个表达式等特点。分析与实验表明该算法具有较高的效率和较强的稳定性。     

Taylor series approach to fuzzy multiobjective linear fractional programming

This paper presents the use of a Taylor series for fuzzy multiobjective linear fractional programming problems (FMOLFP). The Taylor series is a series expansion that a representation of a function. In the proposed approach, membership functions associated with each objective of fuzzy multiobjective linear fractional programming problem transformed by using a Taylor series are unified. Thus, the problem is reduced to a single objective. Practical applications and numerical examples are used in order to show the efficiency and superiority of the proposed approach.     

A separable programming approach to the linear complementarity problem

The linear complementarity problem (LCP) is reformulated as a nonconvex, separable program and solved with a general branch and bound algorithm. Unlike the principal alternatives, the approach offered here works for all linear complementarity problems regardless of their underlying matrix structure. In the reformulated version, the optimal value is known at the outset so a convergence check can be made at each iteration of the algorithm. This greatly improves its performance; in fact, a number of cases are given where immediate convergence can be expected.     

A weight space-based approach to fuzzy multiple-objective linear programming

In this paper, the effects of uncertainty on multiple-objective linear programming models are studied using the concepts of fuzzy set theory. The proposed interactive decision support system is based on the interactive exploration of the weight space. The comparative analysis of indifference regions on the various weight spaces (which vary according to intervals of values of the satisfaction degree of objective functions and constraints) enables to study the stability and evolution of the basis that correspond to the calculated efficient solutions with changes of some model parameters.     

A linear programming approach to shakedown analysis of structures

Two and three dimensional structures are dealt with, subjected to variable repeated loads, in order to establish a numerical tool for determining the load domain multiplier that gives rise to shakedown. The structure is made discrete by finite elements and the yield domain is linearized. By applying Bleich and Melan's theorem, two primal static formulations are found in linear programming, from which the relevant dual kinematic versions are obtained via duality properties.Numerical results are given at the end of the paper, together with some considerations about the numerical efficiency of the proposed formulations.     

An external reconstruction approach (ERA) to linear programming

An externally initiated optimum-searching procedure for large-scale LP optimization and design is presented. It appears to be potentially useful for LP problems characterized by large number of constraints relative to the number of variables. Although ERA (External Reconstruction Approach) still relies on LP subproblems (and their simplex-type solution procedures), its global philosophy is clearly nonsimplex and nonellipsoid in nature. In addition to its computational potential, ERA'S major advantages are: renewed flexibility, built-in parallelism, suitability to design and optimization, ability to handle mixed (both “soft” and “hard”) constraints. A numerical example is appended.     

The linear programming approach to the Randić index

Let G(k, n) be the set of simple graphs (i.e. without multiple edges or loops) that have n vertices and the minimum degree of vertices is k. The Randi? index of a graph G is: , where δ_u is the degree of vertex u and the summation extends over all edges (uv) of G. Using linear programming, we find the extremal graphs or give good bounds for this index when the number n_k of vertices of degree kis n?k+t, for 0tk and kn/2. We also prove that for n_kn?k, (kn/2) the minimum value of the Randi? index is attained for the graph .     

A linear programming approach to max-sum problem: a review

The max-sum labeling problem, defined as maximizing a sum of binary (i.e., pairwise) functions of discrete variables, is a general NP-hard optimization problem with many applications, such as computing the MAP configuration of a Markov random field. We review a not widely known approach to the problem, developed by Ukrainian researchers Schlesinger et al. in 1976, and show how it contributes to recent results, most importantly, those on the convex combination of trees and tree-reweighted max-product. In particular, we review Schlesinger et al.'s upper bound on the max-sum criterion, its minimization by equivalent transformations, its relation to the constraint satisfaction problem, the fact that this minimization is dual to a linear programming relaxation of the original problem, and the three kinds of consistency necessary for optimality of the upper bound. We revisit problems with Boolean variables and supermodular problems. We describe two algorithms for decreasing the upper bound. We present an example application for structural image analysis.     

基于AHP的模糊线性规划求解方法

对于基于AHP的多准则分析过程,存在不一致区间判断的复杂评估问题.通过有下限和上限的区间数表示元素之间的比较比率,构造模糊约束集合矩阵,引入模糊集的隶属度函数表示对各种优先权矢量的满意程度,利用线性规划求解具有最大满意度的优先权矢量,得出候选者的总体优先顺序,并举例说明了应用该方法的计算过程.     

A game-based approach to the teaching of object-oriented programming languages

Students often have difficulties when trying to understand the concepts of object-oriented programming (OOP). This paper presents a contribution to the teaching of OOP languages through a game-oriented approach based on the interaction with tangible user interfaces (TUIs). The use of a specific type of commercial distributed TUI (Sifteo cubes), in which several small physical devices have sensing, wireless communication and user-directed output capabilities, is applied to the teaching of the C# programming language, since the operation of these devices can be controlled by user programs written in C#. For our experiment, we selected a sample of students with a sufficient knowledge about procedural programming, which was divided into two groups: The first one had a standard introductory C# course, whereas the second one had an experimental C# course that included, in addition to the contents of the previous one, two demonstration programs that illustrated some OOP basic concepts using the TUI features. Finally, both groups completed two tests: a multiple-choice exam for evaluating the acquisition of basic OOP concepts and a C# programming exercise. The analysis of the results from the tests indicates that the group of students that attended the course including the TUI demos showed a higher interest level (i.e. they felt more motivated) during the course exposition than the one that attended the standard introductory C# course. Furthermore, the students from the experimental group achieved an overall better mark. Therefore, we can conclude that the technological contribution of Sifteo cubes – used as a distributed TUI by which OOP basic concepts are represented in a tangible and a visible way – to the teaching of the C# language has a positive influence on the learning of this language and such basic concepts.     

Application of fuzzy goal programming approach to multi-objective linear fractional inventory model

In this paper, we propose a model and solution approach for a multi-item inventory problem without shortages. The proposed model is formulated as a fractional multi-objective optimisation problem along with three constraints: budget constraint, space constraint and budgetary constraint on ordering cost of each item. The proposed inventory model becomes a multiple criteria decision-making (MCDM) problem in fuzzy environment. This model is solved by multi-objective fuzzy goal programming (MOFGP) approach. A numerical example is given to illustrate the proposed model.     

A linear programming approach for the weighted graph matchingproblem

A linear programming (LP) approach is proposed for the weighted graph matching problem. A linear program is obtained by formulating the graph matching problem in L₁ norm and then transforming the resulting quadratic optimization problem to a linear one. The linear program is solved using a simplex-based algorithm. Then, approximate 0-1 integer solutions are obtained by applying the Hungarian method on the real solutions of the linear program. The complexity of the proposed algorithm is polynomial time, and it is O(n ⁶L) for matching graphs of size n. The developed algorithm is compared to two other algorithms. One is based on an eigendecomposition approach and the other on a symmetric polynomial transform. Experimental results showed that the LP approach is superior in matching graphs than both other methods     

Decision-making with uncertain data: Bayesian linear programming approach

This paper deals with decision making in a real time optimization context under uncertain data by linking Bayesian networks (BN) techniques (for uncertainties modeling) and linear programming (LP, for optimization scheme) into a single framework. It is supposed that some external events sensed in real time are susceptible to give relevant information about data. BN consists in graphical representation of probabilistic relationship between variables of a knowledge system and so permit to take into account uncertainty in an expert system by bringing together the classical artificial intelligence (AI) approach and statistics approach. They will be used to estimate numerical values of parameters subjected to the influence of random events for a linear programming program that perform optimization process in order to select optimal values of decision variables of a certain real time decision-making system.