Software package for large-scale 0–1 linear programming on Unix system: GUB technique

Recently, a multiple criteria decision making (MCDM) has been well established as a practical approach to seek a satisfactory solution to a decision making problem. Linear programming (LP) is one of the most widely used OR/MS/IE techniques for solving MCDM problems. In the realistic decision making problems, many LP problems are involved a large number of 0–1 decision variables and a special type of system structures. So much kind of the large-scale 0–1 LP problems are simply too large fit into a microcomputer/workstation.

In this paper, we develop a software package micro 0–1LP(GUB) for solving LP problems with a generalized upper bounding (GUB) structure as large-scale 0–1LP problems on UNIX systems. From the views of the computational experience and storage requirement, micro 0–1LP(GUB) using the C programming language is implemented an efficient method in which the GUB structure would be effectively handled.

As a real-world large-scale 0–1LP problem with the GUB structures by the micro 0–1LP (GUB) software package developed here, we demonstrate an optimization problem of system reliability for selecting the allocating the components on an UNIX system, Sanyo/Icon MPS 020.     

Interactive multiple objective linear programming system implemented on a microcomputer

Linear programming is one of the most widely used Operations Research/Management Science techniques. Recently, multiple objective decision making has been well established as a practical approach to seek a satisfactory solution to a decision making problem. Much attention has been focused on a microcomputer as an economical management tool.

In this paper we propose an interactive goal attainment method using the eigenvector algorithm for solving a multiple objective linear programming problem interactively on microcomputers. In the software package Micro-LPS based on the method proposed, we design a conversational and user-friendly system in which the user commands are involved.     

Algorithms for solving large-scale 0–1 goal programming and its application to reliability optimization problem

Goal programming(GP) is one of the most widely used Operations Research/Management Science/Industrial Engineering techniques for solving multiple criteria decision making (MCD M) problems. In the realistic decision making problems, many GP problems are involved a large number of 0–1 decision variables and a special type of system structures.

Inthis paper, we develop a computational algorithm for solving 0–1 goal programming with a generalized upper bounding (GUB) structures. From the views of the computational experience and storage requirement, we implemented an efficient software package for UN IX workstations in which we called it micro 0–1 GP(GUB). In the micro 0–1 GP(GUB) developed here, the GUB structures would be effectively handled and we designed user-friendly GP data entry subsystem.

As a real-world 0–1 goal programming problem with the GUB structures, we demonstrate an optimization problem of system reliability for allocating redundant units by the micro 0–1 GP(GUB) software package on an UN IX system.     

Solving mixed integer programming production planning problems with setups by shadow price information

Algorithms developed to solve linear programming (LP) problems and advances in computer speed have made large-scale LP problems solvable in time for implementation. Solving an LP is relatively easier than solving an MIP for modern production planning problems. In this study, we propose a heuristic iterative algorithm between LP solution phases and setup decision computations for solving these difficult MIP production planning problems. By utilizing the shadow price information provided by the LP solution of the previous iteration, the setup decision computation converts an MIP problem into an LP problem, which can be efficiently solved in the current iteration. Extensive experiments show that the proposed heuristic algorithm performs well.     

Optimally solving Markov decision processes with total expected discounted reward function: Linear programming revisited

We compare the computational performance of linear programming (LP) and the policy iteration algorithm (PIA) for solving discrete-time infinite-horizon Markov decision process (MDP) models with total expected discounted reward. We use randomly generated test problems as well as a real-life health-care problem to empirically show that, unlike previously reported, barrier methods for LP provide a viable tool for optimally solving such MDPs. The dimensions of comparison include transition probability matrix structure, state and action size, and the LP solution method.     

Hybrid-LP: Finding advanced starting points for simplex,and pivoting LP methods

The simplex method has proven its efficiency in practice for linear programming (LP) problems of various types and sizes. However, its theoretical worst-case complexity in addition to its poor performance for very large-scale LP problems has driven researchers to develop alternative methods for LP problems. In this paper, we develop the hybrid-LP; a two-phase approach for solving LP problems. Rather than following a path of extreme points on the boundary of the feasible region as in the simplex method, the first phase of the hybrid-LP moves through the interior of the feasible region to obtain an improved and advanced initial basic feasible solution (BFS). Then, in the second phase simplex or other LP methods can be used to find the optimal solution.     

