117 Matching Results

Search Results

Advanced search parameters have been applied.

Linear Programming--a Management Tool

Description: The purpose of this thesis is to integrate the most up-to-date information on the subject of linear programming into a comprehensive and understandable treatise for the consideration of management. The value of this study, then, is determined by the effectiveness of its presentation so that management may grasp an ample understanding of the subject.
Date: June 1963
Creator: Sosa-Rodriguez, Jose Ramon
Partner: UNT Libraries

Iterative Solution of Linear Programs

Description: By perturbing a linear program to a quadratic program, it is possible to solve the latter in its dual variable space by iterative techniques such as successive over-relaxation (SOR) methods. This provides a solution to the original linear program.
Date: July 1979
Creator: Mangasarian, Olvi L.
Partner: UNT Libraries Government Documents Department

Final report, DOE Grant DE-FG02-98ER25352, Computational semidefinite programming

Description: Semidefinite programming (SDP) is an extension of linear programming, with vector variables replaced by matrix variables and component wise nonnegativity replaced by positive semidefiniteness. SDP's are convex, but not polyhedral, optimization problems. SDP is well on its way to becoming an established paradigm in optimization, with many current potential applications. Consequently, efficient methods and software for solving SDP's are of great importance. During the award period, attention was primarily focused on three aspects of computational semidefinite programming: General-purpose methods for semidefinite and quadratic cone programming; Specific applications (LMI problems arising in control, minimizing a sum of Euclidean norms, a quantum mechanics application of SDP); and Optimizing matrix stability.
Date: September 5, 2002
Creator: Overton, Michael L.
Partner: UNT Libraries Government Documents Department

Generic Optimization Program User Manual Version 3.0.0

Description: GenOpt is an optimization program for the minimization of a cost function that is evaluated by an external simulation program. It has been developed for optimization problems where the cost function is computationally expensive and its derivatives are not available or may not even exist. GenOpt can be coupled to any simulation program that reads its input from text files and writes its output to text files. The independent variables can be continuous variables (possibly with lower and upper bounds), discrete variables, or both, continuous and discrete variables. Constraints on dependent variables can be implemented using penalty or barrier functions. GenOpt uses parallel computing to evaluate the simulations. GenOpt has a library with local and global multi-dimensional and one-dimensional optimization algorithms, and algorithms for doing parametric runs. An algorithm interface allows adding new minimization algorithms without knowing the details of the program structure. GenOpt is written in Java so that it is platform independent. The platform independence and the general interface make GenOpt applicable to a wide range of optimization problems. GenOpt has not been designed for linear programming problems, quadratic programming problems, and problems where the gradient of the cost function is available. For such problems, as well as for other problems, special tailored software exists that is more efficient.
Date: May 11, 2009
Creator: Wetter, Michael
Partner: UNT Libraries Government Documents Department

Analysis of error floor of LDPC codes under LP decoding over the BSC

Description: We consider linear programming (LP) decoding of a fixed low-density parity-check (LDPC) code over the binary symmetric channel (BSC). The LP decoder fails when it outputs a pseudo-codeword which is not a codeword. We propose an efficient algorithm termed the instanton search algorithm (ISA) which, given a random input, generates a set of flips called the BSC-instanton and prove that: (a) the LP decoder fails for any set of flips with support vector including an instanton; (b) for any input, the algorithm outputs an instanton in the number of steps upper-bounded by twice the number of flips in the input. We obtain the number of unique instantons of different sizes by running the ISA sufficient number of times. We then use the instanton statistics to predict the performance of the LP decoding over the BSC in the error floor region. We also propose an efficient semi-analytical method to predict the performance of LP decoding over a large range of transition probabilities of the BSC.
Date: January 1, 2009
Creator: Chertkov, Michael; Chilappagari, Shashi; Vasic, Bane & Stepanov, Mikhail
Partner: UNT Libraries Government Documents Department

DSDP5 user guide - software for semidefinite programming.

