Separable Relaxation for Nonconvex Quadratic Integer Programming: Integer Diagonalization Approach

We present in this paper an integer diagonalization approach for deriving new lower bounds for general quadratic integer programming problems. More specifically, we introduce a semiunimodular transformation in order to diagonalize a symmetric matrix and preserve integral property of the feasible set at the same time. Via the semiunimodular transformation, the resulting separable quadratic integer program is a relaxation of the nonseparable quadratic integer program. We further define the integer diagonalization dual problem to identify the best semiunimodular transformation and analyze some basic properties of the set of semiunimodular transformations for a rational symmetric matrix. In particular, we present a complete characterization of the set of all semiunimodular transformations for a nonsingular 2×2 symmetric matrix. We finally discuss Lagrangian relaxation and convex relaxation schemes for the resulting separable quadratic integer programming problem and compare the tightness of different relaxation schemes.     

Fuzzy Mathematical Programming: A Unified Approach Based On Fuzzy Relations

Fuzzy mathematical programming problems (FMP) form a subclass of decision - making problems where preferences between alternatives are described by means of objective function(s) defined on the set of alternatives. The formulation a FMP problem associated with the classical MP problem is presented. Then the concept of a feasible solution and optimal solution of FMP problem are defined. These concepts are based on generalized equality and inequality fuzzy relations. Among others we show that the class of all MP problems with (crisp) parameters can be naturally embedded into the class of FMP problems with fuzzy parameters. We also show that the feasible and optimal solutions being fuzzy sets are convex under some mild assumptions.     

Fuzzy Linear Programming Approach for Solving Fuzzy Transportation Problems with Transshipment

To find the fuzzy optimal solution of fuzzy transportation problems it is assumed that the direct route between a source and a destination is a minimum-cost route. However, in actual application, the minimum-cost route is not known a priori. In fact, the minimum-cost route from one source to another destination may well pass through another source first. In this paper, a new method is proposed to find the fuzzy optimal solution of fuzzy transportation problems with the following transshipment: (1) From a source to any another source, (2) from a destination to another destination, and (3) from a destination to any source. In the proposed method all the parameters are represented by trapezoidal fuzzy numbers. To illustrate the proposed method a fuzzy transportation problem with transshipment is solved. The proposed method is easy to understand and to apply for finding the fuzzy optimal solution of fuzzy transportation problems with transshipment occurring in real life situations.     

A Unified Monotonic Approach to Generalized Linear Fractional Programming

We present an efficient unified method for solving a wide class of generalized linear fractional programming problems. This class includes such problems as: optimizing (minimizing or maximizing) a pointwise maximum or pointwise minimum of a finite number of ratios of linear functions, optimizing a sum or product of such ratios, etc. – over a polytope. Our approach is based on the recently developed theory of monotonic optimization.     

求解多层线性规划的模糊规划法

本文用模糊集理论中的隶属函数描述多层线性规划的各层目标,在第一层给定最小满意水平下,通过求解相应层次的模糊规划来确定各层的最小满意度,从而最终得到问题的一个满意解。提出的方法只需求解一系列线性规划问题,具有较好的计算复杂性和可行性,最后的算例进一步验证了方法的有效性。     

具有模糊系数的模糊线性规划问题

本文考虑具有模糊系数的模糊线性规划问题中各系数的模糊可能性分布，而用指数（或线性）的隶属函数来描述，然后使用模糊数集上的实值函数，使模糊数在模型均值的意义下对应于一个实数，借此，将原问题公式化为一个普通线性规划。     

具有模糊变量的线性规划问题

讨论含模糊变量的线性规划问题，研究了其求解方法。利用新定义的模糊数序关系，将它转换成一个多目标线性规划问题，然后进一步转换成两层多目标线性规划问题，进而利用分层规划法求解。     

SICOpt: Solution Approach for Nonlinear Integer Stochastic Programming Problems

We propose a novel solution approach for the class of two-stage nonlinear integer stochastic programming models. These problems are characterized by large scale dimensions, as the number of constraints and variables depend on the number of realizations (scenarios) used to capture the underlying distributions of the random data. In addition, the integrality constraints on the decision variables make the solution process even much more difficult preventing the application of general purpose solvers. The proposed solution approach integrates the branch-and-bound framework with the interior point method. The main advantage of this choice is the effective exploitation of the specific structure exhibited by the different subproblems at each node of the search tree. A specifically designed warm start procedure and an early branching technique improve the overall efficiency. Our contribution is well founded from a theoretical point of view and is characterized by good computational efficiency, without any loss in terms of effectiveness. Some preliminary numerical results, obtained by solving a challenging real-life problem, prove the robustness and the efficiency of the proposed approach.     

基于多目标规划法的模糊线性回归分析