Interactive group decision process with evolutionary database

This paper presents interactive procedures for solving a multiple criteria group decision making (MCGDM) problem with incomplete information when multiple decision makers are involved. It is difficult for group members participating in the decision making process to articulate their preferences with cardinal values. Therefore, we represent their preferences with utility ranges obtained by solving linear programming (LP) problems with incompletely specified information, find conflicting judgments, if any in their specified information, and suggest interaction processes to help the group reach a consensus. This paper will provide an algorithmic basis for a normative and interactive knowledge based group decision support system.     

线性规划软件包GLPK的分析与应用

GLPK是一个求解大规模的线性规划问题(LP)、混合整数规划问题(MIP)以及相关问题的自由软件包。该文分析TGLPK的算法结构与数值计算等多方面的实现技术，并应用于解决NP-hard的调度问题。数值结果表明GLPK是研究LP和MIP问题强有力的工具。     

Symmetric approximate linear programming for factored MDPs with application to constrained problems

A weakness of classical Markov decision processes (MDPs) is that they scale very poorly due to the flat state-space representation. Factored MDPs address this representational problem by exploiting problem structure to specify the transition and reward functions of an MDP in a compact manner. However, in general, solutions to factored MDPs do not retain the structure and compactness of the problem representation, forcing approximate solutions, with approximate linear programming (ALP) emerging as a promising MDP-approximation technique. To date, most ALP work has focused on the primal-LP formulation, while the dual LP, which forms the basis for solving constrained Markov problems, has received much less attention. We show that a straightforward linear approximation of the dual optimization variables is problematic, because some of the required computations cannot be carried out efficiently. Nonetheless, we develop a composite approach that symmetrically approximates the primal and dual optimization variables (effectively approximating both the objective function and the feasible region of the LP), leading to a formulation that is computationally feasible and suitable for solving constrained MDPs. We empirically show that this new ALP formulation also performs well on unconstrained problems.      

An advanced start algorithm for all-integer programming

In this paper, we present an all-integer cutting plane technique called the Advanced Start Algorithm (ASA), for solving the all-integer (otherwise linear) programming problem (IP). We develop a good advanced primal-infeasible start based on the optimal solution to the LP relaxation, and use a two-stage dual/primal algorithm to obtain the optimal solution to (IP). We illustrate the operation of the ASA on three small problems, and exhibit computational results on a set of standard test problems.     

A Surrogate cutting plane algorithm for all-integer programming

In this paper we present an all-integer cutting plane technique called the surrogate cutting plane algorithm (SCPA), for solving the all-integer (otherwise linear) programming problem. We develop and solve a smaller surrogate problem based on the solution of the LP relaxation, and thereby speed convergence to the optimal solution of the original problem. We exhibit the operation of the SCPA on three small example problems, and discuss computational results on a set of standard test problems.     

Computer-based algorithms for multiple criteria and multiple constraint level integer linear programming

This paper investigates algorithm development and implementation for multicriteria and multiconstraint level (MC²) integer linear programming problems. MC² linear programming is an extension of linear programming (LP) and multiple criteria (MC) linear programming and a promising computer-aided decision technique in many applications. Here, we present two of the most recent techniques, the MC² branch-and-partition algorithm and the MC² branch-and-bound algorithm, to solve MC² integer linear programs. We describe the design and implementation of a C++ software library for these approaches, and then conduct a comparison study in terms of computational efficiency and complexity through a series of empirical tests.     

Solving fuzzy assembly-line balancing problem with genetic algorithms

Assembly-line balancing problem is known as one of difficult combinatorial optimization problems. This problem has been solved with linear programming, dynamic programming approaches, but unfortunately these approaches do not lead to efficient algorithms. Recently, genetic algorithm has been recognized as an efficient and usefull procedure for solving large and hard combinatorial optimization problems, such as scheduling problems, travelling salesman problems, transportation problems, and so on. Fuzzy sets theory is frequently used to represent uncertainty of information. In this paper, to treat the data of real-world problems we use a fuzzy number to represent the processing time and show that we can get a good performance in solving this problem using genetic algorithms.     

Optimized load planning for motorail transportation

