In this paper, we describe the facial structure of the steiner problem in a directed graph by formulating it as a set covering problem. We first characterize trivial facets and derive a necessary condition for nontrivial facets. We also introduce a class of valid inequalities with 0-1 coefficients and show when such inequalities define facets.

Mixed-integer programming provides a natural framework for modeling optimization problems which require discrete decisions. Valid inequalities, used as cutting-planes and cuttingsurfaces in integer programming solvers, are an essential part of today’s integer programming technology. They enable the solution of mixed-integer programs of greater scale and complexity by providing tighter mathematical descriptions of the feasible solution set. This dissertation presents new structural results on general-purpose valid inequalities for mixedinteger linear and mixed-integer conic programs. Cut-generating functions are a priori formulas for generating a cutting-plane from the data of a mixed-integer linear program. This concept has its roots in the work of Balas, Gomory, and Johnson from the 1970s. It has received renewed attention in the past few years. Gomory and Johnson studied cut-generating functions for the corner relaxation of a mixedinteger linear program, which ignores the nonnegativity constraints on the basic variables in a tableau formulation. We consider models where these constraints are not ignored. In our first contribution, we generalize a classical result of Gomory and Johnson characterizing minimal cut-generating functions in terms of subadditivity, symmetry, and periodicity. Our analysis also exposes shortcomings in the usual definition of minimality in our general setting. To remedy this, we consider stronger notions of minimality and show that these impose additional structure on cut-generating functions. A stronger notion than the minimality of a cut-generating function is its extremality. While extreme cut-generating functions produce powerful cutting-planes, their structure can be very complicated. For the corner relaxation of a one-row integer linear program, Gomory and Johnson identified continuous, piecewise linear, minimal cut-generating functions with only two distinct slope values as a “simple” class of extreme cut-generating functions. In our second contribution, we establish a similar result for a one-row problem which takes the nonnegativity constraint on the basic variable into account. In our third contribution, we consider a multi-row model where only continuous nonbasic variables are present. Conforti, Cornuéjols, Daniilidis, Lemaréchal, and Malick recently showed that not all cutting-planes can be obtained from cut-generating functions in this framework. They also conjectured a natural condition under which cut-generating functions might be sufficient. In our third contribution, we prove that this conjecture is true. This justifies the recent research interest in cut-generating functions for this model. Despite the power of mixed-integer linear programming, many optimization problems of practical and theoretical interest cannot be modeled using a linear objective function and constraints alone. Next, we turn to a natural generalization of mixed-integer linear programming which allows nonlinear convex constraints: mixed-integer conic programming. Disjunctive inequalities, introduced by Balas in the context of mixed-integer linear programming in the 1970s, have been a principal ingredient in the practical success of mixed-integer programming in the last two decades. In order to extend our understanding of disjunctive inequalities to mixed-integer conic programming, we pursue a principled study of two-term disjunctions on conic sets. In our fourth contribution, we consider two-term disjunctions on a general regular cone. A result of Kılınç-Karzan indicates that conic minimal valid linear inequalities are all that is needed for a closed convex hull description of such sets. First we characterize the structure of conic minimal and tight valid linear inequalities for the disjunction. Then we develop structured nonlinear valid inequalities for the disjunction by grouping subsets of valid linear inequalities. We analyze the structure of these inequalities and identify conditions which guarantee that a single such inequality characterizes the closed convex hull of the disjunction. In our fifth and sixth contributions, we extend our earlier results to the cases where the regular cone under consideration is a direct product of second order cones and nonnegative rays and where it is the positive semidefinite cone. Disjunctions on these cones deserve special attention because they provide fundamental relaxations for mixed-integer second-order cone and mixed-integer semidefinite programs. We identify conditions under which our valid convex inequalities can be expressed in computationally tractable forms and present techniques to generate low-complexity relaxations when these conditions are not satisfied. In our final contribution, we provide closed convex hull descriptions for homogeneous two-term disjunctions on the second-order cone and general two-term disjunctions on affine cross-sections of the second-order cone. Our results yield strong convex disjunctive inequalities which can be used as cutting-surfaces in generic mixed-integer conic programming solvers.

