To see the other types of publications on this topic, follow the link: Linear programming.
Dissertations / Theses on the topic 'Linear programming'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Linear programming.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Andreotti, Sandro [Verfasser]. "Linear Programming and Integer Linear Programming in Bioinformatics / Sandro Andreotti." Berlin : Freie Universität Berlin, 2015. http://d-nb.info/1066645213/34.
Full text
2
Sarrabezolles, Pauline. "Colourful linear programming." Thesis, Paris Est, 2015. http://www.theses.fr/2015PESC1033/document.
Full textAbstract:
Le théorème de Carathéodory coloré, prouvé en 1982 par Bárány, énonce le résultat suivant. Etant donnés d Å1 ensembles de points S1,SdÅ1 dans Rd , si chaque Si contient 0 dans son enveloppe convexe, alors il existe un sous-ensemble arc-en-ciel T µ SdÅ1 iÆ1 Si contenant 0 dans son enveloppe convexe, i.e. un sous-ensemble T tel que jT \Si j • 1 pour tout i et tel que 0 2 conv(T ). Ce théorème a donné naissance à de nombreuses questions, certaines algorithmiques et d’autres plus combinatoires. Dans ce manuscrit, nous nous intéressons à ces deux aspects. En 1997, Bárány et Onn ont défini la programmation linéaire colorée comme l’ensemble des questions algorithmiques liées au théorème de Carathéodory coloré. Parmi ces questions, deux ont particulièrement retenu notre attention. La première concerne la complexité du calcul d’un sous-ensemble arc-en-ciel comme dans l’énoncé du théorème. La seconde, en un sens plus générale, concerne la complexité du problème de décision suivant. Etant donnés des ensembles de points dans Rd , correspondant aux couleurs, il s’agit de décider s’il existe un sous-ensemble arc-en-ciel contenant 0 dans son enveloppe convexe, et ce en dehors des conditions du théorème de Carathéodory coloré. L’objectif de cette thèse est de mieux délimiter les cas polynomiaux et les cas “difficiles” de la programmation linéaire colorée. Nous présentons de nouveaux résultats de complexités permettant effectivement de réduire l’ensemble des cas encore incertains. En particulier, des versions combinatoires du théorème de Carathéodory coloré sont présentées d’un point de vue algorithmique. D’autre part, nous montrons que le problème de calcul d’un équilibre de Nash dans un jeu bimatriciel peut être réduit polynomialement à la programmation linéaire coloré. En prouvant ce dernier résultat, nous montrons aussi comment l’appartenance des problèmes de complémentarité à la classe PPAD peut être obtenue à l’aide du lemme de Sperner. Enfin, nous proposons une variante de l’algorithme de Bárány et Onn, calculant un sous ensemble arc-en-ciel contenant 0 dans son enveloppe convexe sous les conditions du théorème de Carathéodory coloré. Notre algorithme est clairement relié à l’algorithme du simplexe. Après une légère modification, il coïncide également avec l’algorithme de Lemke, calculant un équilibre de Nash dans un jeu bimatriciel. La question combinatoire posée par le théorème de Carathéodory coloré concerne le nombre de sous-ensemble arc-en-ciel contenant 0 dans leurs enveloppes convexes. Deza, Huang, Stephen et Terlaky (Colourful simplicial depth, Discrete Comput. Geom., 35, 597–604 (2006)) ont formulé la conjecture suivante. Si jSi j Æ d Å1 pour tout i 2 {1, . . . ,d Å1}, alors il y a au moins d2Å1 sous-ensemble arc-en-ciel contenant 0 dans leurs enveloppes convexes. Nous prouvons cette conjecture à l’aide d’objets combinatoires, connus sous le nom de systèmes octaédriques, dont nous présentons une étude plus approfondie<br>The colorful Carathéodory theorem, proved by Bárány in 1982, states the following. Given d Å1 sets of points S1, . . . ,SdÅ1 µ Rd , each of them containing 0 in its convex hull, there exists a colorful set T containing 0 in its convex hull, i.e. a set T µ SdÅ1 iÆ1 Si such that jT \Si j • 1 for all i and such that 0 2 conv(T ). This result gave birth to several questions, some algorithmic and some more combinatorial. This thesis provides answers on both aspects. The algorithmic questions raised by the colorful Carathéodory theorem concern, among other things, the complexity of finding a colorful set under the condition of the theorem, and more generally of deciding whether there exists such a colorful set when the condition is not satisfied. In 1997, Bárány and Onn defined colorful linear programming as algorithmic questions related to the colorful Carathéodory theorem. The two questions we just mentioned come under colorful linear programming. This thesis aims at determining which are the polynomial cases of colorful linear programming and which are the harder ones. New complexity results are obtained, refining the sets of undetermined cases. In particular, we discuss some combinatorial versions of the colorful Carathéodory theorem from an algorithmic point of view. Furthermore, we show that computing a Nash equilibrium in a bimatrix game is polynomially reducible to a colorful linear programming problem. On our track, we found a new way to prove that a complementarity problem belongs to the PPAD class with the help of Sperner’s lemma. Finally, we present a variant of the “Bárány-Onn” algorithm, which is an algorithmcomputing a colorful set T containing 0 in its convex hull whose existence is ensured by the colorful Carathéodory theorem. Our algorithm makes a clear connection with the simplex algorithm. After a slight modification, it also coincides with the Lemke method, which computes a Nash equilibriumin a bimatrix game. The combinatorial question raised by the colorful Carathéodory theorem concerns the number of positively dependent colorful sets. Deza, Huang, Stephen, and Terlaky (Colourful simplicial depth, Discrete Comput. Geom., 35, 597–604 (2006)) conjectured that, when jSi j Æ d Å1 for all i 2 {1, . . . ,d Å1}, there are always at least d2Å1 colourful sets containing 0 in their convex hulls. We prove this conjecture with the help of combinatorial objects, known as the octahedral systems. Moreover, we provide a thorough study of these objects
3
Espinoza, Daniel G. "On Linear Programming, Integer Programming and Cutting Planes." Diss., Georgia Institute of Technology, 2006. http://hdl.handle.net/1853/10482.
Full textAbstract:
In this thesis we address three related topic in the field of Operations Research.
Firstly we discuss the problems and limitation of most common solvers for linear programming, precision.
We then present a solver that generate rational optimal solutions to linear programming problems by solving a succession of (increasingly more precise) floating point approximations of the original rational problem until the rational optimality conditions are achieved.
This method is shown to be (on average) only 20% slower than the common pure floating point approach, while returning true optimal solutions to the problems.
Secondly we present an extension of the Local Cut procedure introduced by Applegate et al, 2001, for the Symmetric Traveling Salesman Problem (STSP), to the general setting of MIP problems.
This extension also proves finiteness of the separation, facet and tilting procedures in the general MIP setting, and also provides conditions under which the separation procedure is guaranteed to generate cuts that separate the current fractional solution from the convex hull of the mixed-integer polyhedron.
We then move on to explore some configurations for local cuts, realizing extensive testing on the instances from MIPLIB.
Those results show that this technique may be useful in general MIP problems, while the experience of Applegate et al, shows that the ideas can be successfully applied to structures problems as well.
Thirdly we present an extensive computational experiment on the TSP and Domino Parity inequalities as introduced by Letchford, 2000.
This work also include a safe-shrinking theorem for domino parity inequalities, heuristics to apply the planar separation algorithm introduced by Letchford to instances where the planarity requirement does not hold, and several practical speed-ups.
Our computational experience showed that this class of inequalities effectively improve the lower bounds from the best relaxations obtained with Concorde, which is one of the state of the art solvers for the STSP.
As part of these experience, we solved to optimality the (up to now) largest two STSP instances, both of them belong to the TSPLIB set of instances and they have 18,520 and 33,810 cities respectively.
4
Wei, Hua. "Numerical Stability in Linear Programming and Semidefinite Programming." Thesis, University of Waterloo, 2006. http://hdl.handle.net/10012/2922.
Full textAbstract:
We study numerical stability for interior-point methods applied to Linear Programming, LP, and Semidefinite Programming, SDP. We analyze the difficulties inherent in current methods and present robust algorithms. <br /><br /> We start with the error bound analysis of the search directions for the normal equation approach for LP. Our error analysis explains the surprising fact that the ill-conditioning is not a significant problem for the normal equation system. We also explain why most of the popular LP solvers have a default stop tolerance of only 10<sup>-8</sup> when the machine precision on a 32-bit computer is approximately 10<sup>-16</sup>. <br /><br /> We then propose a simple alternative approach for the normal equation based interior-point method. This approach has better numerical stability than the normal equation based method. Although, our approach is not competitive in terms of CPU time for the NETLIB problem set, we do obtain higher accuracy. In addition, we obtain significantly smaller CPU times compared to the normal equation based direct solver, when we solve well-conditioned, huge, and sparse problems by using our iterative based linear solver. Additional techniques discussed are: crossover; purification step; and no backtracking. <br /><br /> Finally, we present an algorithm to construct SDP problem instances with prescribed strict complementarity gaps. We then introduce two <em>measures of strict complementarity gaps</em>. We empirically show that: (i) these measures can be evaluated accurately; (ii) the size of the strict complementarity gaps correlate well with the number of iteration for the SDPT3 solver, as well as with the local asymptotic convergence rate; and (iii) large strict complementarity gaps, coupled with the failure of Slater's condition, correlate well with loss of accuracy in the solutions. In addition, the numerical tests show that there is no correlation between the strict complementarity gaps and the geometrical measure used in [31], or with Renegar's condition number.
5
Wolf, Jan [Verfasser]. "Quantified Linear Programming / Jan Wolf." Aachen : Shaker, 2015. http://d-nb.info/1074087275/34.
Full text
6
Sjöström, Henrik. "Pivoting methods for linear programming." Thesis, KTH, Matematik (Inst.), 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-98977.
Full text
7
Price, C. J. "Non-linear semi-infinite programming." Thesis, University of Canterbury. Mathematics and Statistics, 1992. http://hdl.handle.net/10092/7920.
Full textAbstract:
Optimisation problems occur in many branches of science, engineering, and economics, as well as in other areas. The diversity of the various types of optimisation problems is extremely large, and so a unified approach is not attempted here. This thesis concentrates on a specific type of problem: non-linear semi-infinite programming.
8
Wu, S. Y. "Linear programming on measure spaces." Thesis, University of Cambridge, 1985. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.372925.
Full text
9
DIAS, DOUGLAS MOTA. "QUANTUM-INSPIRED LINEAR GENETIC PROGRAMMING." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2010. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=17544@1.
Full textAbstract:
COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR<br>A superioridade de desempenho dos algoritmos quânticos, em alguns problemas
específicos, reside no uso direto de fenômenos da mecânica quântica para
realizar operações com dados em computadores quânticos. Esta característica fez
surgir uma nova abordagem, denominada Computação com Inspiração Quântica,
cujo objetivo é criar algoritmos clássicos (executados em computadores clássicos)
que tirem proveito de princípios da mecânica quântica para melhorar seu desempenho.
Neste sentido, alguns algoritmos evolutivos com inspiração quântica tem
sido propostos e aplicados com sucesso em problemas de otimização combinatória
e numérica, apresentando desempenho superior àquele dos algoritmos evolutivos
convencionais, quanto à melhoria da qualidade das soluções e à redução do número
de avaliações necessárias para alcançá-las. Até o presente momento, no entanto,
este novo paradigma de inspiração quântica ainda não havia sido aplicado à Programação
Genética (PG), uma classe de algoritmos evolutivos que visa à síntese automática
de programas de computador. Esta tese propõe, desenvolve e testa um novo
modelo de algoritmo evolutivo com inspiração quântica, denominado Programação
Genética Linear com Inspiração Quântica (PGLIQ), para a evolução de programas
em código de máquina. A Programação Genética Linear é assim denominada
porque cada um dos seus indivíduos é representado por uma lista de instruções (estruturas
lineares), as quais são executadas sequencialmente. As contribuições deste
trabalho são o estudo e a formulação inédita do uso do paradigma da inspiração
quântica na síntese evolutiva de programas de computador. Uma das motivações
para a opção pela evolução de programas em código de máquina é que esta é a
abordagem de PG que, por oferecer a maior velocidade de execução, viabiliza experimentos
em larga escala. O modelo proposto é inspirado em sistemas quânticos
multiníveis e utiliza o qudit como unidade básica de informação quântica, o qual
representa a superposição dos estados de um sistema deste tipo. O funcionamento
do modelo se baseia em indivíduos quânticos, que representam a superposição de
todos os programas do espaço de busca, cuja observação gera indivíduos clássicos
e os programas (soluções). Nos testes são utilizados problemas de regressão simbólica
e de classificação binária para se avaliar o desempenho da PGLIQ e compará-lo
com o do modelo AIMGP (Automatic Induction of Machine Code by Genetic Programming),
considerado atualmente o modelo de PG mais eficiente na evolução de
código de máquina, conforme citado em inúmeras referências bibliográficas na área.
Os resultados mostram que a Programação Genética Linear com Inspiração Quântica
(PGLIQ) apresenta desempenho geral superior nestas classes de problemas, ao
encontrar melhores soluções (menores erros) a partir de um número menor de avaliações,
com a vantagem adicional de utilizar um número menor de parâmetros e
operadores que o modelo de referência. Nos testes comparativos, o modelo mostra
desempenho médio superior ao do modelo de referência para todos os estudos
de caso, obtendo erros de 3 a 31% menores nos problemas de regressão simbólica,
e de 36 a 39% nos problemas de classificação binária. Esta pesquisa conclui que
o paradigma da inspiração quântica pode ser uma abordagem competitiva para se
evoluir programas eficientemente, encorajando o aprimoramento e a extensão do
modelo aqui apresentado, assim como a criação de outros modelos de programação
genética com inspiração quântica.<br>The superior performance of quantum algorithms in some specific problems
lies in the direct use of quantum mechanics phenomena to perform operations with
data on quantum computers. This feature has originated a new approach, named
Quantum-Inspired Computing, whose goal is to create classic algorithms (running
on classical computers) that take advantage of quantum mechanics principles to
improve their performance. In this sense, some quantum-inspired evolutionary algorithms
have been proposed and successfully applied in combinatorial and numerical
optimization problems, presenting a superior performance to that of conventional
evolutionary algorithms, by improving the quality of solutions and reducing
the number of evaluations needed to achieve them. To date, however, this
new paradigm of quantum inspiration had not yet been applied to Genetic Programming
(GP), a class of evolutionary algorithms that aims the automatic synthesis
of computer programs. This thesis proposes, develops and tests a novel model of
quantum-inspired evolutionary algorithm named Quantum-Inspired Linear Genetic
Programming (QILGP) for the evolution of machine code programs. Linear Genetic
Programming is so named because each of its individuals is represented by a list of
instructions (linear structures), which are sequentially executed. The contributions
of this work are the study and formulation of the novel use of quantum inspiration
paradigm on evolutionary synthesis of computer programs. One of the motivations
for choosing by the evolution of machine code programs is because this is the GP
approach that, by offering the highest speed of execution, makes feasible large-scale
experiments. The proposed model is inspired on multi-level quantum systems and
uses the qudit as the basic unit of quantum information, which represents the superposition
of states of such a system. The model’s operation is based on quantum individuals,
which represent a superposition of all programs of the search space, whose
observation leads to classical individuals and programs (solutions). The tests use
symbolic regression and binary classification problems to evaluate the performance
of QILGP and compare it with the AIMGP model (Automatic Induction of Machine
Code by Genetic Programming), which is currently considered the most efficient GP
model to evolve machine code, as cited in numerous references in this field. The results
show that Quantum-Inspired Linear Genetic Programming (QILGP) presents
superior overall performance in these classes of problems, by achieving better solutions
(smallest error) from a smaller number of evaluations, with the additional
advantage of using a smaller number of parameters and operators that the reference model. In comparative tests, the model shows average performance higher than that
of the reference model for all case studies, achieving errors 3-31% lower in the
problems of symbolic regression, and 36-39% in the binary classification problems.
This research concludes that the quantum inspiration paradigm can be a competitive
approach to efficiently evolve programs, encouraging the improvement and
extension of the model presented here, as well as the creation of other models of
quantum-inspired genetic programming.
10
Ramadan, Khaled Carleton University Dissertation Mathematics and Statistics. "Linear programming with interval coefficients." Ottawa, 1996.
Find full text
11
Sadhana, Vishnu V. "Efficient presolving in linear programming." [Gainesville, Fla.] : University of Florida, 2002. http://purl.fcla.edu/fcla/etd/UFE1000157.
Full text
12
Ilyes, Amy Louise. "Using linear programming to solve convex quadratic programming problems." Case Western Reserve University School of Graduate Studies / OhioLINK, 1993. http://rave.ohiolink.edu/etdc/view?acc_num=case1056644216.
Full text
13
Gassmann, Horand Ingo. "Multi-period stochastic programming." Thesis, University of British Columbia, 1987. http://hdl.handle.net/2429/27304.
Full textAbstract:
This dissertation presents various aspects of the solution of the linear multi-period stochastic programming problem. Under relatively mild assumptions on the structure of the random variables present in the problem, the value function at every time stage is shown to be jointly convex in the history of the process, namely the random variables observed so far as well as the decisions taken up to that point.
Convexity enables the construction of both upper and lower bounds on the value of the entire problem by suitable discretization of the random variables. These bounds are developed in Chapter 2, where it is also demonstrated how the bounds can be made arbitrarily sharp if the discretizations are chosen sufficiently fine. The chapter emphasizes computability of the bounds, but does not concern itself with finding the discretizations themselves.
The practise commonly followed to obtain a discretization of a random variable is to partition its support, usually into rectangular subsets. In order to apply the bounds of Chapter 2, one needs to determine the probability mass and weighted centroid for each element of the partition. This is a hard problem in itself, since in the continuous case it amounts to a multi-dimensional integration. Chapter 3 describes some Monte-Carlo techniques which can be used for normal distributions. These methods require random sampling, and the two main issues addressed are efficiency and accuracy. It turns out that the optimal method to use depends somewhat on the probability mass of the set in question.
Having obtained a suitable discretization, one can then solve the resulting large scale linear program which approximates the original problem. Its constraint matrix is highly structured, and Chapter 4 describes one algorithm which attempts to utilize this structure.
The algorithm uses the Dantzig-Wolfe decomposition principle, nesting decomposition
levels one inside the other. Many of the subproblems generated in the course of this decomposition share the same constraint matrices and can thus be solved simultaneously. Numerical results show that the algorithm may out-perform a linear programming package on some simple problems.
Chapter 5, finally, combines all these ideas and applies them to a problem in forest management. Here it is required to find logging levels in each of several time periods to maximize the expected revenue, computed as the volume cut times an appropriate discount factor. Uncertainty enters into the model in the form of the risk of forest fires and other environmental hazards, which may destroy a fraction of the existing forest. Several discretizations are used to formulate both upper and lower bound approximations to the original problem.<br>Business, Sauder School of<br>Graduate
14
Eldhuset, Åsmund. "Linear Programming on the Cell/BE." Thesis, Norwegian University of Science and Technology, Department of Computer and Information Science, 2009. http://urn.kb.se/resolve?urn=urn:nbn:no:ntnu:diva-9091.
Full textAbstract:
<p>Linear programming is a form of mathematical optimisation in which one seeks to optimise a linear function subject to linear constraints on the variables. It is a very versatile tool that has many important applications, one of them being modelling of production and trade in the petroleum industry. The Cell Broadband Engine, developed by IBM, Sony and Toshiba, is an innovative multicore architecture that has already been proven to have a great potential for high performance computing. However, developing applications for the Cell/BE is challenging, particularily due to the low-level memory management that is mandated by the architecture, and because careful optimisation by hand is often required to get the most out of the hardware. In this thesis, we investigate the opportunities for implementing a parallel solver for sparse linear programs on the Cell/BE. A parallel version of the standard simplex method is developed, and the ASYNPLEX algorithm by Hall and McKinnon is partially implemented on the Cell/BE. We have met substantial challenges when it comes to numerical stability, and this has prevented us from spending sufficient time on Cell/BE-specific optimisation and support for large data sets. Our implementations can therefore only be regarded as proofs of concept, but we provide analyses and discussions of several aspects of the implementations, which may guide the future work on this topic.</p>
15
Leong, Fu Fai. "Application of linear programming in Sudoku." Thesis, University of Macau, 2006. http://umaclib3.umac.mo/record=b1636813.
Full text
16
Mohyedin, Kermani Ehsan. "Distributed linear programming with Apache Spark." Thesis, University of British Columbia, 2016. http://hdl.handle.net/2429/59990.
Full textAbstract:
For this thesis project, we have implemented Mehrotra's predictor-corrector interior point algorithm on top of Apache Spark for solving large-scale linear programming problems. Our large-scale solver (Spark-LP) is unique because it is open-source, fault-tolerant and can be used on commodity cluster of machines. As a result, Spark-LP provides an opportunity to solve large-scale problems at the lowest possible cost. We have assessed the performance and convergent results of our solver on self-generated, sparse and dense large-scale problems over small to medium-sized clusters, composed of 16 to 64 Amazon's Elastic Computing Cloud r3.xlarge instances.
In conclusions, we have made important suggestions for breaking the current structural limitations so that our solver can be used on heterogeneous clusters containing CPUs and GPUs on JVM environment without the usual numerical
limitations and overheads.<br>Science, Faculty of<br>Computer Science, Department of<br>Graduate
17
Kaseke, Evans. "Fuzzy linear programming and reservoir management." Thesis, University of British Columbia, 1987. http://hdl.handle.net/2429/26708.
Full textAbstract:
The presence of imprecision in parameter specification of water resources
management problems leads to the formulation of fuzzy programming
models. This thesis presents the formulation of a two-reservoir system problem as a fuzzy L.P. model. The aim is to determine if larger monetary
benefits, over and above the usual benefits, can be obtained from the system. The other aim is to determine if desired industrial and domestic water allocations, as well as outflows for selected periods can be achieved.
The problem is formulated as a conventional L.P. model. Then selected water allocations and outflows are fuzzified resulting in a fuzzy L.P. model. The alternative fuzzy L.P. model is also presented.
Monetary benefits larger than those from the conventional L.P. were obtained through the fuzzy L.P. model. The desired water allocations and outflows were also realised for selected periods. Sensitivity information was obtained for fuzzy and non-fuzzy constraints. The alternative fuzzy L.P. model did not give additional valuable information than that obtained from the initial fuzzy L.P. model.<br>Applied Science, Faculty of<br>Civil Engineering, Department of<br>Graduate
18
Karamalis, Constantinos. "Data perturbation analyses for linear programming." Thesis, University of Ottawa (Canada), 1994. http://hdl.handle.net/10393/6709.
Full textAbstract:
This thesis focuses on several aspects of data perturbation for Linear Programming. Classical questions of degeneracy and post-optimal analysis are given a unified presentation, in a view of new interior point methods of linear programming. The performance of these methods is compared to the simplex algorithm; interior point methods are shown to alleviate some difficulties of representation and solution of linear programs. An affine scaling algorithm is implemented in conjunction with a simple rounding heuristic to asses the benefit of interior point trajectories to provide approximate solutions of linear integer programming.
19
Brameier, Markus [Verfasser]. "On linear genetic programming / Markus Brameier." Dortmund : Universitätsbibliothek Technische Universität Dortmund, 2005. http://d-nb.info/1011533146/34.
Full text
20
Mohamed, Radzi Nor Haizan. "Multi-objective planning using linear programming." Thesis, University of Strathclyde, 2010. http://oleg.lib.strath.ac.uk:80/R/?func=dbin-jump-full&object_id=15344.
Full text
21
TORTORELLI, MARCUS MAGNO FERNANDES. "CENTRAL PATH ALGORITHMS FOR LINEAR PROGRAMMING." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 1991. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=9405@1.
Full textAbstract:
Neste trabalho estudamos os algoritmos de Pontos Interiores para programação Linear. Publicados após o Algoritmo de Karmarkar. Que seguem, de algum modo, a Trajetória Central. São considerados tanto algoritmos Primais quanto Primais-Duais e também verificadas a eficácia da aplicação da metodologia de busca bidirecional. Estes métodos foram implementados e testados resolvendo um conjunto de problemas gerados aleatoriamente. Através da comparação dos resultados analisamos o desempenho das diferentes metodologias.<br>We study here the Interior Points Algorithms for Linear Programming, developed after Karmarkar s Algorithm, which follow the Central Path. Both Primal and Primal-dual Algorithms are considered and also the efficiency of applying a bidirecional Search procedure is verified. These methods were implemented and tested solving a set of randomly generated problems. Comparing these results we analyze the performance of the methodologies.
22
Epstein, Rafael 1961. "Linear programming and capacitated network loading." Thesis, Massachusetts Institute of Technology, 1998. http://hdl.handle.net/1721.1/10057.
Full text
23
Sharma, Vivek Narain. "Linear programming and quadratic programming approach for graduation in fuzzy environment." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2001. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/MQ57577.pdf.
Full text
24
Edlund, Ove. "Solution of linear programming and non-linear regression problems using linear M-estimation methods /." Luleå, 1999. http://epubl.luth.se/1402-1544/1999/17/index.html.
Full text
25
Kästner, Daniel. "Retargetable postpass optimisation by integer linear programming." [S.l.] : [s.n.], 2000. http://deposit.ddb.de/cgi-bin/dokserv?idn=972330917.
Full text
26
Stoutchinin, Artour V. "Optimal software pipelining, integer linear programming approach." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk2/tape16/PQDD_0002/MQ29793.pdf.
Full text
27
Kong, Seunghyun. "Linear programming algorithms using least-squares method." Diss., Available online, Georgia Institute of Technology, 2007, 2007. http://etd.gatech.edu/theses/available/etd-04012007-010244/.
Full textAbstract:
Thesis (Ph. D.)--Industrial and Systems Engineering, Georgia Institute of Technology, 2007.<br>Martin Savelsbergh, Committee Member ; Joel Sokol, Committee Member ; Earl Barnes, Committee Co-Chair ; Ellis L. Johnson, Committee Chair ; Prasad Tetali, Committee Member.
28
Stoutchinin, Artour V. "Optimal software pipelining : integer linear programming approach." Thesis, McGill University, 1996. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=27418.
Full textAbstract:
In optimizing the code for high-performance processors, software pipelining of innermost loops is of fundamental importance. In order to benefit from software pipelining, it is essential to: (i) find the rate-optimal legal schedule, and (ii) allocate registers to the found schedule (it must fit into the limited number of available machine registers). This thesis deals with the development of a software pipeliner that produces the best possible schedules in terms of required registers, thus, assisting register allocation.<br>Software pipelining and register allocation can be formulated as an integer linear programming (ILP) problem, aiming to produce optimal schedules. In this thesis, we discuss the application of the integer linear programming to software pipelining and design a pipeliner for the MIPS R8000 superscalar microprocessor. We extended the previously developed ILP framework to a full software pipelining implementation by: (1) establishing an ILP model for the R8000 processor, (2) implementing the model in Modulo Scheduling ToolSet (MOST), (3) integrating it into the MIPSpro compiler, (4) successfully producing real code and gathering runtime statistics, and (5) developing and implementing a model for optimization of the memory system behavior on the R8000 processor.<br>The ILP-based software pipeliner was tested as a functional replacement for the original MIPSpro software pipeliner. Our results indicate a need of improving the ILP formulation and its solution: (1) the existing technique failed to produce results for loops with large instruction counts, (2) it was not able to guarantee register optimality for many interesting and important loops, for which optimal scheduling is necessary in order to avoid spilling, (3) the branching order, in which an ILP solver traverses the branch-and-bound tree, was a single significant factor that affected the ILP solution time, leading to a conclusion that exploiting scheduling problem structure is essential for improving the efficiency of the ILP problem solving in the future.
29
Kaluzny, Bohdan Lubomyr. "Linear programming : pivoting on polyhedra and arrangements." Thesis, McGill University, 2005. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=100633.
Full textAbstract:
Linear programming is perhaps the most useful tool in optimization, much of it's success owed to the efficiency of the simplex method in practice --- its ability to solve problems with millions of variables with relative ease. However, whether there exists a strongly polynomial algorithm to solve linear programming remains an open question. Pivot methods, including the simplex method, remain the best hope for finding such an algorithm, despite the fact that almost all variants have been shown to require exponential time on special instances. Fundamental questions about the path length (number of iterations) of pivot methods remain unanswered. Some, such as the related Hirsch Conjecture, are famous long-standing problems in polyhedral theory. How long can a pivot path be? How many distinct degenerate solutions (bases) can appear during a simplex method cycle? How long can a finite pivot rule stall without improving the solution? Can we enumerate all possible pivot paths to optimality? Can we compute monotone disjoint pivot paths? These are some of the questions we tackle in this thesis in a quest to better understand pivot methods.
30
Lewis, A. "Extreme point methods for infinite linear programming." Thesis, University of Cambridge, 1986. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.384548.
Full text
31
Panagiotopoulos, Apostolos. "Optimising time series forecasts through linear programming." Thesis, University of Nottingham, 2012. http://eprints.nottingham.ac.uk/12515/.
Full textAbstract:
This study explores the usage of linear programming (LP) as a tool to optimise the parameters of time series forecasting models. LP is the most well-known tool in the field of operational research and it has been used for a wide range of optimisation problems. Nonetheless, there are very few applications in forecasting and all of them are limited to causal modelling. The rationale behind this study is that time series forecasting problems can be treated as optimisation problems, where the objective is to minimise the forecasting error. The research topic is very interesting from a theoretical and mathematical prospective. LP is a very strong tool but simple to use; hence, an LP-based approach will give to forecasters the opportunity to do accurate forecasts quickly and easily. In addition, the flexibility of LP can help analysts to deal with situations that other methods cannot deal with. The study consists of five parts where the parameters of forecasting models are estimated by using LP to minimise one or more accuracy (error) indices (sum of absolute deviations – SAD, sum of absolute percentage errors – SAPE, maximum absolute deviation – MaxAD, absolute differences between deviations – ADBD and absolute differences between percentage deviations – ADBPD). In order to test the accuracy of the approaches two samples of series from the M3 competition are used and the results are compared with traditional techniques that are found in the literature. In the first part simple LP is used to estimate the parameters of autoregressive based forecasting models by minimising one error index and they are compared with the method of the ordinary least squares (OLS minimises the sum of squared errors, SSE). The experiments show that the decision maker has to choose the best optimisation objective according to the characteristic of the series. In the second part, goal programming (GP) formulations are applied to similar models by minimising a combination of two accuracy indices. The experiments show that goal programming improves the performance of the single objective approaches. In the third part, several constraints to the initial simple LP and GP formulations are added to improve their performance on series with high randomness and their accuracy is compared with techniques that perform well on these series. The additional constraints improve the results and outperform all the other techniques. In the fourth part, simple LP and GP are used to combine forecasts. Eight simple individual techniques are combined and LP is compared with five traditional combination methods. The LP combinations outperform the other methods according to several performance indices. Finally, LP is used to estimate the parameters of autoregressive based models with optimisation objectives to minimise forecasting cost and it is compared them with the OLS. The experiments show that LP approaches perform better in terms of cost. The research shows that LP is a very useful tool that can be used to make accurate time series forecasts, which can outperform the traditional approaches that are found in forecasting literature and in practise.
32
GANDOLPHO, ANDRE ALVES. "METHODOLOGY FOR SOLVING FUZZY LINEAR PROGRAMMING PROBLEMS." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2005. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=8070@1.
Full textAbstract:
COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR<br>Esta tese propõe uma metodologia para obter uma solução
para problemas de programação linear fuzzy. A metodologia
aqui descrita apresenta um conjunto de soluções em que
tanto os valores das variáveis quanto o valor ótimo para a
função de custo, ou função objetivo, possuem uma faixa de
valores possíveis. Assim, é possível fornecer um conjunto
de soluções factíveis que atendam a diferentes cenários,
além de fornecer ao tomador de decisões uma ferramenta de
análise mais útil, permitindo que sejam analisadas outras
soluções possíveis antes de se escolher uma solução em
particular. O problema é resolvido de forma iterativa,
tornando mais simples e de fácil aplicação a metodologia
desenvolvida.<br>This work proposes an approach to obtain a solution to
linear fuzzy programming problems. The approach described
here presents a solution set in where both the variables
values and the cost function optimun value to have an
associated membership function. Thus, it is possible to
provided not only a feasible solution set applicable to
different scenarios but also to supply the decision maker
with a more powerful tool for the analysis of other
possible solutions. The problem is solved in an
interactive way, so that the developed is approach easily
applicable and simple to handle
33
Richards, Arthur George 1977. "Trajectory optimization using mixed-integer linear programming." Thesis, Massachusetts Institute of Technology, 2002. http://hdl.handle.net/1721.1/16873.
Full textAbstract:
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2002.<br>Includes bibliographical references (p. 121-129).<br>This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.<br>This thesis presents methods for finding optimal trajectories for vehicles subjected to avoidance and assignment requirements. The former include avoidance of collisions with obstacles or other vehicles and avoidance of thruster plumes from spacecraft. Assignment refers to the inclusion of decisions about terminal constraints in the optimization, such as assignment of waypoints to UAVs and the assignment of spacecraft to positions in a formation. These requirements lead to non-convex constraints and difficult optimizations. However, they can be formulated as mixed-integer linear programs (MILP) that can be solved for global optimality using powerful, commercial software. This thesis provides several extensions to previous work using MILP. The constraints for avoidance are extended to prevent plume impingement, which occurs when one spacecraft fire thrusters towards another. Methods are presented for efficient simplifications to complex problems, allowing solutions to be obtained in practical computation times. An approximation is developed to enable the inclusion of aircraft dynamics in a linear optimization, and also to include a general form of waypoint assignment suitable for UAV problems. Finally, these optimizations are used in model predictive control, running in real-time to incorporate feedback and compensate for uncertainty. Two major application areas are considered: spacecraft and aircraft. Spacecraft problems involve minimum fuel optimizations, and include ISS rendezvous and satellite cluster configuration. Aircraft problems are solved for minimum flight-time, or in the case of UAV problems with assignment, waypoint values and vehicle capabilities are included. Aircraft applications include air traffic management and coordination of autonomous UAVs. The results in this thesis provide a direct route to globally-optimal solutions of these non-convex trajectory optimizations.<br>by Arthur George Richards.<br>S.M.
34
Luo, Xiaodong. "Continuous linear programming : theory, algorithms and applications." Thesis, Massachusetts Institute of Technology, 1995. http://hdl.handle.net/1721.1/10591.
Full text
35
Feldman, Jon 1975. "Decoding error-correcting codes via linear programming." Thesis, Massachusetts Institute of Technology, 2003. http://hdl.handle.net/1721.1/42831.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003.<br>Includes bibliographical references (p. 147-151).<br>Error-correcting codes are fundamental tools used to transmit digital information over unreliable channels. Their study goes back to the work of Hamming [Ham50] and Shannon [Sha48], who used them as the basis for the field of information theory. The problem of decoding the original information up to the full error-correcting potential of the system is often very complex, especially for modern codes that approach the theoretical limits of the communication channel. In this thesis we investigate the application of linear programming (LP) relaxation to the problem of decoding an error-correcting code. Linear programming relaxation is a standard technique in approximation algorithms and operations research, and is central to the study of efficient algorithms to find good (albeit suboptimal) solutions to very difficult optimization problems. Our new "LP decoders" have tight combinatorial characterizations of decoding success that can be used to analyze error-correcting performance. Furthermore, LP decoders have the desirable (and rare) property that whenever they output a result, it is guaranteed to be the optimal result: the most likely (ML) information sent over the channel. We refer to this property as the ML certificate property. We provide specific LP decoders for two major families of codes: turbo codes and low-density parity-check (LDPC) codes. These codes have received a great deal of attention recently due to their unprecedented error-correcting performance.<br>(cont.) Our decoder is particularly attractive for analysis of these codes because the standard message-passing algorithms used for decoding are often difficult to analyze. For turbo codes, we give a relaxation very close to min-cost flow, and show that the success of the decoder depends on the costs in a certain residual graph. For the case of rate-1/2 repeat-accumulate codes (a certain type of turbo code), we give an inverse polynomial upper bound on the probability of decoding failure. For LDPC codes (or any binary linear code), we give a relaxation based on the factor graph representation of the code. We introduce the concept of fractional distance, which is a function of the relaxation, and show that LP decoding always corrects a number of errors up to half the fractional distance. We show that the fractional distance is exponential in the girth of the factor graph. Furthermore, we give an efficient algorithm to compute this fractional distance. We provide experiments showing that the performance of our decoders are comparable to the standard message-passing decoders. We also give new provably convergent message-passing decoders based on linear programming duality that have the ML certificate property.<br>by Jon Feldman.<br>Ph.D.
36
Cartis, Coralia. "On interior point methods for linear programming." Thesis, University of Cambridge, 2005. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.614693.
Full text
37
Planes, Francisco J. "Metabolic pathway analysis via integer linear programming." Thesis, Brunel University, 2008. http://bura.brunel.ac.uk/handle/2438/6134.
Full textAbstract:
The understanding of cellular metabolism has been an intriguing challenge in classical cellular biology for decades. Essentially, cellular metabolism can be viewed as a complex system of enzyme-catalysed biochemical reactions that produces the energy and material necessary for the maintenance of life. In modern biochemistry, it is well-known that these reactions group into metabolic pathways so as to accomplish a particular function in the cell. The identification of these metabolic pathways is a key step to fully understanding the metabolic capabilities of a given organism. Typically, metabolic pathways have been elucidated via experimentation on different organisms. However, experimental findings are generally limited and fail to provide a complete description of all pathways. For this reason it is important to have mathematical models that allow us to identify and analyze metabolic pathways in a computational fashion. This is precisely the main theme of this thesis. We firstly describe, review and discuss existent mathematical/computational approaches to metabolic pathways, namely stoichiometric and path finding approaches. Then, we present our initial mathematical model named the Beasley-Planes (BP) model, which significantly improves on previous stoichiometric approaches. We also illustrate a successful application of the BP model to optimally disrupt metabolic pathways. The main drawback of the BP model is that it needs as input extra pathway knowledge. This is especially inappropriate if we wish to detect unknown metabolic pathways. As opposed to the BP model and stoichoimetric approaches, this issue is not found in path finding approaches. For this reason a novel path finding approach is built and examined in detail. This analysis serves us as inspiration to build the Improved Beasley-Planes (IBP) model. The IBP model incorporates elements of both stoichometric and path finding approaches. Though somewhat less accurate than the BP model, the IBP model solves the issue of extra pathway knowledge. Our research clearly demonstrates that there is a significant chance of developing a mathematical optimisation model that underlies many/all metabolic pathways.
38
Koo, Karen. "Introduction of linear programming to construction management." Thesis, University of Manchester, 1997. https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.561290.
Full text
39
D'Ambrosio, Claudia <1980>. "Application-oriented Mixed Integer Non-Linear Programming." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2009. http://amsdottorato.unibo.it/1634/1/DAmbrosio_Claudia_tesi.pdf.
Full textAbstract:
In the most recent years there is a renovate interest for Mixed Integer Non-Linear Programming (MINLP) problems. This can be explained for different reasons: (i) the performance of solvers handling non-linear constraints was largely improved; (ii) the awareness that most of the applications from the real-world can be modeled as an MINLP problem; (iii) the challenging nature of this very general class of problems.
It is well-known that MINLP problems are NP-hard because they are the generalization of MILP problems, which are NP-hard themselves. However, MINLPs are, in general, also hard to solve in practice. We address to non-convex MINLPs, i.e. having non-convex continuous relaxations: the presence of non-convexities in the model makes these problems usually even harder to solve.
The aim of this Ph.D. thesis is to give a flavor of different possible approaches that one can study to attack MINLP problems with non-convexities, with a special attention to real-world problems. In Part 1 of the thesis we introduce the problem and present three special cases of general MINLPs and the most common methods used to solve them. These techniques play a fundamental role in the resolution of general MINLP problems. Then we describe algorithms addressing general MINLPs. Parts 2 and 3 contain the main contributions of the Ph.D. thesis. In particular, in Part 2 four different methods aimed at solving different classes of MINLP problems are presented. Part 3 of the thesis is devoted to real-world applications: two different problems and approaches to MINLPs are presented, namely Scheduling and Unit Commitment for Hydro-Plants and Water Network Design problems. The results show that each of these different methods has advantages and disadvantages. Thus, typically the method to be adopted to solve a real-world problem should be tailored on the characteristics, structure and size of the problem. Part 4 of the thesis consists of a brief review on tools commonly used for general MINLP problems, constituted an integral part of the development of this Ph.D. thesis (especially the use and development of open-source software).
We present the main characteristics of solvers for each special case of MINLP.
40
D'Ambrosio, Claudia <1980>. "Application-oriented Mixed Integer Non-Linear Programming." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2009. http://amsdottorato.unibo.it/1634/.
Full textAbstract:
In the most recent years there is a renovate interest for Mixed Integer Non-Linear Programming (MINLP) problems. This can be explained for different reasons: (i) the performance of solvers handling non-linear constraints was largely improved; (ii) the awareness that most of the applications from the real-world can be modeled as an MINLP problem; (iii) the challenging nature of this very general class of problems.
It is well-known that MINLP problems are NP-hard because they are the generalization of MILP problems, which are NP-hard themselves. However, MINLPs are, in general, also hard to solve in practice. We address to non-convex MINLPs, i.e. having non-convex continuous relaxations: the presence of non-convexities in the model makes these problems usually even harder to solve.
The aim of this Ph.D. thesis is to give a flavor of different possible approaches that one can study to attack MINLP problems with non-convexities, with a special attention to real-world problems. In Part 1 of the thesis we introduce the problem and present three special cases of general MINLPs and the most common methods used to solve them. These techniques play a fundamental role in the resolution of general MINLP problems. Then we describe algorithms addressing general MINLPs. Parts 2 and 3 contain the main contributions of the Ph.D. thesis. In particular, in Part 2 four different methods aimed at solving different classes of MINLP problems are presented. Part 3 of the thesis is devoted to real-world applications: two different problems and approaches to MINLPs are presented, namely Scheduling and Unit Commitment for Hydro-Plants and Water Network Design problems. The results show that each of these different methods has advantages and disadvantages. Thus, typically the method to be adopted to solve a real-world problem should be tailored on the characteristics, structure and size of the problem. Part 4 of the thesis consists of a brief review on tools commonly used for general MINLP problems, constituted an integral part of the development of this Ph.D. thesis (especially the use and development of open-source software).
We present the main characteristics of solvers for each special case of MINLP.
41
Ghosh, D. "Application of linear programming for feed formulation." Thesis, Central Marine Fisheries Research Institute, 2003. http://eprints.cmfri.org.in/11055/1/Dipankar%20Ghosh.pdf.
Full textAbstract:
The use of artificial feed balanced in protein, lipid,
carbohydrate, fibre, amino-acids, digestible energy, vitamins and
minerals is very essential in fish farming. In the formulation of feed it is necessary to determine exact optimum proportions of different feed ingredients, which meets the above nutritional requirements, to be mixed to produce a nutritionally well-balanced feed at the least possible cost.
42
Kumar, Manish. "Converting some global optimization problems to mixed integer linear problems using piecewise linear approximations." Diss., Rolla, Mo. : University of Missouri-Rolla, 2007. http://scholarsmine.umr.edu/thesis/pdf/Kumar_09007dcc803c8e68.pdf.
Full textAbstract:
Thesis (M.S.)--University of Missouri--Rolla, 2007.<br>Vita. The entire thesis text is included in file. Title from title screen of thesis/dissertation PDF file (viewed December 7, 2007) Includes bibliographical references (p. 28).
43
Steffy, Daniel E. "Topics in exact precision mathematical programming." Diss., Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/39639.
Full textAbstract:
The focus of this dissertation is the advancement of theory and computation related to exact precision mathematical programming. Optimization software based on floating-point arithmetic can return suboptimal or incorrect resulting because of round-off errors or the use of numerical tolerances. Exact or correct results are necessary for some applications. Implementing software entirely in rational arithmetic can be prohibitively slow. A viable alternative is the use of hybrid methods that use fast numerical computation to obtain approximate results that are then verified or corrected with safe or exact computation. We study fast methods for sparse exact rational linear algebra, which arises as a bottleneck when solving linear programming problems exactly. Output sensitive methods for exact linear algebra are studied. Finally, a new method for computing valid linear programming bounds is introduced and proven effective as a subroutine for solving mixed-integer linear programming problems exactly. Extensive computational results are presented for each topic.
44
Hadjiconstanti, Andriani. "Modelling support for the analysis of linear programming and mixed integer programming problems." Thesis, Brunel University, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.436478.
Full text
45
Magatão, Leandro. "Mixed integer linear programming and constraint logic programming : towards a unified modeling framework." Centro Federal de Educação Tecnológica do Paraná, 2005. http://repositorio.utfpr.edu.br/jspui/handle/1/86.
Full textAbstract:
The struggle to model and solve Combinatorial Optimization Problems (COPs) has challenged the development of new approaches to deal with COPs. In one of the front lines of such approaches, Operational Research (OR) and Constraint Programming (CP) optimization techniques are beginning to converge, despite their very different origins. More specifically, Mixed Integer Linear Programming (MILP) and Constraint Logic Programming (CLP) are at the confluence of the OR and the CP fields. This thesis summarizes and contrasts the essential characteristics of MILP and CLP, and the ways that they can be fruitfully combined. Chapters 1 to 3 sketch the intellectual background for recent efforts at integration and the main results achieved. In addition, these chapters highlight that CLP is known by its reach modeling framework, and the MILP modeling vocabulary is just based on inequalities, which makes the modeling process hard and error-prone. Therefore, a combined CLP-MILP approach suffers from this MILP inherited drawback. In chapter 4, this issue is addressed, and some "high-level" MILP modeling structures based on logical inference paradigms are proposed. These structures help the formulation of MILP models, and can be seen as a contribution towards a unifying modeling framework for a combined CLP-MILP approach. In addition, chapter 5 presents an MILP formulation addressing a combinatorial problem. This problem is focused on issues regarding the oil industry, more specifically, issues involving the scheduling of operational activities in a multi-product pipeline. Chapter 5 demonstrates the applicability of the high-level MILP modeling structures in a real-world scenario. Furthermore, chapter 6 presents a CLP-MILP formulation addressing the same scheduling problem previously exploited. This chapter demonstrates the applicability of the high-level MILP modeling structures in an integrated CLP-MILP modeling framework. The set of simulations conducted indicates that the combined CLP-MILP model was solved to optimality faster than either the MILP model or the CLP model. Thus, the CLP-MILP framework is a promising alternative to deal with the computational burden of this pipeline-scheduling problem. In essence, this thesis considers the integration of CLP and MILP in a modeling standpoint: it conveys the fundamentals of both techniques and the modeling features that help establish a combined CLP-MILP approach. Herein, the concentration is on the building of MILP and CLP-MILP models rather than on the solution process.
46
Wang, Xia. "Applications of genetic algorithms, dynamic programming, and linear programming to combinatorial optimization problems." College Park, Md.: University of Maryland, 2008. http://hdl.handle.net/1903/8778.
Full textAbstract:
Thesis (Ph. D.) -- University of Maryland, College Park, 2008.<br>Thesis research directed by: Applied Mathematics & Statistics, and Scientific Computation Program. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.
47
朱紫君 and Chi-kwan Chu. "Polynomial time algorithms for linear and integer programming." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2000. http://hub.hku.hk/bib/B31224301.
Full text
48
Chu, Chi-kwan. "Polynomial time algorithms for linear and integer programming." Hong Kong : University of Hong Kong, 2000. http://sunzi.lib.hku.hk/hkuto/record.jsp?B22718710.
Full text
49
Jayawardane, Ananda Kithsiri Wijenayaka. "Optimising earthmoving by linear programming and computer simulation." Thesis, Loughborough University, 1989. https://dspace.lboro.ac.uk/2134/31915.
Full textAbstract:
The accuracy of planning and estimating of earthmoving operations in any highway construction is important for both successful tendering and high profit margins. Mass-haul diagrams and experienced engineering judgement together with deterministic methods have been the key factors in planning and estimating earthmoving operations. Despite this, the limited use of Mass-haul diagrams and inaccuracy of deterministic estimates are well known. Although Stochastic and Linear Programming methods were developed to overcome some of these limitations, those available hitherto are relatively fundamental and are not bold enough to incorporate most real-life problems.
50
Salazar-Neumann, Martha. "Advances in robust combinatorial optimization and linear programming." Doctoral thesis, Universite Libre de Bruxelles, 2010. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210192.
Full textAbstract:
La construction de modèles qui protègent contre les incertitudes dans les données, telles que la variabilité de l'information et l'imprécision est une des principales préoccupations en optimisation sous incertitude. L'incertitude peut affecter différentes domaines, comme le transport, les télécommunications, la finance, etc. ainsi que les différentes parts d'un problème d'optimisation, comme les coefficients de la fonction objectif et /ou les contraintes. De plus, l'ensemble des données incertaines peut être modélisé de différentes façons, comme sous ensembles compactes et convexes de l´espace réel de dimension n, polytopes, produits Cartésiens des intervalles, ellipsoïdes, etc.<p><p>Une des approches possibles pour résoudre des tels problèmes est de considérer les versions minimax regret, pour lesquelles résoudre un problème sous incertitude revient à trouver une solution qui s'écarte le moins possible de la valeur solution optimale dans tout les cas. <p><p>Dans le cas des incertitudes définies par intervalles, les versions minimax regret de nombreux problèmes combinatoires polynomiaux sont NP-difficiles, d'ou l'importance d'essayer de réduire l'espace des solutions. Dans ce contexte, savoir quand un élément du problème, représenté par une variable, fait toujours ou jamais partie d'une solution optimal pour toute réalisation des données (variables 1-persistentes et 0-persistentes respectivement), constitue une manière de réduire la taille du problème. Un des principaux objectifs de cette thèse est d'étudier ces questions pour quelques problèmes d'optimisation combinatoire sous incertitude.<p><p>Nous étudions les versions minimax regret du problème du choix de p éléments parmi m, de l'arbre couvrant minimum et des deux problèmes de plus court chemin. Pour de tels problèmes, dans le cas des incertitudes définis par intervalles, nous étudions le problème de trouver les variables 1- et 0-persistentes. Nous présentons une procédure de pre-traitement du problème, lequel réduit grandement la taille des formulations des versions de minimax regret.<p><p>Nous nous intéressons aussi à la version minimax regret du problème de programmation linéaire dans le cas où les coefficients de la fonction objectif sont incertains et l'ensemble des données incertaines est polyédral. Dans le cas où l'ensemble des incertitudes est défini par des intervalles, le problème de trouver le regret maximum est NP-difficile. Nous présentons des cas spéciaux ou les problèmes de maximum regret et de minimax regret sont polynomiaux. Dans le cas où l´ensemble des incertitudes est défini par un polytope, nous présentons un algorithme pour trouver une solution exacte au problème de minimax regret et nous discutons les résultats numériques obtenus dans un grand nombre d´instances générées aléatoirement.<p><p>Nous étudions les relations entre le problème de 1-centre continu et la version minimax regret du problème de programmation linéaire dans le cas où les coefficients de la fonction objectif sont évalués à l´aide des intervalles. En particulier, nous décrivons la géométrie de ce dernier problème, nous généralisons quelques résultats en théorie de localisation et nous donnons des conditions sous lesquelles certaines variables peuvet être éliminées du problème. Finalement, nous testons ces conditions dans un nombre d´instances générées aléatoirement et nous donnons les conclusions.<br>Doctorat en sciences, Orientation recherche opérationnelle<br>info:eu-repo/semantics/nonPublished