This paper studies a real-world problem arising in the area of motorail transportation. The considered problem deals with the loading of cars and motorcycles onto motorail wagons under realistic technical and legal constraints. The load planning problem, introduced as motorail transportation problem (MTP), occurs during the booking process and afterwards during the loading process at motorail terminals. Optimization based decision support is highly valuable due to the combinatorial nature of these problems. In practical applications, the fast generation of good solutions is essential. Previous model formulations in literature reveal considerable optimality gaps in real-world instances. Hence, we propose and evaluate two novel integer linear programming formulations of the MTP. The first formulation is a simplified reformulation of the original problem, uses less variables and provides a tighter LP relaxation. The second model is a column-generation formulation of the reformulated model which is solved using branch-and-price. Both novel model formulations are compared and evaluated on the basis of real-world data sets and considerably outperform previous approaches in terms of solution quality and speed.     

Control applications of nonlinear convex programming

Since 1984 there has been a concentrated effort to develop efficient interior-point methods for linear programming (LP). In the last few years researchers have begun to appreciate a very important property of these interior-point methods (beyond their efficiency for LP): they extend gracefully to nonlinear convex optimization problems. New interior-point algorithms for problem classes such as semidefinite programming (SDP) or second-order cone programming (SOCP) are now approaching the extreme efficiency of modern linear programming codes. In this paper we discuss three examples of areas of control where our ability to efficiently solve nonlinear convex optimization problems opens up new applications. In the first example we show how SOCP can be used to solve robust open-loop optimal control problems. In the second example, we show how SOCP can be used to simultaneously design the set-point and feedback gains for a controller, and compare this method with the more standard approach. Our final application concerns analysis and synthesis via linear matrix inequalities and SDP.     

A new approach to the solution of the l1 controlproblem: the scaled-Q method

We explore an approach for solving multiple input-multiple output (MIMO) l₁ optimal control problems. This approach, which we refer to as the scaled-Q approach, is introduced to alleviate many of the difficulties facing the numerical solution of optimal l₁ control problems. In particular, the computations of multivariable zeros and their directions are no longer required. The scaled-Q method also avoids the pole-zero cancellation difficulties that existing methods based on zero-interpolation face when attempting to recover the optimal controller from an optimal closed-loop map. Because the scaled-Q approach is based on solving a regularized auxiliary problem for which the solution is always guaranteed to exist, it can be used no matter where the system zeros are (including the stability boundary). Upper and lower bounds that converge to the optimal cost are provided, and all solutions are based on finite dimensional linear programming for which efficient software exists     

Modelling a nationwide crop planning problem using a multiple criteria decision making tool

Multiple criteria decision making (MCDM) tools have been used in recent years to solve a wide variety of problems. In this paper we consider a nation-wide crop-planning problem and show how an MCDM tool can be used efficiently and effectively for these types of problems. A crop-planning problem is usually formulated as a single objective linear programming model. The objective is either the maximization of return from cultivated land or the minimization of cost of cultivation. This type of problem, however, normally involves more than one goal. We thus formulate a crop-planning problem as a goal program (an MCDM tool) and discuss the importance of three different goals for a case problem. We solve the goal program with a real world data set, and compare the solution with that of linear program. We argue that the goal program provides better insights to the problem and thus allows better decision support.     

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.     

A neural network model for monotone linear asymmetric variationalinequalities

A linear variational inequality is a uniform approach for some important problems in optimization and equilibrium problems. We give a neural network model for solving asymmetric linear variational inequalities. The model is based on a simple projection and contraction method. Computer simulation is performed for linear programming (LP) and linear complementarity problems (LCP). The test results for the LP problem demonstrate that our model converges significantly faster than the three existing neural network models examined in a comparative study paper.     

Model, solution concept, and Kth-best algorithm for linear trilevel programming

Trilevel programming refers to hierarchical optimization problems in which the top-level, middle-level, and bottom-level decision entities all attempt to optimize their individual objectives, but are impacted by the actions and partial control exercised by decision entities located at other levels. To solve this complex problem, in this study first we propose the use of a general linear trilevel programming (LTLP) subsequently, we develop a trilevel Kth-best algorithm to solve LTLP problems. A user-friendly trilevel decision support tool is also developed. A case study further illustrates the effectiveness of the proposed method.