Addressing fairness among users and risk mitigation in the context of resource allocation in transportation systems under uncertainties poses a crucial challenge yet to be satisfactorily resolved. This dissertation attempts to address this challenge, focusing on achieving a balance between system-wide efficiency and individual fairness in stochastic transportation resource allocation problems. To study complicated fair and risk-averse resource allocation problems - from public transit to urban air mobility and multi-stage infrastructure maintenance - we develop three models: DrFRAM, FairUAM, and FCMDP. Each of these models, despite being proven NP-hard even in a simplistic case, inspires us to develop efficient solution algorithms. We derive mixed-integer linear programming (MILP) formulations for these models, leveraging the unique properties of each model and linearizing non-linear terms. Additionally, we strengthen these models with valid inequalities. To efficiently solve these models, we design exact algorithms and approximation algorithms capable of obtaining near-optimal solutions. We numerically validate the effectiveness of our proposed models and demonstrate their capability to be applied to real-world case studies to adeptly address the uncertainties and risks arising from transportation systems. This dissertation provides a foundational platform for future inquiries of risk-averse resource allocation strategies under uncertainties for more efficient, equitable, and resilient decision-making. Our adaptable framework can address a variety of transportation-related challenges and can be extended beyond the transportation domain to tackle resource allocation problems in a broader setting. / Doctor of Philosophy / In transportation systems, decision-makers constantly strive to devise the optimal plan for the most beneficial outcomes when facing future uncertainties. When optimizing overall efficiency, individual fairness has often been overlooked. Besides, the uncertainties in the transportation systems raise serious questions about the adaptability of the allocation plan. In response to these issues, we introduce the concept of fair and risk-averse resource allocation under uncertainties in this dissertation. Our goal is to formulate the optimal allocation plan that is both fair and risk-averse amid uncertainties. To tackle the complexities of fair and risk-averse resource allocation problems, we propose innovative methods and practical algorithms, including creating novel formulations as well as deriving super-fast algorithms. These solution approaches are designed to accommodate the fairness, uncertainties, and risks typically in transportation systems. Beyond theoretical results, we apply our frameworks and algorithms to real-world case studies, thus demonstrating our approaches' adaptability to various transportation systems and ability to achieve various optimization goals. Ultimately, this dissertation aims to contribute to fairer, more efficient, and more robust transportation systems. We believe our research findings can help decision-makers with well-informed choices about resource allocation in transportation systems, which, in turn, lead to the development of more equitable and reliable systems, benefiting all the stakeholders.

Nesta tese apresentamos duas estratégias para resolver o problema de job-shop flexível com o objetivo de minimizar o makespan. A primeira estratégia utiliza um algoritmo branch and cut (B&C) e a segunda abordagens matheuristics. O algoritmo B&C utiliza novas classes de inequações válidas, originalmente formulada para o problema de job-shop e estendida para o problema em questão. Para que as inequações válidas sejam eficientes, o modelo proposto por Birgin et al, (2014) (A milp model for an extended version of the fexible job shop problem. Optimization Letters, Springer, v. 8, n. 4, 1417-1431), é reformulado (MILP-2). A segunda estratégia utiliza as matheuristcs local branching e diversification, refining and tight-refining. Os experimentos computacionais mostraram que a inclusão dos planos de corte melhoram a relaxação do modelo MILP-2 e a qualidade das soluções. O algoritmo B&C reduziu o gap e o número de nós explorados para uma grande quantidade de instâncias. As abordagens matheuristics tiveram um excelente desempenho. Do total de 59 instâncias analisadas, somente em 3 problemas a resolução do modelo MILP-1 obteve melhores resultados do que as abordagens matheuristcs / This thesis proposes two approaches to solve the flexible job-shop scheduling problem to minimize the makespan. The first strategy uses a branch and cut algorithm (B&C) and the second approach is based on matheuristics. The B&C algorithm uses new classes of valid inequalities, originally formulated for job-shop scheduling problems and extended to the problem at hand. The second approach uses the matheuristics local branching and diversification, refining and tight-refining. For all valid inequalities to be effective, the precedence variable based model proposed by Birgin et al, (2014) (A milp model for an extended version of the fexible job shop problem. Optimization Letters, Springer, v. 8, n. 4, 1417-1431), is reformulated (MILP-2). The computational experiments showed that the inclusion of cutting planes tightened the linear programming relaxations and improved the quality of solutions. B&C algorithm reduced the gap value and the number of nodes explored in a large number of instances. The matheuristics approaches had an excellent performance. From 59 instances analized, MILP-1-Gurobi showed better results than matheuristics approaches in only 3 problems

