Recent advances in linear programming solution methodology have focused on interior point algorithms. These are powerful new methods, achieving significant reductions in computer time for large LPs and solving problems significantly larger than previously possible. This dissertation describes the implementation of interior point algorithms. It focuses on applications of direct sparse matrix methods to sparse symmetric positive definite systems of linear equations on scalar computers and vector supercomputers. The most computationally intensive step in each iteration of any interior point algorithm is the numerical factorization of a sparse symmetric positive definite matrix. In large problems or relatively dense problems, 80-90% or more of computational time is spent in this step. This study concentrates on solution methods for such linear systems. It is based on modifications and extensions of graph theory applied to sparse matrices. The row and column permutation of a sparse symmetric positive definite matrix dramatically affects the performance of solution algorithms. Various reordering methods are considered to find the best ordering for various numerical factorization methods and computer architectures. It is assumed that the reordering method will follow the fill-preserving rule, i.e., not allow additional fill-ins beyond that provided by the initial ordering. To follow this rule, a modular approach is used. In this approach, the matrix is first permuted by using any minimum degree heuristic, and then the permuted matrix is again reordered according to a specific reordering objective. Results of different reordering methods are described. There are several ways to compute the Cholesky factor of a symmetric positive definite matrix. A column Cholesky algorithm is a popular method for dense and sparse matrix factorization on serial and parallel computers. Applying this algorithm to a sparse matrix requires the use of sparse vector operations. Graph theory is applied to reduce sparse vector computations. A second and relatively new algorithm is the multifrontal algorithm. This method uses dense operations for sparse matrix computation at the expense of some data manipulation. The performance of the column Cholesky and multifrontal algorithms in the numerical factorization of a sparse symmetric positive definite matrix on an IBM 3090 vector supercomputer is described.

This report presents a qualitative case study, which explored how a Grade 11 mathematics teacher in a multilingual classroom used the learners’ home languages in order to support their understanding of concepts in Linear Programming. The study involved one teacher together with his Grade 11 learners and was carried out in a township school located in the Eastrand, Johannesburg. Data was collected through lesson observations of five consecutive lessons and a reflective interview with the teacher. The situated-sociocultural perspectives guided the study. The analysis shows that the teacher used learners’ home languages deliberately; in mathematics tasks, for asking questions, to re-voice learners’ contributions, for encouraging learners’ participation in mathematical discourses and practices, and for probing learners’ thinking. In general, the use of learners’ home languages enhanced learners’ understanding of Linear Programming concepts. The study also highlights the complexities of translating mathematics tasks from English to learners’ home languages.

by Shiu-Tung Ng. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1998. / Includes bibliographical references (leaves 100-103). / Abstract also in Chinese. / Chapter 1 --- Preliminary --- p.5 / Chapter 1.1 --- Linear and Convex Optimization Model --- p.5 / Chapter 1.2 --- Notations for Linear Optimization --- p.5 / Chapter 1.3 --- Definition and Properties of Convexities --- p.7 / Chapter 1.4 --- Useful Theorem for Unconstrained Minimization --- p.10 / Chapter 2 --- Linear Optimization --- p.11 / Chapter 2.1 --- Self-dual Linear Optimization Model --- p.11 / Chapter 2.2 --- Definitions and Main Theorems --- p.14 / Chapter 2.3 --- Self-dual Embedding and Simple Example --- p.22 / Chapter 2.4 --- Newton step --- p.25 / Chapter 2.5 --- "Rescaling and Definition of δ(xs,w)" --- p.29 / Chapter 2.6 --- An Interior Point Method --- p.32 / Chapter 2.6.1 --- Algorithm with Full Newton Steps --- p.33 / Chapter 2.6.2 --- Iteration Bound --- p.33 / Chapter 2.7 --- Background and Rounding Procedure for Interior-point Solution --- p.36 / Chapter 2.8 --- Solving Some LP problems --- p.42 / Chapter 2.9 --- Remarks --- p.51 / Chapter 3 --- Convex Optimization --- p.53 / Chapter 3.1 --- Introduction --- p.53 / Chapter 3.1.1 --- Convex Optimization Problem --- p.53 / Chapter 3.1.2 --- Idea of Interior Point Method --- p.55 / Chapter 3.2 --- Logarithmic Barrier Method --- p.55 / Chapter 3.2.1 --- Basic Concepts and Properties --- p.55 / Chapter 3.2.2 --- k-Self-Concordance Condition --- p.62 / Chapter 3.2.3 --- Short-step Logarithmic Barrier Algorithm --- p.64 / Chapter 3.2.4 --- Initialization Algorithm --- p.67 / Chapter 3.3 --- Center Method --- p.70 / Chapter 3.3.1 --- Basic Concepts and Properties --- p.70 / Chapter 3.3.2 --- Short-step Center Algorithm --- p.75 / Chapter 3.3.3 --- Initialization Algorithm --- p.76 / Chapter 3.4 --- Properties and Examples on Self-Concordance --- p.78 / Chapter 3.5 --- Examples of Convex Optimization Problem --- p.82 / Chapter 3.5.1 --- Self-concordant Logarithmic Barrier and Distance Function --- p.82 / Chapter 3.5.2 --- General Convex Optimization Problems --- p.91 / Chapter 3.6 --- Remarks --- p.98 / Bibliography

