Linear programming software tools on UNIX System

Linear programming(LP) is one of the most widely used Operations Research/Management Science/Industrial Engineering techniques. Recently, multiple criteria decision making or multiple objective linear programming has been well established as a practical approach to seeking satisfactory solutions to real-world decision problems.

In this paper we develop software tools for solving various linear programming problems such as a traditional LP problem, bicriteria LP problem, and multi-criteria LP problem on UNIX system. In a phase for reading data of various LP problems, we define a BNF(Backus-Nauel form) of various LP problems and implement BNF rules by using the C programming language.

In a phase for computing various LP problems, we use efficient methods for solving LP problems, develop various software tools on UNIX system, and combine each LP tool corresponding to an user request in which the Shell programming is used.

We also demonstrate some real-world LP problems by using LP software tools developed here on an UNIX System. Sanyo MPS 020.     

求解线性规划问题的光滑型牛顿算法

对线性规划的最优性条件,给出一个扩展系统,设计一个连续化的光滑型算法求解该系统。所设计的算法的全局收敛性不需要添加任何假设条件。在每一个迭代点处,只需要解一个线性方程组和做一次线性搜索,比现有求解线性规划问题的连续化方法具有更好的收敛性质。     

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.     

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.     

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.     

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.     

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.      

A coalitional game approach for fractional cooperative caching in content-oriented networks

In content-oriented networks, popular contents are replicated at the intermediate nodes to enhance content delivery performance. Under cooperative caching, the caching nodes collaborate to leverage one another’s cache capability and to reduce the amount of traffic transferring inside the network. This study considers the cooperation among service providers (SPs). The transferable-payoff coalitional game model is applied for analysis. We investigate the stability of the grand coalition and show that the dual-based cost allocation is in the core. A linear program (LP) minimizing the network bandwidth-expense is used for the characteristic function of the game model. However, solving the LP is a challenge because of a large amount of contents in the network. The Dantzig–Wolfe decomposition approach is further applied to decompose the large-scale problem into many subproblems, which can be solved in parallel. The analysis provides not only a deeper insight into the cooperative cache among SPs but also content placement and distribution strategies as a solution to the LP.     

A geometric view of parametric linear programming

We present a new definition of optimality intervals for the parametric right-hand side linear programming (parametric RHS LP) Problem ?(λ) = min{c ^t x¦Ax =b + λ¯b,x ≥ 0}. We then show that an optimality interval consists either of a breakpoint or the open interval between two consecutive breakpoints of the continuous piecewise linear convex function ?(λ). As a consequence, the optimality intervals form a partition of the closed interval {λ; ¦?(λ)¦ < ∞}. Based on these optimality intervals, we also introduce an algorithm for solving the parametric RHS LP problem which requires an LP solver as a subroutine. If a polynomial-time LP solver is used to implement this subroutine, we obtain a substantial improvement on the complexity of those parametric RHS LP instances which exhibit degeneracy. When the number of breakpoints of ?(λ) is polynomial in terms of the size of the parametric problem, we show that the latter can be solved in polynomial time.     

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

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

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.     

A hybrid of Nested Partition, Binary Ant System, and Linear Programming for the multidimensional knapsack problem

This work presents a hybrid algorithm of Nested Partition (NP), Binary Ant System (BAS), and Linear Programming (LP) to solve the multidimensional knapsack problem (MKP). The hybrid NP+BAS+LP algorithm takes advantage of the global search strategies of the NP algorithm; the ability of BAS to quickly generate good solutions and incorporates information obtained from solving a LP relaxation of the MKP to help guide the search. It thus incorporates both the lower bounds (LB), found by the BAS, and the upper bounds (UB), found by solving the relaxed LP, into the search by embedding both in the NP framework. An adjustable computation budget is implemented where the number of samples increases if the LB and the UB point to different promising subregions. The proposed hybrid is compared to state-of-the-art solution techniques and is found to be one of the best algorithms in terms of the quality of solutions obtained and CPU time requirements.     

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.     

The identification of binding constraints: A directional derivative heuristic approach