We consider combinatorial t-design problems as discrete optimization problems. Our motivation is that only a few studies have been done on the use of exact optimization techniques in designs, and that classical methods in design theory have still left many open existence questions. Roughly defined, t-designs are pairs of discrete sets that are related following some strict properties of size, balance, and replication. These highly structured relationships provide optimal solutions to a variety of problems in computer science like error-correcting codes, secure communications, network interconnection, design of hardware; and are applicable to other areas like statistics, scheduling, games, among others. We give a new approach to combinatorial t-designs that is useful in constructing t-designs by polyhedral methods. The first contribution of our work is a new result of equivalence of t-design problems with a graph theory problem. This equivalence leads to a novel integer programming formulation for t-designs, which we call GDP. We analyze the polyhedral properties of GDP and conclude, among other results, the associated polyhedron dimension. We generate new classes of valid inequalities to aim at approximating this integer program by a linear program that has the same optimal solution. Some new classes of valid inequalities are generated as Chv´atal-Gomory cuts, other classes are generated by graph complements and combinatorial arguments, and others are generated by the use of incidence substructures in a t-design. In particular, we found a class of valid inequalities that we call stable-set class that represents an alternative graph equivalence for the problem of finding a t-design. We analyze and give results on the strength of these new classes of valid inequalities. We propose a separation problem and give its integer programming formulation as a maximum (or minimum) edge-weight biclique subgraph problem. We implement a pure cutting-plane algorithm using one of the stronger classes of valid inequalities derived. Several instances of t-designs were solved efficiently by this algorithm at the root node of the search tree. Also, we implement a branch-and-cut algorithm and solve several instances of 2-designs trying different base formulations. Computational results are included.

We consider combinatorial t-design problems as discrete optimization problems. Our motivation is that only a few studies have been done on the use of exact optimization techniques in designs, and that classical methods in design theory have still left many open existence questions. Roughly defined, t-designs are pairs of discrete sets that are related following some strict properties of size, balance, and replication. These highly structured relationships provide optimal solutions to a variety of problems in computer science like error-correcting codes, secure communications, network interconnection, design of hardware; and are applicable to other areas like statistics, scheduling, games, among others. We give a new approach to combinatorial t-designs that is useful in constructing t-designs by polyhedral methods. The first contribution of our work is a new result of equivalence of t-design problems with a graph theory problem. This equivalence leads to a novel integer programming formulation for t-designs, which we call GDP. We analyze the polyhedral properties of GDP and conclude, among other results, the associated polyhedron dimension. We generate new classes of valid inequalities to aim at approximating this integer program by a linear program that has the same optimal solution. Some new classes of valid inequalities are generated as Chv´atal-Gomory cuts, other classes are generated by graph complements and combinatorial arguments, and others are generated by the use of incidence substructures in a t-design. In particular, we found a class of valid inequalities that we call stable-set class that represents an alternative graph equivalence for the problem of finding a t-design. We analyze and give results on the strength of these new classes of valid inequalities. We propose a separation problem and give its integer programming formulation as a maximum (or minimum) edge-weight biclique subgraph problem. We implement a pure cutting-plane algorithm using one of the stronger classes of valid inequalities derived. Several instances of t-designs were solved efficiently by this algorithm at the root node of the search tree. Also, we implement a branch-and-cut algorithm and solve several instances of 2-designs trying different base formulations. Computational results are included.