Description: DSDP implements the dual-scaling algorithm for semidefinite programming. The source code of this interior-point solver, written entirely in ANSI C, is freely available. The solver can be used as a subroutine library, as a function within the Matlab environment, or as an executable that reads and writes to files. Initiated in 1997, DSDP has developed into an efficient and robust general-purpose solver for semidefinite programming. Although the solver is written with semidefinite programming in mind, it can also be used for linear programming and other constraint cones. The features of DSDP include the following: a robust algorithm with a convergence proof and polynomially bounded complexity under mild assumptions on the data, primal and dual solutions, feasible solutions when they exist or approximate certificates of infeasibility, initial points that can be feasible or infeasible, relatively low memory requirements for an interior-point method, sparse and low-rank data structures, extensibility that allows applications to customize the solver and improve its performance, a subroutine library that enables it to be linked to larger applications, scalable performance for large problems on parallel architectures, and a well-documented interface and examples of its use. The package has been used in many applications and tested for efficiency, robustness, and ease of use. We welcome and encourage further use under the terms of the license included in the distribution.
Date: January 24, 2006
Creator: Benson, S. J.; Ye, Y. & Science, Mathematics and Computer
Partner: UNT Libraries Government Documents Department

Final Report---Optimization Under Nonconvexity and Uncertainty: Algorithms and Software

Description: the goal of this work was to develop new algorithmic techniques for solving large-scale numerical optimization problems, focusing on problems classes that have proven to be among the most challenging for practitioners: those involving uncertainty and those involving nonconvexity. This research advanced the state-of-the-art in solving mixed integer linear programs containing symmetry, mixed integer nonlinear programs, and stochastic optimization problems. The focus of the work done in the continuation was on Mixed Integer Nonlinear Programs (MINLP)s and Mixed Integer Linear Programs (MILP)s, especially those containing a great deal of symmetry.
Date: November 6, 2011
Creator: Linderoth, Jeff
Partner: UNT Libraries Government Documents Department

A path-following interior-point algorithm for linear and quadratic problems

Description: We describe an algorithm for the monotone linear complementarity problem that converges for many positive, not necessarily feasible, starting point and exhibits polynomial complexity if some additional assumptions are made on the starting point. If the problem has a strictly complementary solution, the method converges subquadratically. We show that the algorithm and its convergence extend readily to the mixed monotone linear complementarity problem and, hence, to all the usual formulations of the linear programming and convex quadratic programming problems.
Date: December 1, 1993
Creator: Wright, S.J.
Partner: UNT Libraries Government Documents Department

PCx user guide

Description: We describe the code PCx, a primal-dual interior-point code for linear programming. Information is given about problem formulation and the underlying algorithm, along with instructions for installing, invoking, and using the code. Computational results on standard test problems are tabulated. The current version number is 1.0.
Date: March 1, 1997
Creator: Czyzyk, J.; Mehrotra, S. & Wright, S.J.
Partner: UNT Libraries Government Documents Department

Multicriteria approximation through decomposition

Description: The authors propose a general technique called solution decomposition to devise approximation algorithms with provable performance guarantees. The technique is applicable to a large class of combinatorial optimization problems that can be formulated as integer linear programs. Two key ingredients of the technique involve finding a decomposition of a fractional solution into a convex combination of feasible integral solutions and devising generic approximation algorithms based on calls to such decompositions as oracles. The technique is closely related to randomized rounding. The method yields as corollaries unified solutions to a number of well studied problems and it provides the first approximation algorithms with provable guarantees for a number of new problems. The particular results obtained in this paper include the following: (1) The authors demonstrate how the technique can be used to provide more understanding of previous results and new algorithms for classical problems such as Multicriteria Spanning Trees, and Suitcase Packing. (2) They show how the ideas can be extended to apply to multicriteria optimization problems, in which they wish to minimize a certain objective function subject to one or more budget constraints. As corollaries they obtain first non-trivial multicriteria approximation algorithms for problems including the k-Hurdle and the Network Inhibition problems.
Date: December 1, 1997
Creator: Burch, C.; Krumke, S.; Marathe, M.; Phillips, C. & Sundberg, E.
Partner: UNT Libraries Government Documents Department

Computational experience with a dense column feature for interior-point methods