讨论输入、输出均为模糊数,回归系数为实数时的模糊线性回归分析。由于模糊最小二乘线性回归容易受异常值的影响,而最小一乘法能有效地降低回归模型的误差。为此,基于最小一乘法,建立多目标规划模型并将其转化为非线性规划问题进行求解,从而实现模糊线性回归模型的参数估计。最后,结合一个数值实例,验证和比较该方法的合理性和优越性。     

Stability and Regularization of Vector Problems of Integer Linear Programming

In this article we consider the problem of finding the Pareto set, and also the problem of lexicographic optimization. We study several types of stability, understood as preservation of certain properties of the efficient solution set under "small" changes of input data. The borders of such changes are ascertained. Necessary and sufficient conditions of stability are specified. A regularizing operator is proposed for transferring a probably unstable problem to a series of stable ones.     

Parametric Integer Programming Analysis: A Contraction Approach

An algorithm is presented for solving families of integer linear programming problems in which the problems are "related" by having identical objective coefficients and constraint matrix coefficients. The righthand-side constants have the form b + θd where b and d are conformable vectors and θ varies from zero to one.The approach consists primarily of solving the most relaxed problem (θ = 1) using cutting planes and then contracting the region of feasible integer solutions in such a manner that the current optimal integer solution is eliminated.The algorithm was applied to 1800 integer linear programming problems with reasonable success. Integer programming problems which have proved to be unsolvable using cutting planes have been solved by expanding the region of feasible integer solutions (θ = 1) and then contracting to the original region.     

A Reference Direction Algorithm for Solving Multiple Objective Integer Linear Programming Problems

In this paper, we propose a reference direction approach and an interactive algorithm to solve the general multiple objective integer linear programming problem. At each iteration, only one mixed integer linear programming problem is solved to find an (weak) efficient solution. Each intermediate solution is integer. The decision maker has to provide only the reference point at each iteration. No special software is required to implement the proposed algorithm. The algorithm is illustrated with an example.     

Integer Fuzzy Programming Approach in Bi-objective Selective Maintenance Allocation Problem

An attempt has been made to obtain a compromise allocation based on maximization of individual reliabilities of repairable and replaceable components with in the subsystems, using the information of failed and operational components and a non linear cost function with fixed budget. A solution algorithm of fuzzy programming technique is used to solve the Bi-Objective Selective Maintenance Allocation Problem (BSMAP). Also, the problem has been solved by two other suggested methods; “Weighted Criterion Technique” and “Desirability Function Technique”. A numerical example is also presented to illustrate the computational details.     

Reducing the number of variables in Integer and Linear Programming Problems

Computational difficulties in solving the Integer Programming Problems (IPP) are caused to a considerable degree by the number of variables. If the number of variables is small, then even NP-complete problems usually can be solved with a reasonable expenditure of effort.A procedure is developed for the analysis of large scale IPP with the aim of reducing the number of variables prior to starting the solution method. The procedure is based on comparing pairs of columns of the constraint matrix of the IPP. If a pair of columns thus compared meets certain conditions, then the IPP has an optimal solution, in which a variable corresponding to one of the columns in the pair is equal to zero. Corresponding theorems for Knapsack and Multidimensional Knapsack problems and for general IPP are presented. The procedure is extended to Linear and Mixed Integer Programming Problems. The presented results of computational experiments illustrate the efficiency of the developed procedure.     

A Branch and Bound Method for Solving Integer Separable Concave Problems

A branch and bound algorithm is proposed for solving integer separable concave problems. The method uses Lagrangian duality to obtain lower and upper bounds. We show that the dual program of a separable concave problem is a linear program. Moreover, we identify an excellent candidate to test on each region of the branch and we show an optimality sufficient condition for this candidate. Preliminary computational results are reported.     

Duality Theory in Fuzzy Linear Programming Problems with Fuzzy Coefficients

The concept of fuzzy scalar (inner) product that will be used in the fuzzy objective and inequality constraints of the fuzzy primal and dual linear programming problems with fuzzy coefficients is proposed in this paper. We also introduce a solution concept that is essentially similar to the notion of Pareto optimal solution in the multiobjective programming problems by imposing a partial ordering on the set of all fuzzy numbers. We then prove the weak and strong duality theorems for fuzzy linear programming problems with fuzzy coefficients.     

Computer-assisted Modelling and Analysis of Linear Programming Problems: Towards a Unified Framework

A framework for model formulation and analysis to support operationsand management of large-scale linear programs is developed fromthe combined capabilities of CAMPS and ANALYZE. Both the systemsare reviewed briefly and the interface which integrates thetwo systems is then described. The model formulation, matrixgeneration, and model management capability of CAMPS and thecomplementary model and solution analysis capability of ANALYZEare presented within a unified framework. Relevant generic functionsare highlighted, and an example is presented in detail to illustratethe level of integration achieved in the current prototype system.Some new results on discourse models and model management supportare given in a framework designed to move toward an ‘intelligent’system for linear programming modelling and analysis.