Typescript, etc. / Digitized by Kansas Correctional Industries

This thesis focuses on combining data envelopment analysis (DEA) and multi-objective linear programming (MOLP) methods to set targets by referencing peers' performances and decision-makers' (DMs) preferences. A large number of past papers have proven the importance of a company having a target; however, obtaining a feasible but challenging target has always been a difficult topic for companies. Since DEA was proposed in 1978, it has become one of the most popular performance assessment tools. The performance possibility set and efficient frontier established by DEA provide solid and scientific reference information for managers to evaluate an individual's efficiency. Based on the successful experience of DEA in performance assessment, many scholars have mentioned that DEA can be used to set appropriate targets as well; however, traditional DEA models do not include DMs' preference information that is crucial to a target-setting process. Therefore, several MOLP methods have been introduced to include DMs' preferences in the target-setting process based on the DEA efficient frontier and performance possibility set. The trade-off-based method is one of the most popular interactive methods that have been incorporated with DEA. However, there are several gaps in the current research: (1) the trade-off-based method could take so many interactions that no DMs could finish the interactive process; (2) DMs might find it very difficult to provide the preference information required by MOLP models; and (3) DMs cannot have an intuitive view in terms of the efficient frontier. Regarding the gaps above, this thesis proposes three new trade-off-based interactive target-setting models based on the DEA performance possibility set and efficient frontier to improve DMs' experience when setting targets. The three models can work independently or can be combined during the decision-making process. The piecewise linear model uses a piecewise linear assumption to simulate DMs' real utility function. It gradually narrows down the region that could contain DMs' most-preferred solution (MPS) until it reaches an acceptable range. This model could help DMs who have limited time for interaction but want to have a global view of the entire efficient frontier. This model has also been proven very helpful when DMs are not sensitive to close efficient solutions. The prioritized trade-off model provides a new way for a DM to know about the efficient frontier, which allows the DM to explore the efficient frontier following the preferred direction with a series of trade-off tables and trade-off figures as visual aids. The stepwise trade-off model focuses on situations where the number of objectives (outputs/inputs for the DEA model) is quite large and DMs cannot provide all indifference trade-offs between all the objectives simultaneously. To release the DMs' burden, the stepwise model starts from two objectives and gradually includes new objectives in the decision-making process, with the assumption that the indifference trade-offs between previous objectives are fixed, until all objectives are included. All three models have been validated through numerical examples and case studies of a Chinese state-owned bank to help DMs to explore their MPS in the DEA production possibility set.

In this thesis we study the theory and algorithms for separated continuous linear programming (SCLP) and its extensions. / Throughout this thesis, some numerical examples are used to illustrate the algorithms that we propose. In particular, we solve a special LQ control problem with sign constraints on the state and the control variables as an instance of SCCP, yielding a new solution method for such kind of LQ control problems. / We first investigate the relationships among SCLP, the dual of SCLP and the corresponding discretized versions of them. By using the symmetric primal and dual structure and an even partition of the time interval [0, T], we show that the strong duality holds between SCLP and its dual problem under some mild assumption. This is actually an alternative proof for the strong duality theorem. The other constructive proof is due to Weiss [50]. Our new proof is more direct and can be easily extended to prove the same strong duality results for the extensions of SCLP. Based on these results, we propose an approximation algorithm which solves SCLP with any prescribed precision requirement. Our algorithm is in fact a polynomial-time approximation (PTA) scheme. The trade-off between the quality of the solution and the computational effort is explicit. / We then study the extensions of SCLP; that is, separated continuous conic programming (SCCP) and its generalized version (GSCCP). It turns out that our results on SCLP can be readily extended to SCCP and GSCCP. To our knowledge, SCCP and GSCCP are new models with novel applications. / Wang Xiaoqing. / "June 2005." / Advisers: Shuzhong Zhang; David Da-Wei Yao. / Source: Dissertation Abstracts International, Volume: 67-01, Section: B, page: 0520. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (p. 122-127). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307.