Description: Most software that implements interior-point methods for linear programming formulates the linear algebra at each iteration as a system of normal equations. This approach can be extremely inefficient when the constraint matrix has dense columns, because the density of the normal equations matrix is much greater than the constraint matrix and the system is expensive to solve. In this report the authors describe a more efficient approach for this case, that involves handling the dense columns by using a Schur-complement method and conjugate gradient interaction. The authors report numerical results with the code PCx, into which the technique now has been incorporated.
Date: August 1, 1997
Creator: Wenzel, M.; Czyzyk, J. & Wright, S.
Partner: UNT Libraries Government Documents Department

Inversion of Head Wave Traveltimes for Three-Dimensional Planar Structure

Description: Inversion of head wave arrival times for three-dimensional (3D) planar structure is formulated as a constrained parameter optimization problem, and solved via linear programming techniques. The earth model is characterized by a set of homogeneous and isotropic layers bounded by plane, dipping interfaces. Each interface may possess arbitrary strike and dip. Predicted data consists of traveltimes of critically refracted waves formed on the plane interfaces of the model. The nonlinear inversion procedure is iterative; an initial estimate of the earth model is refined until an acceptable match is obtained between observed and predicted data. Inclusion of a priori constraint information, in the form of inequality relations satisfied by the model parameters, assists the algorithm in converging toward a realistic solution. Although the 3D earth model adopted for the inversion procedure is simple, the algorithm is quite useful in two particular contexts: (i) it can provide an initial model estimate suitable for subsequent improvement by more general techniques (i.e., traveltime tomography), and (ii) it is an effective analysis tool for investigating the power of areal recording geometries for detecting and resolving 3D dipping planar structure.
Date: March 31, 1999
Creator: Aldridge, D.F. & Oldenburg, D.W.
Partner: UNT Libraries Government Documents Department

Systems Studies

Description: The Systems Studies Activity had two objectives: (1) to investigate nontechnical barriers to the deployment of biomass production and supply systems and (2) to enhance and extend existing systems models of bioenergy supply and use. For the first objective, the Activity focused on existing bioenergy markets. Four projects were undertaken: a comparative analysis of bioenergy in Sweden and Austria; a one-day workshop on nontechnical barriers jointly supported by the Production Systems Activity; the development and testing of a framework for analyzing barriers and drivers to bioenergy markets; and surveys of wood pellet users in Sweden, Austria and the US. For the second objective, two projects were undertaken. First, the Activity worked with the Integrated BioEnergy Systems (TBS) Activity of TEA Bioenergy Task XIII to enhance the BioEnergy Assessment Model (BEAM). This model is documented in the final report of the IBS Activity. The Systems Studies Activity contributed to enhancing the feedstock portion of the model by developing a coherent set of willow, poplar, and switchgrass production modules relevant to both the US and the UK. The Activity also developed a pretreatment module for switchgrass. Second, the Activity sponsored a three-day workshop on modeling bioenergy systems with the objectives of providing an overview of the types of models used to evaluate bioenergy and promoting communication among bioenergy modelers. There were nine guest speakers addressing different types of models used to evaluate different aspects of bioenergy, ranging from technoeconomic models based on the ASPEN software to linear programming models to develop feedstock supply curves for the US. The papers from this workshop have been submitted to Biomass and Bioenergy and are under editorial review.
Date: March 17, 1998
Creator: Graham, R.L.
Partner: UNT Libraries Government Documents Department

Towards a 4/3 Approximation for the Asymmetric Traveling Salesman Problem

Description: A long-standing conjecture in combinatorial optimization says that the integrality gap of the famous Held-Karp relaxation of the symmetric TSP is precisely 4/3. In this paper, we show that a slight strengthening of this conjecture implies a tight 4/3 integrality gap for a linear programming relaxation of the asymmetric TSP. This is surprising since no constant-factor approximation is known for the latter problem. Our main tools are a new characterization of the integrality gap for linear objective functions over polyhedra, and the isolation of ''hard-to-round'' solutions of the relaxations.
Date: June 10, 1999
Creator: Carr, Robert & Vempala, Santosh
Partner: UNT Libraries Government Documents Department

Randomized metarounding