Orientador: Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-10T01:09:54Z (GMT). No. of bitstreams: 1 Fonseca_SaraLuisadeAndrade_M.pdf: 1363535 bytes, checksum: aa7c01c779a21ea25aa3b603425c92fe (MD5) Previous issue date: 2007 / Resumo: Em 1958, Gomory propôs uma desigualdade válida ou corte a partir do tableau do método simplex para programação linear, que foi utilizado no primeiro método genérico para resolução de problemas de programação inteira. Em 1960, o corte foi estendido para problemas de programação inteira mista. Em 1973, Chvátal sugeriu um corte derivado da formulação original do problema de programação inteira, e devido à equivalência com o corte de Gomory, este passou a ser chamado de corte de Chvátal-Gomory. A importância do corte de Gomory só foi reconhecida em 1996 dentro do contexto do método branch-and-cut para resolução de problemas de programação inteira e programação inteira mista. Desde então, este corte é utilizado em resolvedores comerciais de otimização. Recentemente, diversos cortes novos derivados do corte de Chvátal-Gomory foram propostos na literatura para programação inteira. Este trabalho trata do desenvolvimento de algoritmos para alguns destes cortes, e implementação computacional em um contexto de branch-and-cut, no ambiente do resolvedor CPLEX. A eficácia dos cortes é testada em instâncias dos problemas da mochila multidimensional, designação generalizada e da biblioteca MIPLIB. / Abstract: In 1958, Gomory proposed a valid inequality or cut from the tableau of the simplex method for linear programming, which was used in the first generic method for solving integer programming problems. In 1960, the cut was extended to handle mixed integer programming problems. In 1973, Chvátal suggested a cut that is generated from the original formulation of an integer programming problem, and due to the equivalence with the Gomory cut, it was named Chvátal-Gomory cut. The importance of the Gomory cut was recognized only in 1996 in the context of the branch-and-cut method for solving (mixed) integer programming problems. Today, such a cut is utilized in optimization commercial solvers. Recently, several new cuts derived from the Chvátal-Gomory cut have been proposed in the literature for integer programming. This work deals with the development of algorithms and computational implementations for some of the new proposed cuts, in a context of the branch-and-cut method, by using the CPLEX solver. The efficiency of the cuts is tested on instances of the multi-dimensional knapsack, generalized assignment problems, and instances from the MIPLIB library. / Mestrado / Automação / Mestre em Engenharia Elétrica

Nesta tese apresentamos duas estratégias para resolver o problema de job-shop flexível com o objetivo de minimizar o makespan. A primeira estratégia utiliza um algoritmo branch and cut (B&C) e a segunda abordagens matheuristics. O algoritmo B&C utiliza novas classes de inequações válidas, originalmente formulada para o problema de job-shop e estendida para o problema em questão. Para que as inequações válidas sejam eficientes, o modelo proposto por Birgin et al, (2014) (A milp model for an extended version of the fexible job shop problem. Optimization Letters, Springer, v. 8, n. 4, 1417-1431), é reformulado (MILP-2). A segunda estratégia utiliza as matheuristcs local branching e diversification, refining and tight-refining. Os experimentos computacionais mostraram que a inclusão dos planos de corte melhoram a relaxação do modelo MILP-2 e a qualidade das soluções. O algoritmo B&C reduziu o gap e o número de nós explorados para uma grande quantidade de instâncias. As abordagens matheuristics tiveram um excelente desempenho. Do total de 59 instâncias analisadas, somente em 3 problemas a resolução do modelo MILP-1 obteve melhores resultados do que as abordagens matheuristcs / This thesis proposes two approaches to solve the flexible job-shop scheduling problem to minimize the makespan. The first strategy uses a branch and cut algorithm (B&C) and the second approach is based on matheuristics. The B&C algorithm uses new classes of valid inequalities, originally formulated for job-shop scheduling problems and extended to the problem at hand. The second approach uses the matheuristics local branching and diversification, refining and tight-refining. For all valid inequalities to be effective, the precedence variable based model proposed by Birgin et al, (2014) (A milp model for an extended version of the fexible job shop problem. Optimization Letters, Springer, v. 8, n. 4, 1417-1431), is reformulated (MILP-2). The computational experiments showed that the inclusion of cutting planes tightened the linear programming relaxations and improved the quality of solutions. B&C algorithm reduced the gap value and the number of nodes explored in a large number of instances. The matheuristics approaches had an excellent performance. From 59 instances analized, MILP-1-Gurobi showed better results than matheuristics approaches in only 3 problems