Chan, Yuk Hei. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 49-51). / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Problem Definition --- p.1 / Chapter 1.1.1 --- Hypergraph Matching --- p.1 / Chapter 1.1.2 --- k-Set Packing --- p.2 / Chapter 1.1.3 --- k-Dimensional Matching --- p.2 / Chapter 1.1.4 --- Related Problems --- p.2 / Chapter 1.2 --- Main Result --- p.5 / Chapter 1.3 --- Overview of the Thesis --- p.6 / Chapter 2 --- Background --- p.8 / Chapter 2.1 --- Matching --- p.8 / Chapter 2.1.1 --- Augmenting Path --- p.8 / Chapter 2.1.2 --- Linear Programming --- p.10 / Chapter 2.1.3 --- Matching in General Graphs --- p.11 / Chapter 2.1.4 --- Approximate Min-max Relation for Hypergraphs --- p.11 / Chapter 2.2 --- Local Search --- p.12 / Chapter 2.2.1 --- Unweighted k-Set Packing --- p.12 / Chapter 2.2.2 --- Weighted k-Set Packing ´ؤ (k- - 1 + ₂ё)-approximation --- p.14 / Chapter 2.2.3 --- Weighted k-Set Packing´ؤ(2(k + l)/3 + ₂ё)-approximation --- p.15 / Chapter 2.2.4 --- Weighted k-Set Packing´ؤ((k + l)/2 + ₂ё)-approximation --- p.16 / Chapter 2.3 --- Iterative Rounding --- p.17 / Chapter 2.3.1 --- Basic Solution --- p.17 / Chapter 2.3.2 --- Bipartite Matching --- p.19 / Chapter 2.3.3 --- Generalized Steiner Network Problem --- p.20 / Chapter 2.3.4 --- Minimum Bounded Degree Spanning Tree --- p.22 / Chapter 2.4 --- Packing Problems --- p.24 / Chapter 2.4.1 --- Projective Plane --- p.26 / Chapter 2.5 --- Local Ratio --- p.28 / Chapter 2.5.1 --- Vertex Cover --- p.28 / Chapter 2.5.2 --- Local Ratio Theorem --- p.29 / Chapter 2.5.3 --- Feedback Vertex Set in Tournaments --- p.29 / Chapter 2.5.4 --- Fractional Local Ratio --- p.31 / Chapter 2.5.5 --- Maximum Weight Independent Set in t-interval Graph --- p.31 / Chapter 3 --- k-Dimensional Matching --- p.33 / Chapter 3.1 --- Integrality Gap of the Standard LP Relaxation --- p.33 / Chapter 3.1.1 --- Approximation Algorithm for Unweighted k-D Matching --- p.34 / Chapter 3.1.2 --- Fractional Colouring --- p.35 / Chapter 3.1.3 --- Produce an Ordering --- p.37 / Chapter 3.2 --- Approximation Algorithm for Weighted k-D Matching --- p.38 / Chapter 4 --- k-Set Packing --- p.40 / Chapter 4.1 --- Integrality Gap of the Standard LP Relaxation --- p.40 / Chapter 4.2 --- Improved LP Relaxation for 3-SP --- p.41 / Concluding Remarks --- p.48 / Bibliography --- p.49

The purposes of this paper were to inventory the available agricultural production resources in Utah, to determine how those resources could be allocated most efficiently, and to provide information to aid the crop and livestock producing sectors in Utah in making informed production and marketing decisions. Utah was divided into eight agricultural production and product consumption regions and the rest of the country was regionalized into product supply and market areas. Input and output coefficients, production costs, and market prices for the major Utah crop and livestock production enterprises and their products were developed . A linear program was then used to determine how resources could most profitably be allocated among regions and production enterprises. The optimal marketing pattern for agricultural commodities produced in Utah was also generated. A sensitivity analysis was utilized to ascertain the stability of the optimal production and marketing patterns.

No description available.

Thesis (M.S.)--Rochester Institute of Technology, 2007. / Typescript. Includes bibliographical references (leaves 74-78).