Description: The authors present a new technique for the design of approximation algorithms that can be viewed as a generalization of randomized rounding. They derive new or improved approximation guarantees for a class of generalized congestion problems such as multicast congestion, multiple TSP etc. Their main mathematical tool is a structural decomposition theorem related to the integrality gap of a relaxation.
Date: January 25, 2000
Creator: CARR,ROBERT D. & VEMPALA,SANTOSH
Partner: UNT Libraries Government Documents Department

A new bound for the 2-edge connected subgraph problem

Description: Given a complete undirected graph with non-negative costs on the edges, the 2-Edge Connected Subgraph Problem consists in finding the minimum cost spanning 2-edge connected subgraph (where multi-edges are allowed in the solution). A lower bound for the minimum cost 2-edge connected subgraph is obtained by solving the linear programming relaxation for this problem, which coincides with the subtour relaxation of the traveling salesman problem when the costs satisfy the triangle inequality. The simplest fractional solutions to the subtour relaxation are the 1/2-integral solutions in which every edge variable has a value which is a multiple of 1/2. The authors show that the minimum cost of a 2-edge connected subgraph is at most four-thirds the cost of the minimum cost 1/2-integral solution of the subtour relaxation. This supports the long-standing 4/3 Conjecture for the TSP, which states that there is a Hamilton cycle which is within 4/3 times the cost of the optimal subtour relaxation solution when the costs satisfy the triangle inequality.
Date: April 1, 1998
Creator: Carr, R. & Ravi, R.
Partner: UNT Libraries Government Documents Department

Multicriteria approximation through decomposition

Description: The authors propose a general technique called solution decomposition to devise approximation algorithms with provable performance guarantees. The technique is applicable to a large class of combinatorial optimization problems that can be formulated as integer linear programs. Two key ingredients of their technique involve finding a decomposition of a fractional solution into a convex combination of feasible integral solutions and devising generic approximation algorithms based on calls to such decompositions as oracles. The technique is closely related to randomized rounding. Their method yields as corollaries unified solutions to a number of well studied problems and it provides the first approximation algorithms with provable guarantees for a number of new problems. The particular results obtained in this paper include the following: (1) the authors demonstrate how the technique can be used to provide more understanding of previous results and new algorithms for classical problems such as Multicriteria Spanning Trees, and Suitcase Packing; (2) they also show how the ideas can be extended to apply to multicriteria optimization problems, in which they wish to minimize a certain objective function subject to one or more budget constraints. As corollaries they obtain first non-trivial multicriteria approximation algorithms for problems including the k-Hurdle and the Network Inhibition problems.
Date: June 1998
Creator: Burch, C.; Krumke, S.; Marathe, M.; Phillips, C. & Sundberg, E.
Partner: UNT Libraries Government Documents Department

On-Off Minimum-Time Control With Limited Fuel Usage: Global Optima Via Linear Programming

Description: A method for finding a global optimum to the on-off minimum-time control problem with limited fuel usage is presented. Each control can take on only three possible values: maximum, zero, or minimum. The simplex method for linear systems naturally yields such a solution for the re-formulation presented herein because it always produces an extreme point solution to the linear program. Numerical examples for the benchmark linear flexible system are presented.
Date: September 1, 1999
Creator: DRIESSEN,BRIAN
Partner: UNT Libraries Government Documents Department

Mexico City Air Quality Research Initiative; Volume 5, Strategic evaluation

Description: Members of the Task HI (Strategic Evaluation) team were responsible for the development of a methodology to evaluate policies designed to alleviate air pollution in Mexico City. This methodology utilizes information from various reports that examined ways to reduce pollutant emissions, results from models that calculate the improvement in air quality due to a reduction in pollutant emissions, and the opinions of experts as to the requirements and trade-offs that are involved in developing a program to address the air pollution problem in Mexico City. The methodology combines these data to produce comparisons between different approaches to improving Mexico City`s air quality. These comparisons take into account not only objective factors such as the air quality improvement or cost of the different approaches, but also subjective factors such as public acceptance or political attractiveness of the different approaches. The end result of the process is a ranking of the different approaches and, more importantly, the process provides insights into the implications of implementing a particular approach or policy.
Date: March 1, 1994
Partner: UNT Libraries Government Documents Department