Dissertations / Theses on the topic 'Integer programming'
To see the other types of publications on this topic, follow the link: Integer 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 'Integer 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
Achterberg, Tobias. "Constraint integer programming /." München : Verl. Dr. Hut, 2008. http://bvbr.bib-bvb.de:8991/F?func=service&doc_library=BVB01&doc_number=017108806&line_number=0001&func_code=DB_RECORDS&service_type=MEDIA.
2
Achterberg, Tobias. "Constraint integer programming." München Verl. Dr. Hut, 2007. http://d-nb.info/992163366/04.
3
Hewitt, Michael R. "Integer programming based search." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2009. http://hdl.handle.net/1853/31641.
Abstract:
Thesis (Ph.D)--Industrial and Systems Engineering, Georgia Institute of Technology, 2010.Committee Chair: Erera, Martin; Committee Chair: Nemhauser, George; Committee Chair: Savelsbergh, Martin; Committee Member: Ergun, Ozlem; Committee Member: Ferguson, Mark. Part of the SMARTech Electronic Thesis and Dissertation Collection.
4
Vigerske, Stefan. "Decomposition in multistage stochastic programming and a constraint integer programming approach to mixed-integer nonlinear programming." Doctoral thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, 2013. http://dx.doi.org/10.18452/16704.
Abstract:
Diese Arbeit leistet Beiträge zu zwei Gebieten der mathematischen Programmierung: stochastische Optimierung und gemischt-ganzzahlige nichtlineare Optimierung (MINLP). Im ersten Teil erweitern wir quantitative Stetigkeitsresultate für zweistufige stochastische gemischt-ganzzahlige lineare Programme auf Situationen in denen Unsicherheit gleichzeitig in den Kosten und der rechten Seite auftritt, geben eine ausführliche Übersicht zu Dekompositionsverfahren für zwei- und mehrstufige stochastische lineare und gemischt-ganzzahlig lineare Programme, und diskutieren Erweiterungen und Kombinationen des Nested Benders Dekompositionsverfahrens und des Nested Column Generationsverfahrens für mehrstufige stochastische lineare Programme die es erlauben die Vorteile sogenannter rekombinierender Szenariobäume auszunutzen. Als eine Anwendung dieses Verfahrens betrachten wir die optimale Zeit- und Investitionsplanung für ein regionales Energiesystem unter Einbeziehung von Windenergie und Energiespeichern. Im zweiten Teil geben wir eine ausführliche Übersicht zum Stand der Technik bzgl. Algorithmen und Lösern für MINLPs und zeigen dass einige dieser Algorithmen innerhalb des constraint integer programming Softwaresystems SCIP angewendet werden können. Letzteres erlaubt uns die Verwendung schon existierender Technologien für gemischt-ganzzahlige linear Programme und constraint Programme für den linearen und diskreten Teil des Problems. Folglich konzentrieren wir uns hauptsächlich auf die Behandlung der konvexen und nichtkonvexen nichtlinearen Nebenbedingungen mittels Variablenschrankenpropagierung, äußerer Approximation und Reformulierung. In einer ausführlichen numerischen Studie untersuchen wir die Leistung unseres Ansatzes anhand von Anwendungen aus der Tagebauplanung und des Aufbaus eines Wasserverteilungssystems und mittels verschiedener Vergleichstests. Die Ergebnisse zeigen, dass SCIP ein konkurrenzfähiger Löser für MINLPs geworden ist.This thesis contributes to two topics in mathematical programming: stochastic optimization and mixed-integer nonlinear programming (MINLP). In the first part, we extend quantitative continuity results for two-stage stochastic mixed-integer linear programs to include situations with simultaneous uncertainty in costs and right-hand side, give an extended review on decomposition algorithm for two- and multistage stochastic linear and mixed-integer linear programs, and discuss extensions and combinations of the Nested Benders Decomposition and Nested Column Generation methods for multistage stochastic linear programs to exploit the advantages of so-called recombining scenario trees. As an application of the latter, we consider the optimal scheduling and investment planning for a regional energy system including wind power and energy storages. In the second part, we give a comprehensive overview about the state-of-the-art in algorithms and solver technology for MINLPs and show that some of these algorithm can be applied within the constraint integer programming framework SCIP. The availability of the latter allows us to utilize the power of already existing mixed integer linear and constraint programming technologies to handle the linear and discrete parts of the problem. Thus, we focus mainly on the domain propagation, outer-approximation, and reformulation techniques to handle convex and nonconvex nonlinear constraints. In an extensive computational study, we investigate the performance of our approach on applications from open pit mine production scheduling and water distribution network design and on various benchmarks sets. The results show that SCIP has become a competitive solver for MINLPs.
5
Shmonin, Gennady. "Parameterised integer programming, integer cones, and related problems." [S.l.] : [s.n.], 2007. http://deposit.ddb.de/cgi-bin/dokserv?idn=985786132.
6
Espinoza, Daniel G. "On Linear Programming, Integer Programming and Cutting Planes." Diss., Georgia Institute of Technology, 2006. http://hdl.handle.net/1853/10482.
Abstract:
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.
7
Hooker, Kevin J. "Hypergraphs and integer programming polytopes /." Search for this dissertation online, 2005. http://wwwlib.umi.com/cr/ksu/main.
8
Chandrasekaran, Karthekeyan. "New approaches to integer programming." Diss., Georgia Institute of Technology, 2012. http://hdl.handle.net/1853/44814.
Abstract:
Integer Programming (IP) is a powerful and widely-used formulation for combinatorial problems. The study of IP over the past several decades has led to fascinating theoretical developments, and has improved our ability to solve discrete optimization problems arising in practice. This thesis makes progress on algorithmic solutions for IP by building on combinatorial, geometric and Linear Programming (LP) approaches.
We use a combinatorial approach to give an approximation algorithm for the feedback vertex set problem (FVS) in a recently developed Implicit Hitting Set framework. Our algorithm is a simple online algorithm which finds a nearly optimal FVS in random graphs. We also propose a planted model for FVS and show that an optimal hitting set for a polynomial number of subsets is sufficient to recover the planted subset.
Next, we present an unexplored geometric connection between integer feasibility and the classical notion of discrepancy of matrices. We exploit this connection to show a phase transition from infeasibility to feasibility in random IP instances. A recent algorithm for small discrepancy solutions leads to an efficient algorithm to find an integer point for random IP instances that are feasible with high probability.
Finally, we give a provably efficient implementation of a cutting-plane algorithm for perfect matchings. In our algorithm, cuts separating the current optimum are easy to derive while a small LP is solved to identify the cuts that are to be retained for later iterations. Our result gives a rigorous theoretical explanation for the practical efficiency of the cutting plane approach for perfect matching evident from implementations.
In summary, this thesis contributes to new models and connections, new algorithms and rigorous analysis of well-known approaches for IP.
9
Mefo, Kue Floriane. "Mixed integer bilevel programming problems." Doctoral thesis, Technische Universitaet Bergakademie Freiberg Universitaetsbibliothek "Georgius Agricola", 2017. http://nbn-resolving.de/urn:nbn:de:bsz:105-qucosa-230335.
Abstract:
This thesis presents the mixed integer bilevel programming problems where some optimality conditions and solution algorithms are derived. Bilevel programming problems are optimization problems which are partly constrained by another optimization problem.
The theoretical part of this dissertation is mainly based on the investigation of optimality conditions of mixed integer bilevel program. Taking into account both approaches (optimistic and pessimistic) which have been developed in the literature to deal with this type of problem, we derive some conditions for the existence of solutions. After that, we are able to discuss local optimality conditions using tools of variational analysis for each different approach. Moreover, bilevel optimization problems with semidefinite programming in the lower level are considered in order to formulate more optimality conditions for the mixed integer bilevel program. We end the thesis by developing some algorithms based on the theory presented
10
Evans, G. M. "Parallel and distributed integer programming." Thesis, University of East Anglia, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.267706.
11
Connard, Peter. "Mixed Integer Programming on transputers." Thesis, University of Warwick, 1992. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.359933.
12
De, Vries Tonny Tessa. "Irrigation scheduling with integer programming." Thesis, University of Southampton, 2003. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.273891.
13
Ginn, Isabella Brooke. "Integer Programming With Groebner Basis." VCU Scholars Compass, 2007. http://scholarscompass.vcu.edu/etd/769.
Abstract:
Integer Programming problems are difficult to solve. The goal is to find an optimal solution that minimizes cost. With the help of Groebner based algorithms the optimal solution can be found if it exists. The application of the Groebner based algorithm and how it works is the topic of research. The Algorithms are The Conti-Traverso Algorithm and the Original Conti-Traverso Algorithm. Examples are given as well as proofs that correspond to the algorithms. The latter algorithm is more efficient as well as user friendly. The algorithms are not necessarily the best way to solve and integer programming problem, but they do find the optimal solution if it exists.
14
Patel, Harsida. "Diet planning by goal programming and integer goal programming." Thesis, University of Portsmouth, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.286085.
15
Vielma, Centeno Juan Pablo. "Mixed integer programming approaches for nonlinear and stochastic programming." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2009. http://hdl.handle.net/1853/29624.
Abstract:
Thesis (Ph.D)--Industrial and Systems Engineering, Georgia Institute of Technology, 2010.Committee Chair: Nemhauser, George; Committee Co-Chair: Ahmed, Shabbir; Committee Member: Bill Cook; Committee Member: Gu, Zonghao; Committee Member: Johnson, Ellis. Part of the SMARTech Electronic Thesis and Dissertation Collection.
16
McAdoo, Michael John. "Three set inequalities in integer programming." Thesis, Manhattan, Kan. : Kansas State University, 2007. http://hdl.handle.net/2097/476.
17
Li, Yaxian. "Lower bounds for integer programming problems." Diss., Georgia Institute of Technology, 2013. http://hdl.handle.net/1853/48959.
Abstract:
Solving real world problems with mixed integer programming (MIP) involves efforts in modeling and efficient algorithms. To solve a minimization MIP problem, a lower bound is needed in a branch-and-bound algorithm to evaluate the quality of a feasible solution and to improve the efficiency of the algorithm. This thesis develops a new MIP model and studies algorithms for obtaining lower bounds for MIP.
The first part of the thesis is dedicated to a new production planning model with pricing decisions. To increase profit, a company can use pricing to influence its demand to increase revenue, decrease cost, or both. We present a model that uses pricing discounts to increase production and delivery flexibility, which helps to decrease costs. Although the revenue can be hurt by introducing pricing discounts, the total profit can be increased by properly choosing the discounts and production and delivery decisions. We further explore the idea with variations of the model and present the advantages of using flexibility to increase profit.
The second part of the thesis focuses on solving integer programming(IP) problems by improving lower bounds. Specifically, we consider obtaining lower bounds for the multi- dimensional knapsack problem (MKP). Because MKP lacks special structures, it allows us to consider general methods for obtaining lower bounds for IP, which includes various relaxation algorithms. A problem relaxation is achieved by either enlarging the feasible region, or decreasing the value of the objective function on the feasible region. In addition, dual algorithms can also be used to obtain lower bounds, which work directly on solving the dual problems.
We first present some characteristics of the value function of MKP and extend some properties from the knapsack problem to MKP. The properties of MKP allow some large scale problems to be reduced to smaller ones. In addition, the quality of corner relaxation bounds of MKP is considered. We explore conditions under which the corner relaxation is
tight for MKP, such that relaxing some of the constraints does not affect the quality of the lower bounds. To evaluate the overall tightness of the corner relaxation, we also show the worst-case gap of the corner relaxation for MKP.
To identify parameters that contribute the most to the hardness of MKP and further evaluate the quality of lower bounds obtained from various algorithms, we analyze the characteristics that impact the hardness of MKP with a series of computational tests and establish a testbed of instances for computational experiments in the thesis.
Next, we examine the lower bounds obtained from various relaxation algorithms com- putationally. We study methods of choosing constraints for relaxations that produce high- quality lower bounds. We use information obtained from linear relaxations to choose con- straints to relax. However, for many hard instances, choosing the right constraints can be challenging, due to the inaccuracy of the LP information. We thus develop a dual heuristic algorithm that explores various constraints to be used in relaxations in the Branch-and- Bound algorithm. The algorithm uses lower bounds obtained from surrogate relaxations to improve the LP bounds, where the relaxed constraints may vary for different nodes. We also examine adaptively controlling the parameters of the algorithm to improve the performance.
Finally, the thesis presents two problem-specific algorithms to obtain lower bounds for MKP: A subadditive lifting method is developed to construct subadditive dual solutions, which always provide valid lower bounds. In addition, since MKP can be reformulated as a shortest path problem, we present a shortest path algorithm that uses estimated distances by solving relaxations problems. The recursive structure of the graph is used to accelerate the algorithm. Computational results of the shortest path algorithm are given on the testbed instances.
18
Tjandraatmadja, Christian. "Decision Diagram Relaxations for Integer Programming." Research Showcase @ CMU, 2018. http://repository.cmu.edu/dissertations/1194.
Abstract:
Mixed-integer programming (MIP) is often a practitioner’s primary approach when tackling hard discrete optimization problems. This important role was enabled by decades of theory and practical experience poured into modern MIP solvers. However, many problems are still challenging for MIP solvers, which motivates the need for novel perspectives to enhance MIP technology. In this dissertation, we explore the use of relaxed decision diagrams to improve MIP solvers. Relaxed decision diagrams are graph structures that encode relaxations of discrete optimization problems. One of their many uses in optimization is to generate bounds on the optimal value, which are strong in practice in the presence of certain types of structure. However, exporting decision diagram techniques to integer programming can be challenging due to the lack of clear structure to exploit. A first step is to develop methods to construct good relaxed decision diagrams from integer programming models. We propose a framework that focuses on a substructure of the problem and incorporates remaining constraints via Lagrangian relaxation and constraint propagation. In particular, we explore the use of a prevalent substructure in MIP solvers known as the conflict graph. Computational experiments indicate that they yield strong bounds under this framework. Once we understand how to build good relaxed decision diagrams, the next question is how to apply them in the context of a MIP solver. A MIP solver has several components, which include presolve, cutting planes, primal heuristics, and branch-and-bound. We show how relaxed decision diagrams can aid each of these components throughout the subsequent chapters. In particular, we view decision diagrams from a polyhedral perspective in order to generate cutting planes. Through a connection between decision diagrams and polarity, we develop an algorithm that generates cuts that are facet-defining for the convex hull of a decision diagram relaxation. We provide computational evidence that this algorithm generates strong cuts for structured problems. Finally, we investigate a broader integration of decision diagrams into MIP solvers. First, we show how relaxed decision diagrams can be used for bound and coefficient strengthening in the presolve step of a MIP solver. Second, we investigate the effect of applying cuts from decision diagrams throughout a branch-and-bound tree. Third, we generate both primal and dual bounds from decision diagrams to improve pruning within a branch-and-bound tree, which can result in significant improvements in solving time.
19
Zanette, Arrigo. "Three Topics in Mixed Integer Programming." Doctoral thesis, Università degli studi di Padova, 2009. http://hdl.handle.net/11577/3425623.
Abstract:
In chapter entitled "Lexicography and degeneracy: Can a pure cutting plane algorithm work?", we discuss an implementation of the lexicographic version of Gomory's fractional cutting plane method for Integer Linear Programming (ILP) problems and of two heuristics mimicking the latter. In computational testing on a battery of MIPLIB problems we compare the performance of these variants with that of the standard Gomory algorithm, both in the single-cut and in the multi-cut (rounds of cuts) version, and show that they provide a radical improvement over the standard procedure. In particular, we report the exact solution of ILP instances from MIPLIB such as stein15, stein27, and bm23, for which the standard Gomory cutting plane algorithm is not able to close more than a tiny fraction of the integrality gap. We also offer an explanation for this surprising phenomenon.
In chapter entitled "Minimal Infeasible Subsystems and Benders cuts", taking inspiration from general cutting plane methods for MIP, we propose alternative selection criteria for Benders cuts, and analyze them computationally. Our approach is based on the correspondence between minimal infeasible subsystems of an infeasible Linear Program, and the vertices of the so-called alternative polyhedron. The choice of the "most effective" violated Benders cut then corresponds to the selection of a suitable vertex of the alternative polyhedron, hence a clever choice of the dual objective function is crucial--whereas the textbook Benders approach uses a completely random selection policy, at least when the so-called feasibility cuts are generated. Computational results on a testbed of MIPLIB instances are presented. We show that the proposed methods allow for a speedup of 1 to 2 orders of magnitude with respect to a textbook implementation.
In chapter entitled "Fast Approaches to Improve the Robustness of a Railway Timetable", we address the problem of finding a robust train timetable. The Train Timetabling Problem (TTP) consists in finding a train schedule on a railway network that satisfies some operational
constraints and maximizes some profit function which counts for the efficiency of the infrastructure usage. In practical cases, however, the maximization of the objective function is not enough and one calls for a robust solution that is capable of absorbing as much as possible delays/disturbances on the network. We propose and analyze computationally four different methods to improve the robustness of a given TTP solution. The approaches combine Linear Programming (LP) and ad-hoc Stochastic Programming/Robust Optimization techniques. The computational results on real-world instances show that two of the proposed techniques are very fast and provide robust solutions of comparable quality with respect to the standard (but very time consuming) Stochastic Programming approach.Nel presente lavoro di tesi descriviamo i nostri contributi su tre argomenti di Mixed Integer Programming (MIP). Nel capitolo intitolato "Lexicography and degeneracy: Can a pure cutting plane algorithm work?" discutiamo una implementazione della versione lessicografica del metodo dei piani di taglio di Gomory per problemi di Integer Linear Programming (ILP) e due euristiche. Nei test computazionali su una batteria di istanze della libreria MIPLIB confrontiamo la performance dei metodi implementati col l'algoritmo standard di Gomory, sia nella versione a singolo taglio che nella versione multi taglio (round di tagli), e mostriamo che le nostre implementazioni producono un miglioramento radicale sulla procedura standard. In particolare riportiamo la soluzione esatta di istanze ILP come stein15, stein27 e bm23, per le quali l'algoritmo standard di Gomory non è in grado di chiudere se non una piccola frazione del gap di integralità. Inoltre forniamo un'interpretazione di questo sorprendente fenomeno. Nel capitolo intitolato "Minimal Infeasible Subsystems and Benders cuts", prendendo ispirazione dai metodi cutting plane generalmente usati in MIP, proponiamo nuovi criteri di selezione per i tagli di Benders, e li analizziamo computazionalmente. Il nostro approccio si basa sulla corrispondenza tra sistemi minimamente infeasible di un problema lineare infeasible, e i vertici del così detto poliedro delle alternative. La scelta del taglio di Benders violato "più efficace" corrisponde quindi alla selezione di un vertice opportuno nel poliedro delle alternative, da cui segue che è cruciale una scelta intelligente della funzione obiettivo duale--mentre l'approccio di Benders textbook usa una politica di scelta completamente casuale. Nei test computazionali mostriamo che il metodo proposto consente uno speedup da 1 a 2 ordini di grandezza rispetto all'implementazione textbook. Nel capitolo intitolato "Fast Approaches to Improve the Robustness of a Railway Timetable", ci occupiamo del problema di trovare una tabella oraria robusta in ambito ferroviario. Il Train Timetabling Problem (TTP) consiste nel trovare uno schedule dei treni di una rete ferroviaria che soddisfi dei vincoli operativi e massimizzi una funzione di profitto che stimi l'efficienza dell'uso dell'infrastruttura. Tuttavia la massimizzazione della funzione obiettivo può non essere sufficiente e si può voler trovare una soluzione robusta, ovvero capace di assorbire il più possibile i ritardi/disturbi sulla rete. A tal fine, proponiamo e analizziamo computazionalmente quattro diversi metodi per migliorare la robustezza di una data soluzione di TTP. Gli approcci combinano Programmazione Lineare e tecniche ad-hoc di Stochastic Programming/Robust Optimization. I risultati computazionali su istanze reali mostrano che due delle tecniche proposte sono molto veloci e forniscono soluzioni robuste di qualità comparabile con un approccio di Stochastic Programming standard ma computazionalmente molto più oneroso.
20
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.
21
Wang, Guanglei. "Relaxations in mixed-integer quadratically constrained programming and robust programming." Thesis, Evry, Institut national des télécommunications, 2016. http://www.theses.fr/2016TELE0026/document.
Abstract:
De nombreux problèmes de la vie réelle sont exprimés sous la forme de décisions à prendre à l’aide de l’information accessible dans le but d’atteindre certains objectifs. La programmation numérique a prouvé être un outil efficace pour modéliser et résoudre une grande variété de problèmes de ce type. Cependant, de nombreux problèmes en apparence faciles sont encore durs à résoudre. Et même des problèmes faciles de programmation linéaire deviennent durs avec l’incertitude de l’information disponible. Motivés par un problème de télécommunication où l’on doit associer des machines virtuelles à des serveurs tout en minimisant les coûts, nous avons employé plusieurs outils de programmation mathématique dans le but de résoudre efficacement le problème, et développé de nouveaux outils pour des problèmes plus généraux. Dans l’ensemble, résumons les principaux résultats de cette thèse comme suit. Une formulation exacte et plusieurs reformulations pour le problème d’affectation de machines virtuelles dans le cloud sont données. Nous utilisons plusieurs inégalités valides pour renforcer la formulation exacte, accélérant ainsi l’algorithme de résolution de manière significative. Nous donnons en outre un résultat géométrique sur la qualité de la borne lagrangienne montrant qu’elle est généralement beaucoup plus forte que la borne de la relaxation continue. Une hiérarchie de relaxation est également proposée en considérant une séquence de couverture de l’ensemble de la demande. Ensuite, nous introduisons une nouvelle formulation induite par les symétries du problème. Cette formulation permet de réduire considérablement le nombre de termes bilinéaires dans le modèle, et comme prévu, semble plus efficace que les modèles précédents. Deux approches sont développées pour la construction d’enveloppes convexes et concaves pour l’optimisation bilinéaire sur un hypercube. Nous établissons plusieurs connexions théoriques entre différentes techniques et nous discutons d’autres extensions possibles. Nous montrons que deux variantes de formulations pour approcher l’enveloppe convexe des fonctions bilinéaires sont équivalentes. Nous introduisons un nouveau paradigme sur les problèmes linéaires généraux avec des paramètres incertains. Nous proposons une hiérarchie convergente de problèmes d’optimisation robuste – approche robuste multipolaire, qui généralise les notions de robustesse statique, de robustesse d’affinement ajustable, et de robustesse entièrement ajustable. En outre, nous montrons que l’approche multipolaire peut générer une séquence de bornes supérieures et une séquence de bornes inférieures en même temps et les deux séquences convergent vers la valeur robuste des FARC sous certaines hypothèses modéréesMany real life problems are characterized by making decisions with current information to achieve certain objectives. Mathematical programming has been developed as a successful tool to model and solve a wide range of such problems. However, many seemingly easy problems remain challenging. And some easy problems such as linear programs can be difficult in the face of uncertainty. Motivated by a telecommunication problem where assignment decisions have to be made such that the cloud virtual machines are assigned to servers in a minimum-cost way, we employ several mathematical programming tools to solve the problem efficiently and develop new tools for general theoretical problems. In brief, our work can be summarized as follows. We provide an exact formulation and several reformulations on the cloud virtual machine assignment problem. Then several valid inequalities are used to strengthen the exact formulation, thereby accelerating the solution procedure significantly. In addition, an effective Lagrangian decomposition is proposed. We show that, the bounds providedby the proposed Lagrangian decomposition is strong, both theoretically and numerically. Finally, a symmetry-induced model is proposed which may reduce a large number of bilinear terms in some special cases. Motivated by the virtual machine assignment problem, we also investigate a couple of general methods on the approximation of convex and concave envelopes for bilinear optimization over a hypercube. We establish several theoretical connections between different techniques and prove the equivalence of two seeming different relaxed formulations. An interesting research direction is also discussed. To address issues of uncertainty, a novel paradigm on general linear problems with uncertain parameters are proposed. This paradigm, termed as multipolar robust optimization, generalizes notions of static robustness, affinely adjustable robustness, fully adjustable robustness and fills the gaps in-between. As consequences of this new paradigms, several known results are implied. Further, we prove that the multipolar approach can generate a sequence of upper bounds and a sequence of lower bounds at the same time and both sequences converge to the robust value of fully adjustable robust counterpart under some mild assumptions
22
Wang, Guanglei. "Relaxations in mixed-integer quadratically constrained programming and robust programming." Electronic Thesis or Diss., Evry, Institut national des télécommunications, 2016. http://www.theses.fr/2016TELE0026.
Abstract:
De nombreux problèmes de la vie réelle sont exprimés sous la forme de décisions à prendre à l’aide de l’information accessible dans le but d’atteindre certains objectifs. La programmation numérique a prouvé être un outil efficace pour modéliser et résoudre une grande variété de problèmes de ce type. Cependant, de nombreux problèmes en apparence faciles sont encore durs à résoudre. Et même des problèmes faciles de programmation linéaire deviennent durs avec l’incertitude de l’information disponible. Motivés par un problème de télécommunication où l’on doit associer des machines virtuelles à des serveurs tout en minimisant les coûts, nous avons employé plusieurs outils de programmation mathématique dans le but de résoudre efficacement le problème, et développé de nouveaux outils pour des problèmes plus généraux. Dans l’ensemble, résumons les principaux résultats de cette thèse comme suit. Une formulation exacte et plusieurs reformulations pour le problème d’affectation de machines virtuelles dans le cloud sont données. Nous utilisons plusieurs inégalités valides pour renforcer la formulation exacte, accélérant ainsi l’algorithme de résolution de manière significative. Nous donnons en outre un résultat géométrique sur la qualité de la borne lagrangienne montrant qu’elle est généralement beaucoup plus forte que la borne de la relaxation continue. Une hiérarchie de relaxation est également proposée en considérant une séquence de couverture de l’ensemble de la demande. Ensuite, nous introduisons une nouvelle formulation induite par les symétries du problème. Cette formulation permet de réduire considérablement le nombre de termes bilinéaires dans le modèle, et comme prévu, semble plus efficace que les modèles précédents. Deux approches sont développées pour la construction d’enveloppes convexes et concaves pour l’optimisation bilinéaire sur un hypercube. Nous établissons plusieurs connexions théoriques entre différentes techniques et nous discutons d’autres extensions possibles. Nous montrons que deux variantes de formulations pour approcher l’enveloppe convexe des fonctions bilinéaires sont équivalentes. Nous introduisons un nouveau paradigme sur les problèmes linéaires généraux avec des paramètres incertains. Nous proposons une hiérarchie convergente de problèmes d’optimisation robuste – approche robuste multipolaire, qui généralise les notions de robustesse statique, de robustesse d’affinement ajustable, et de robustesse entièrement ajustable. En outre, nous montrons que l’approche multipolaire peut générer une séquence de bornes supérieures et une séquence de bornes inférieures en même temps et les deux séquences convergent vers la valeur robuste des FARC sous certaines hypothèses modéréesMany real life problems are characterized by making decisions with current information to achieve certain objectives. Mathematical programming has been developed as a successful tool to model and solve a wide range of such problems. However, many seemingly easy problems remain challenging. And some easy problems such as linear programs can be difficult in the face of uncertainty. Motivated by a telecommunication problem where assignment decisions have to be made such that the cloud virtual machines are assigned to servers in a minimum-cost way, we employ several mathematical programming tools to solve the problem efficiently and develop new tools for general theoretical problems. In brief, our work can be summarized as follows. We provide an exact formulation and several reformulations on the cloud virtual machine assignment problem. Then several valid inequalities are used to strengthen the exact formulation, thereby accelerating the solution procedure significantly. In addition, an effective Lagrangian decomposition is proposed. We show that, the bounds providedby the proposed Lagrangian decomposition is strong, both theoretically and numerically. Finally, a symmetry-induced model is proposed which may reduce a large number of bilinear terms in some special cases. Motivated by the virtual machine assignment problem, we also investigate a couple of general methods on the approximation of convex and concave envelopes for bilinear optimization over a hypercube. We establish several theoretical connections between different techniques and prove the equivalence of two seeming different relaxed formulations. An interesting research direction is also discussed. To address issues of uncertainty, a novel paradigm on general linear problems with uncertain parameters are proposed. This paradigm, termed as multipolar robust optimization, generalizes notions of static robustness, affinely adjustable robustness, fully adjustable robustness and fills the gaps in-between. As consequences of this new paradigms, several known results are implied. Further, we prove that the multipolar approach can generate a sequence of upper bounds and a sequence of lower bounds at the same time and both sequences converge to the robust value of fully adjustable robust counterpart under some mild assumptions
23
Mirrazavi, Seyed Keyvan. "Investigation and development of efficient integer and integer goal programming systems." Thesis, University of Portsmouth, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.299475.
24
Detar, Paul J. "Scheduling Marine Corps entry-level MOS schools." Thesis, Monterey, Calif. : Springfield, Va. : Naval Postgraduate School ; Available from National Technical Information Service, 2004. http://library.nps.navy.mil/uhtbin/hyperion/04Sept%5FDetar.pdf.
25
Easton, Kelly King. "Using integer programming and constraint programming to solve sports scheduling problems." Diss., Georgia Institute of Technology, 2002. http://hdl.handle.net/1853/25795.
26
Strauss, Aaron B. 1980. "Applying integer programming techniques to find minimum integer weights of voting games." Thesis, Massachusetts Institute of Technology, 2003. http://hdl.handle.net/1721.1/18019.
Abstract:
Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003.Includes bibliographical references (p. 73-76).
Using concepts from computer science and mathematics I develop three algorithms to find the minimum integer weights for voting games. Games with up to at least 17 players can be solved in a reasonable amount of time. First, coalitions are mapped to constraints, reducing the problem to constraint optimization. The optimization techniques used are Gomory's all-integer simplex algorithm and a variant of the popular integer programming method branch and bound. Theoretical results include that minimum integer weights are not unique and a confirmation of a prior result that minimum integer weights are proportional to a priori seat share. Thus, these algorithms can be useful for researchers evaluating the differences between proportional bargaining models and formateur models. The running times of the different algorithms are contrasted and analyzed for potential improvements.
by Aaron B. Strauss.
M.Eng.
27
Kästner, Daniel. "Retargetable postpass optimisation by integer linear programming." [S.l.] : [s.n.], 2000. http://deposit.ddb.de/cgi-bin/dokserv?idn=972330917.
28
Chen, Kenneth. "Topics in group methods for integer programming." Diss., Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/41133.
Abstract:
In 2003, Gomory and Johnson gave two different three-slope T-space
facet constructions, both of which shared a slope with the corresponding
Gomory mixed-integer cut. We give a new three-slope facet
which is independent of the GMIC and also give a four-slope
T-space facet construction, which to our knowledge, is the first
four-slope construction.
We describe an enumerative framework for the discovery of T-space
facets.
Using an algorithm by Harvey for computing integer hulls in the
plane, we give a heuristic for quickly computing lattice-free
triangles.
Given two rows of the tableau, we derive how to exactly calculate
lattice-free triangles and quadrilaterals in the plane which can be
used to derive facet-defining inequalities of the integer hull.
We then present computational results using these derivations where
non-basic integer variables are strengthened using Balas-Jeroslow lifting.
29
Ulusal, Elif. "Integer programming models for the branchwidth problem." Diss., Texas A&M University, 2008. http://hdl.handle.net/1969.1/85936.
Abstract:
We consider the problem of computing the branchwidth and an optimal branch decomposition
of a graph. Branch decompositions and branchwidth were introduced in
1991 by Robertson and Seymour and were used in the proof of Graph Minors Theorem
(GMT), a well known conjecture (Wagner's conjecture) in graph theory. The
notions of branchwidth and branch decompositions have been proved to be useful for
solving many NP-hard problems that have applications in fields such as graph theory,
network design, sensor networks and biology. Branch decompositions have been
utilized for problems such as the traveling salesman problem by Cook and Seymour,
general minor containment and the branchwidth problem by Hicks by means of the
relevant branch decomposition-based algorithms.
Branch decomposition-based algorithms are fixed parameter tractable algorithms
obtained by combining dynamic programming techniques with branch decompositions.
The running time and space of these algorithms strongly depend on the width
of the utilized branch decomposition. Thus, finding optimal or close to optimal branch
decompositions is very important for the efficiency of the branch decomposition-based
algorithms. Motivated by the vastness of the fields of application, we aim to increase
the efficiency of the branch decomposition-based algorithms by investigating effective techniques to find optimal branch decompositions.
We present three integer programming models for the branchwidth problem.
Two similar formulations are based on the relationship of branchwidth problem with
a special case of the Steiner tree packing problem. The third formulation is based on
the notion of laminar separations. We utilize upper and lower bounds obtained by
heuristic algorithms, reduction techniques and cutting planes to increase the efficiency
of our models. We use all three models for the branchwidth problem on hypergraphs as
well. We compare the performance of three models both on graphs and hypergraphs.
Furthermore we use the third model for rank-width problem and also offer a
heuristic for finding good rank decompositions. We provide computational results for
this problem, which can be a basis of comparison for future formulations.
30
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.
31
Bogart, Tristram. "Problems in computational algebra and integer programming /." Thesis, Connect to this title online; UW restricted, 2007. http://hdl.handle.net/1773/5805.
32
Axehill, Daniel. "Integer quadratic programming for control and communcation /." Linköping : Department of Electrical Engineering, Linköping University, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-10642.
33
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.
Abstract:
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.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.
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.
34
AMORIM, RAFAEL FREITAS DE. "INTEGER PROGRAMMING PROBLEMS ON TELECOMMUNICATIONS OPTICAL NETWORKS." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2006. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=8796@1.
Abstract:
COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIORImpulsionadas pelo crescimento do mercado corporativo e pela prestação de serviços para grandes clientes, as operadoras de serviços de telecomunicação estão buscando processos automatizados e redução de custo no desenvolvimento de novos projetos de redes de telecomunicações. Nesse cenário, dois modelos de Programação Inteira são apresentados buscando uma minimização de custos. O primeiro para o problema de planejamento de novas redes. E segundo para o problema de configuração de trails nas redes SDH. Uma introdução sobre meios de transmissão, redes de telecomunicações, topologias mais utilizadas e sistemas de proteção são apresentados. Por fim, em ambos problemas, são apresentados estudos comparativos com situações reais, com o intuito de validar os modelos.
Stimulated by the growth of the corporate market and by the services dedicated to big customers, providers are searching for, even more nowadays, automated process and cost reduction on the development of new telecommunications networks projects. In that setting, two models of Integer Programming will be presented, seeking a minimization of costs. At first, for the problem of planning of new networks, and second for the problem of configuration of trails in the SDH networks. Beyond that, an introduction about transmission lines, networks of communication, topology more utilized and systems of protection will be presented. In both problems, comparing real situations, with the purpose of validate the models.
35
Richards, Arthur George 1977. "Trajectory optimization using mixed-integer linear programming." Thesis, Massachusetts Institute of Technology, 2002. http://hdl.handle.net/1721.1/16873.
Abstract:
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2002.Includes bibliographical references (p. 121-129).
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
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.
by Arthur George Richards.
S.M.
36
Axehill, Daniel. "Integer Quadratic Programming for Control and Communication." Doctoral thesis, Linköpings universitet, Reglerteknik, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-10642.
Abstract:
The main topic of this thesis is integer quadratic programming with applications to problems arising in the areas of automatic control and communication. One of the most widespread modern control methods is Model Predictive Control (MPC). In each sampling time, MPC requires the solution of a Quadratic Programming (QP) problem. To be able to use MPC for large systems, and at high sampling rates, optimization routines tailored for MPC are used. In recent years, the range of application of MPC has been extended to so-called hybrid systems. Hybrid systems are systems where continuous dynamics interact with logic. When this extension is made, binary variables are introduced in the problem. As a consequence, the QP problem has to be replaced by a far more challenging Mixed Integer Quadratic Programming (MIQP) problem, which is known to have a computational complexity which grows exponentially in the number of binary optimization variables. In modern communication systems, multiple users share a so-called multi-access channel. To estimate the information originally sent, a maximum likelihood problem involving binary variables can be solved. The process of simultaneously estimating the information sent by multiple users is called Multiuser Detection (MUD). In this thesis, the problem to efficiently solve MIQP problems originating from MPC and MUD is addressed. Four different algorithms are presented. First, a polynomial complexity preprocessing algorithm for binary quadratic programming problems is presented. By using the algorithm, some, or all, binary variables can be computed efficiently already in the preprocessing phase. In numerical experiments, the algorithm is applied to unconstrained MPC problems with a mixture of real valued and binary valued control signals, and the result shows that the performance gain can be significant compared to solving the problem using branch and bound. The preprocessing algorithm has also been applied to the MUD problem, where simulations have shown that the bit error rate can be significantly reduced compared to using common suboptimal algorithms. Second, an MIQP algorithm tailored for MPC is presented. The algorithm uses a branch and bound method where the relaxed node problems are solved by a dual active set QP algorithm. In this QP algorithm, the KKT systems are solved using Riccati recursions in order to decrease the computational complexity. Simulation results show that both the proposed QP solver and MIQP solver have lower computational complexity compared to corresponding generic solvers. Third, the dual active set QP algorithm is enhanced using ideas from gradient projection methods. The performance of this enhanced algorithm is shown to be comparable with the existing commercial state-of-the-art QP solver \cplex for some random linear MPC problems. Fourth, an algorithm for efficient computation of the search directions in an SDP solver for a proposed alternative SDP relaxation applicable to MPC problems with binary control signals is presented. The SDP relaxation considered has the potential to give a tighter lower bound on the optimal objective function value compared to the QP relaxation that is traditionally used in branch and bound for these problems, and its computational performance is better than the ordinary SDP relaxation for the problem. Furthermore, the tightness of the different relaxations is investigated both theoretically and in numerical experiments.This material is posted here with permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of the Linköping University's products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to pubs-permissions@ieee.org. By choosing to view this material, you agree to all provisions of the copyright laws protecting it.
37
Council, Steven Michael. "A 'satisfiability' based approach to integer programming." Thesis, University of Southampton, 1999. https://eprints.soton.ac.uk/50600/.
Abstract:
The purpose of this work is the development of a collection of satisfiability based algorithms that can be used to solve particular instances of integer programming problems. Satisfiability based algorithms have recently obtained a strong standing within the industrial community and, although for all but a few special cases the problem is NP-complete, research has shown that other problems in this class can often be transformed into a corresponding satisfiability problem and solved more effectively using the best SAT-solvers. One of the most important uses of satisfiability based algorithms is within chip design testing, such as the floating point failure of Pentium processors which require the need of efficient satisfiability based tools to aid in the verification process. We start with the case of Pure 0-1 Integer Programming problems and show how they can be transformed into a general satisfiability problem and solved using an algorithm developed by Davis, Putnam and Loveland. The thesis then concerns itself with making the process as efficient as possible by adopting a number of approaches that include the implementation of polynomial time algorithms including 'Incremental Satisfiability', allowing flexibility to add new branching strategies and the conversion of constraints to logical clauses. The programs are compiled to interact with each other fully and are tested on the 'truss design problem' found in structural engineering.
38
Liu, Xiao. "Integer Programming Approaches to Risk-Averse Optimization." The Ohio State University, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=osu1480461192784862.
39
Planes, Francisco J. "Metabolic pathway analysis via integer linear programming." Thesis, Brunel University, 2008. http://bura.brunel.ac.uk/handle/2438/6134.
Abstract:
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.
40
Tural, Mustafa Kemal Lu Shu. "Topics in basis reduction and integer programming." Chapel Hill, N.C. : University of North Carolina at Chapel Hill, 2009. http://dc.lib.unc.edu/u?/etd,2521.
Abstract:
Thesis (Ph. D.)--University of North Carolina at Chapel Hill, 2009.Title from electronic title page (viewed Oct. 5, 2009). "... in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the Department of Statistics and Operations Research." Discipline: Statistics and Operations Research; Department/School: Statistics and Operations Research.
41
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.
Abstract:
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.
42
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/.
Abstract:
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.
43
Angulo, Olivares Gustavo I. "Integer programming approaches for semicontinuous and stochastic optimization." Diss., Georgia Institute of Technology, 2014. http://hdl.handle.net/1853/51862.
Abstract:
This thesis concerns the application of mixed-integer programming techniques to solve special classes of network flow problems and stochastic integer programs. We draw tools from complexity and polyhedral theory to analyze these problems and propose improved solution methods. In the first part, we consider semi-continuous network flow problems, that is, a class of network flow problems where some of the variables are required to take values above a prespecified minimum threshold whenever they are not zero. These problems find applications in management and supply chain models where orders in small quantities are undesirable. We introduce the semi-continuous inflow set with variable upper bounds as a relaxation of general semi-continuous network flow problems. Two particular cases of this set are considered, for which we present complete descriptions of the convex hull in terms of linear inequalities and extended formulations. We also consider a class of semi-continuous transportation problems where inflow systems arise as substructures, for which we investigate complexity questions. Finally, we study the computational efficacy of the developed polyhedral results in solving randomly generated instances of semi-continuous transportation problems. In the second part, we introduce and study the forbidden-vertices problem. Given a polytope P and a subset X of its vertices, we study the complexity of optimizing a linear function on the subset of vertices of P that are not contained in X. This problem is closely related to finding the k-best basic solutions to a linear problem and finds applications in stochastic integer programming. We observe that the complexity of the problem depends on how P and X are specified. For instance, P can be explicitly given by its linear description, or implicitly by an oracle. Similarly, X can be explicitly given as a list of vectors, or implicitly as a face of P. While removing vertices turns to be hard in general, it is tractable for tractable 0-1 polytopes, and compact extended formulations can be obtained. Some extensions to integral polytopes are also presented. The third part is devoted to the integer L-shaped method for two-stage stochastic integer programs. A widely used model assumes that decisions are made in a two-step fashion, where first-stage decisions are followed by second-stage recourse actions after the uncertain parameters are observed, and we seek to minimize the expected overall cost. In the case of finitely many possible outcomes or scenarios, the integer L-shaped method proposes a decomposition scheme akin to Benders' decomposition for linear problems, but where a series of mixed-integer subproblems have to be solved at each iteration. To improve the performance of the method, we devise a simple modification that alternates between linear and mixed-integer subproblems, yielding significant time savings in instances from the literature. We also present a general framework to generate optimality cuts via a cut-generating problem. Using an extended formulation of the forbidden-vertices problem, we recast our cut-generating problem as a linear problem and embed it within the integer L-shaped method. Our numerical experiments suggest that this approach can prove beneficial when the first-stage set is relatively complicated.
44
Rönnberg, Elina. "Methods and Applications in Integer Programming : All-Integer Column Generation and Nurse Scheduling." Licentiate thesis, Linköping University, Linköping University, Optimization, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-15143.
Abstract:
Integer programming can be used to provide solutionsto complex decision and planning problems occurring in a wide varietyof situations. Applying integer programming to a real life problembasically involves a first phase where a mathematical model isconstructed, and a second phase where the problem described by themodel is solved. While the nature of the challenges involved in therespective two phases differ, the strong relationship between theproperties of models, and which methods that are appropriate for theirsolution, links the two phases. This thesis constitutes of threepapers, of which the third one considers the modeling phase, while thefirst and second one consider the solution phase.
Many applications of column generation yield master problems of setpartitioning type, and the first and second papers presentmethodologies for solving such problems. The characteristics of themethodologies presented are that all successively found solutions arefeasible and integral, where the retention of integrality is a majordistinction from other column generation methods presented in theliterature.
The third paper concerns nurse scheduling and describes the results ofa pilot implementation of a scheduling tool at a Swedish nursing ward.This paper focuses on the practical aspects of modeling and thechallenges of providing a solution to a complex real life problem.
45
Wiese, Sven <1985>. "On the interplay of Mixed Integer Linear, Mixed Integer Nonlinear and Constraint Programming." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2016. http://amsdottorato.unibo.it/7612/1/wiese_sven_tesi.pdf.
Abstract:
In this thesis we study selected topics in the field of Mixed Integer Programming (MIP), in particular Mixed Integer Linear and Nonlinear Programming (MI(N)LP). We set a focus on the influences of Constraint Programming (CP).
First, we analyze Mathematical Programming approaches to water network optimization, a set of challenging optimization problems frequently modeled as non-convex MINLPs. We give detailed descriptions of many variants and survey solution approaches from the literature. We are particularly interested in MILP approximations and present a respective computational study for water network design problems. We analyze this approach by algorithmic considerations and highlight the importance of certain convex substructures in these non-convex MINLPs. We further derive valid inequalities for water network design problems exploiting these substructures.
Then, we treat Mathematical Programming problems with indicator constraints, recalling their most popular reformulation techniques in MIP, leading to either big-M constraints or disjunctive programming techniques. The latter give rise to reformulations in higher-dimensional spaces, and we review special cases from the literature that allow to describe the projection on the original space of variables explicitly. We theoretically extend the respective results in two directions and conduct computational experiments. We then present an algorithm for MILPs with indicator constraints that incorporates elements of CP into MIP techniques, including computational results for the JobShopScheduling problem.
Finally, we introduce an extension of the class of MILPs so that linear expressions are allowed to have non-contiguous domains. Inspired by CP, this permits to model holes in the domains of variables as a special case. For such problems, we extend the theory of split cuts and show two ways of separating them, namely as intersection and lift-and-project cuts, and present computational results. We further experiment with an exact algorithm for such problems, applied to the Traveling Salesman Problem with multiple time windows.
46
Wiese, Sven <1985>. "On the interplay of Mixed Integer Linear, Mixed Integer Nonlinear and Constraint Programming." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2016. http://amsdottorato.unibo.it/7612/.
Abstract:
In this thesis we study selected topics in the field of Mixed Integer Programming (MIP), in particular Mixed Integer Linear and Nonlinear Programming (MI(N)LP). We set a focus on the influences of Constraint Programming (CP).
First, we analyze Mathematical Programming approaches to water network optimization, a set of challenging optimization problems frequently modeled as non-convex MINLPs. We give detailed descriptions of many variants and survey solution approaches from the literature. We are particularly interested in MILP approximations and present a respective computational study for water network design problems. We analyze this approach by algorithmic considerations and highlight the importance of certain convex substructures in these non-convex MINLPs. We further derive valid inequalities for water network design problems exploiting these substructures.
Then, we treat Mathematical Programming problems with indicator constraints, recalling their most popular reformulation techniques in MIP, leading to either big-M constraints or disjunctive programming techniques. The latter give rise to reformulations in higher-dimensional spaces, and we review special cases from the literature that allow to describe the projection on the original space of variables explicitly. We theoretically extend the respective results in two directions and conduct computational experiments. We then present an algorithm for MILPs with indicator constraints that incorporates elements of CP into MIP techniques, including computational results for the JobShopScheduling problem.
Finally, we introduce an extension of the class of MILPs so that linear expressions are allowed to have non-contiguous domains. Inspired by CP, this permits to model holes in the domains of variables as a special case. For such problems, we extend the theory of split cuts and show two ways of separating them, namely as intersection and lift-and-project cuts, and present computational results. We further experiment with an exact algorithm for such problems, applied to the Traveling Salesman Problem with multiple time windows.
47
Goycoolea, Marcos G. "Cutting Planes for Large Mixed Integer Programming Models." Diss., Georgia Institute of Technology, 2006. http://hdl.handle.net/1853/13956.
Abstract:
In this thesis I focus on cutting planes for large Mixed Integer Programming (MIP) problems. More specifically, I focus on two independent cutting planes studies. The first of these deals with cutting planes for the Traveling Salesman Problem (TSP), and the second with cutting planes for general MIPs.
In the first study I introduce a new class of cutting planes which I call the Generalized Domino Parity (GDP) inequalities. My main achievements with regard to these are: (1) I show that these are valid for the TSP and for the graphical TSP. (2) I show that they generalize most well-known TSP inequalities (including combs, domino-parity constraints, clique-trees, bipartitions, paths and stars). (3) I show that a sub-class of these (which contains all clique-tree inequalities w/ a fixed number of handles) can be separated in polynomial time, on planar graphs.
My second study can be subdivided in two parts. In the first of these I study the Mixed Integer Knapsack Problem (MIKP) and develop a branch-and-bound based algorithm for solving it. The novelty of the approach is that it exploits the notion of "dominance" in order to effectively prune solutions in the branch-and-bound tree. In the second part, I develop a Mixed Integer Rounding (MIR) cut separation heuristic, and embed the MIKP solver in a column generation algorithm in order to assess the performance of said heuristic. The goal of this study is to understand why no other class of inequalities derived from single-row systems has been able to outperform the MIR. Computational results are presented.
48
Vigerske, Stefan [Verfasser], Werner [Akademischer Betreuer] Römisch, Rüdiger [Akademischer Betreuer] Schultz, and Pierre [Akademischer Betreuer] Bonami. "Decomposition in multistage stochastic programming and a constraint integer programming approach to mixed-integer nonlinear programming / Stefan Vigerske. Gutachter: Werner Römisch ; Rüdiger Schultz ; Pierre Bonami." Berlin : Humboldt Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, 2013. http://d-nb.info/1033586579/34.
49
Engineer, Faramroze Godrej. "Advances in shortest path based column generation for integer programming." Diss., Georgia Institute of Technology, 2009. http://hdl.handle.net/1853/34761.
Abstract:
Branch-price-and-cut algorithms are among the most successful exact optimization approaches for solving many routing and scheduling problems. This is due, in part, to the availability of extremely efficient and effective dynamic programming algorithms for solving the pricing problem, and the availability of efficient and effective branching schemes and cutting planes that drive integrality. In terms of branch-price-and-cut, two obstacles we face today are (1) being able to solve harder and larger pricing problems, and (2) solving mixed-integer column generation formulations that suffer from relatively weak LP bounds compared to the more traditional 0-1 set partitioning type. As part of the work presented in this thesis, we encounter column generation formulations motivated by real life problems that require overcoming both types of challenges.
The first part of this thesis is dedicated to solving the resource constrained shortest path problem (RCSPP) arising in column generation pricing problems for formulations involving extremely large networks and a huge number of local resource constraints. We present a relaxation-based dynamic programming algorithm that alternates between a forward and a backward search. Each search employs bounds derived in the previous search to prune the search, and between consecutive searches, the relaxation is tightened over a set of critical resources and arcs.
The second part of this thesis focuses in the fixed charge shortest path problem (FCSPP) in which the amount of resource consumed is itself a continuous bounded variable. By exploiting the structure of optimal solutions to FCSPP, we design and implement a solution approach that relies on solving multiple RCSPPs, and therefore can again make use of extremely efficient and effective dynamic programming algorithms.
In the third and final part of this thesis, we present a branch-price-and-cut algorithm for the inventory routing problem (IRP). We extend a class of cuts known for the vehicle routing problem, and develop a new class of cuts specifically for IRP to tighten the formulation. Both the branching schemes and cuts preserve the structure of the pricing problem making them efficiently implementable within a branch-price-and-cut algorithm.
50
朱紫君 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.