Mixed-integer linear programming approach for global discrete sizing optimization of frame structures

This paper focuses on discrete sizing optimization of frame structures using commercial profile catalogs. The optimization problem is formulated as a mixed-integer linear programming (MILP) problem by including the equations of structural analysis as constraints. The internal forces of the members are taken as continuous state variables. Binary variables are used for choosing the member profiles from a catalog. Both the displacement and stress constraints are formulated such that for each member limit values can be imposed at predefined locations along the member. A valuable feature of the formulation, lacking in most contemporary approaches, is that global optimality of the solution is guaranteed by solving the MILP using branch-and-bound techniques. The method is applied to three design problems: a portal frame, a two-story frame with three load cases and a multiple-bay multiple-story frame. Performance profiles are determined to compare the MILP reformulation method with a genetic algorithm.     

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.     

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.     

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     

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 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.     

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 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     

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.     

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.     

A neural network approach for solving linear bilevel programming problem

A novel neural network approach is proposed for solving linear bilevel programming problem. The proposed neural network is proved to be Lyapunov stable and capable of generating optimal solution to the linear bilevel programming problem. The numerical result shows that the neural network approach is feasible and efficient.     

Multi-media instructional approach to teaching linear programming

This paper describes different strategies employed in converting a lecture-oriented mathematical programming course to a Personalized Self-Paced Instructional (PSI) format. This is an elective course for students in science, engineering and management. A multi media instructional approach is used in the PSI system which combines traditional lectures, self-paced and individualized learning assisted by interactive computer programs and video taped instructional materials. This unique PSI system for mathematical programming provides maximum learning opportunity and flexibility to students. The author's experiences with the PSI system and the students' evaluation of the self-paced system are also discussed.     

A perturbation approach for a type of inverse linear programming problems

We consider an inverse linear programming (LP) problem in which the parameters in both the objective function and the constraint set of a given LP problem need to be adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a linear complementarity constrained minimization problem. With the help of the smoothed Fischer–Burmeister function, we propose a perturbation approach to solve the inverse problem and demonstrate its global convergence. An inexact Newton method is constructed to solve the perturbed problem and numerical results are reported to show the effectiveness of the approach.     

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

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

A Hybrid approach for integer programming combining genetic algorithms, linear programming and ordinal optimization

Hybrid methods are promising tools in integer programming, as they combine the best features of different methods in a complementary fashion. This paper presents such a framework, integrating the notions of genetic algorithm, linear programming, and ordinal optimization in an effort to shorten computation times for large and/or difficult integer programming problems. Capitalizing on the central idea of ordinal optimization and on the learning capability of genetic algorithms to quickly generate good feasible solutions, and then using linear programming to solve the problem that results from fixing the integer part of the solution, one may be able to obtain solutions that are close to optimal. Indeed ordinal optimization guarantees the quality of the solutions found. Numerical testing on a real-life complex scheduling problem demonstrates the effectiveness and efficiency of this approach.     

A linear programming approach for multivariable feedback control with inequality constraints

A multivariable control scheme which explicitly includes inequality constraints on the state, control and output variables is developed using a linear programming (LP) formulation. A suboptimal feedback control policy results since the LP calculations are repeated at each sampling instant. A number of important properties related to the LP control problem are obtained from a theoretical analysis. Simulation results illustrate that the on-line computational requirements are modest and that the new LP approach compares favourably with existing methods such as optimal feedback control     

A heuristic approach for identification of redundant constraints in linear programming models

Linear programming (LP) is one of the most important techniques used in modelling and solving practical optimization problems that arise in industry, commerce, and management. When formulating an LP model, systems analysts and researchers often include all possible constraints although some of them may not be binding at the optimal solution. The presence of redundant constraints does not alter the optimum solution(s), but may consume extra computational effort. Many researchers have proposed algorithms for identifying the redundant constraints in LP models. Here we propose a heuristic approach using an intercept matrix to identify redundant constraints prior to the start of the solution process. An interesting observation of the proposal technique is that the tendency of variables to pop in and pop out of the basis is eradicated after eliminating the redundancies. The eradication of pop-in and pop-out substantially reduces the number of iterations. A significant reduction in the computational effort is achieved for LP problems of different sizes.     

A linear genetic programming approach for the prediction of solar global radiation

In this article, the linear genetic programming (LGP) is utilized to predict the solar global radiation. The solar radiation is formulated in terms of several climatological and meteorological parameters. Comprehensive databases containing monthly data collected for 6 years (1995–2000) in two nominal cities in Iran are used to develop LGP-based models. Separate models are established for each city. To verify the performance of the proposed models, they are applied to estimate the solar global radiation of test data of database. The contribution of the parameters affecting the solar radiation is evaluated through a sensitivity analysis. The results indicate that the LGP models give precise estimations of the solar global radiation and significantly outperform traditional angstrom’s model.