A heuristic procedure to identify binding constraints in linear programming (LP) problems is based upon an examination of the orientation of the constraining closed half spaces with respect to the orientation of the objective function. The constraints with the minimum difference will be classified as binding. An experiment to test the usefulness of this procedure in solving LP problems is also developed and discussed.     

一种可扩展的线性规划并行算法

由于线性规划在理论和实践中的重要性，对求解大规模规划问题并行算法的研究已引起许多学者的兴趣．本文根据Galperin提出的线性规划的一种线性时间的立方算法特别适合并行的特点，提出了一种基于SPMD模型和主从式MPI的线性规划并行算法，并对算法性能进行了深入分析，理论分析和在曙光3000上的实验结果表明：该算法具有粗粒度并行、良好的可扩展性和理想加速比模型等优点，明显优于目前为止求解同类不对称线性规划问题的其他并行算法，可用于求解此类大规模线性规划问题的高性能计算．     

A computational comparison of gomory and knapsack cuts

A common method of solving integer programs is to solve the problem first as a linear program (LP) then add constraints that cut off noninteger solutions from the set of LP feasible solutions. As soon as an optimal LP solution is all integer, then it is an optimal solution to the integer program. The method of Gomory can generate a variety of different cuts but there is a dearth of reports on systematic testing of the effectiveness of different cuts. We report extensive computational comparisons between a number of different cuts, including a successful one not previously publicised. It has been known for some time that Gomory cuts can be unsuccessful because of slow convergence with the accompanying difficulties of computer round-off error. Recently a method has been proposed for generating, for 0–1 integer problems, cuts that are usually tighter than Gomory cuts and thus give faster convergence. This method of knapsack cuts is tested in comparison with Gomory cuts for moderate size problems and is found to be superior for 0–1 problems having dense constraint matrices but only slightly better than Gomory cuts for problems with sparse matrices. On the other hand, knapsack cuts applied to general integer problems reformulated as 0–1 are found to be less successful than Gomory cuts applied to the original integer problem.     

Searching for optimal integer solutions to set partitioning problems using column generation

In this paper, we describe a new approach to increase the possibility of finding integer feasible columns to a set partitioning problem (SPP) directly in solving the linear programming (LP) relaxation using column generation. Traditionally, column generation is aimed to solve the LP‐relaxation as quickly as possible without any concern for the integer properties of the columns formed. In our approach, we aim to generate columns forming an optimal integer solution while simultaneously solving the LP‐relaxation. Using this approach, we can improve the possibility of finding integer solutions by heuristics at each node in the branch‐and‐bound search. In addition, we improve the possibility of finding high‐quality integer solutions in cases where only the columns in the root node are used to solve the problem. The basis of our approach is a subgradient technique applied to a Lagrangian dual formulation of the SPP extended with an additional surrogate constraint. This extra constraint is not relaxed and is used to better control the subgradient evaluations and how the multiplier values are computed. The column generation is then directed, via the multipliers, to construct columns that form feasible integer solutions. Computational experiments show that we can generate optimal integer columns in a large set of well‐known test problems as compared to both standard and stabilized column generation, and simultaneously keep the number of columns smaller than standard column generation. This is also supported by tests on a case study with work‐shift generation.     

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.     

Location pairs: a test coverage metric for shared-memory concurrent programs

We present a coverage metric targeted at shared-memory concurrent programs: the Location Pairs (LP) coverage metric. The goals of this metric are (i) to measure how thoroughly a program has been tested from a concurrency standpoint, i.e., whether enough qualitatively different thread interleavings have been explored, and (ii) to guide testing towards unexplored concurrency scenarios. This metric was inspired by an access pattern known to lead to high-level concurrency errors in industrial software and in the literature. We built a monitoring tool to measure LP coverage of test programs. We used the LP metric for interactive debugging, and compared LP coverage with other concurrency coverage metrics on Java benchmarks. We demonstrated that LP coverage corresponds better to concurrency errors, is a better measure of how well a program is exercised concurrency-wise by a test set, reaches saturation later than other coverage metrics, and is viable and useful as an interactive testing and debugging tool.