No description available.

Στην εργασία αυτή αντιμετωπίζεται το πρόβλημα της χωροθέτησης εγκαταστάσεων και της κατανομής της ζήτησης σε περιφερειακό επίπεδο μέσω της παρουσίασης σχετικών μαθηματικών υποδειγμάτων μικτού ακέραιου προγραμματισμού, τα οποία στη συνέχεια εφαρμόζονται σε περιπτωσιολογική μελέτη. Η εργασία αφορά την χωροθέτηση δημοσίων εγκαταστάσεων. Ειδικότερα, αναφέρεται στην κατηγορία των προβλημάτων χωροθέτησης που χρησιμοποιούν την τυπική συνάρτηση αποδοτικότητας minsum. Σε αυτές τις περιπτώσεις οι εγκαταστάσεις τοποθετούνται έτσι ώστε να ελαχιστοποιούν το άθροισμα του συνολικού κόστους μεταφοράς. Η εργασία επικεντρώνεται στην χωροθέτηση οχληρών εγκαταστάσεων και συγκεκριμένα στη χωροθέτηση εγκαταστάσεων διαχείρισης αστικών απορριμμάτων. Αυτές οι εγκαταστάσεις ασκούν επιδράσεις όχι μόνο στον χώρο που καταλαμβάνουν, αλλά και σε μεγάλες εκτάσεις γύρω τους. Το πρόβλημα χωροθέτησης σε αυτές τις περιπτώσεις γίνεται ακόμα πιο πολύπλοκο λόγω της αναγκαίας συνεκτίμησης πολλαπλών κριτηρίων. Για τον σκοπό αυτό αναπτύσσεται ένα εξειδικευμένο πλαίσιο παραγωγής μαθηματικών υποδειγμάτων. Ειδικότερα,. στην παρούσα διδακτορική εργασία, δημιουργήθηκαν μαθηματικά υποδείγματα βελτιστοποίησης μικτού ακέραιου προγραμματισμού, τα οποία στη συνέχεια αναλύονται με μεθόδους πολυκριτηριακής ανάλυσης. Τα υποδείγματα αυτά εφαρμόζονται σε περιπτωσιολογική μελέτη με θέμα το χωροθετικό σχεδιασμό ενός περιφερειακού συστήματος διαχείρισης των αστικών απορριμμάτων για τον νομό Αχαΐας. / This study considers a facility location problem with demand allocation in regional level through mixed integer programming models that have been developed for these propose. Afterwards, these models applied in a case study. The present research concerns mostly the public facility location problems. In particular, the PhD dissertation deals with models using the typical mathematical function of efficiency minsum. Therese models locate the facilities in order to minimize the sum of costs for opening facilities and variable transportation costs. The problem becomes more complicated if, in addition it is necessary to locate undesirable facilities. The selection of proper sites for the facilities with obnoxious characteristics is a sensitive issue that has often cause social and political tension. The multiobjective nature of the problem implies that a number of environmental social and political criteria have to be considered. The study presents a model generating framework for formulating location allocation models that applied in municipal solid waste management systems. These models analyzed via multicriteria methodology in order to select the locations of different types of facilities at the regional level. Finally, we apply these concepts in a case study for the development of a solid waste management system for a specific region in Greece.