Solution methodologies for mixed integer bilinear problems (MIBLP) are studied in this dissertation. This problem class is motivated using the pooling problem, a multicommodity network flow problem that typically arises in chemical engineering applications. Stronger than previously known results are provided to compare the strengths of polyhedral relaxations of the pooling problem. A novel single node flow relaxation, defined by a bilinear equality constraint and flow balance, is proposed for the pooling problem. Linear valid inequalities in the original space of variables are derived using a well-known technique called lifting. Mixed integer linear (MILP) formulations are proposed for generating feasible solutions to the pooling problem. Some of these MILP models arise from variable discretizations while others possess a network flow interpretation. The effectiveness of these MILP models is empirically validated on a library of medium and large-scale instances. General MIBLPs, not necessarily pooling problems, are solved using extended MILP reformulations. The reformulation is obtained by writing binary representation for each general integer variable. Facet-defining inequalities are provided for the reformulation of each bilinear term. New valid inequalities are also proposed for bilinear terms with a nontrivial upper bound. The proposed reformulation and cutting planes are compared against a global solver on five different classes of MIBLPs.

Orientador: José Roberto Sanches Mantovani / Resumo: Neste trabalho, o modelo matemático do problema de fluxo de potência ótimo básico não linear é analisado e manipulado algebricamente para obter um modelo de programação convexa, do tipo cônico de segunda ordem. O conceito de envelopes convexos é apresentado para tratar a não linearidade e não convexidade da restrição trigonométrica inversa que surge ao escrever o modelo de FPO como um modelo cônico. Aplicando duas proposições apresentadas neste trabalho a restrição trigonométrica é resolvida em um pré-processamento por um solver de otimalidade local, neste caso o KNITRO, que enumera todas as possibilidades dos pontos de KKT para obter os envelopes convexos e tornar o modelo de FPO totalmente convexo. O modelo é implementado no AMPL e é resolvido com solvers de otimalidade global com sistemas testes da literatura, nesta tese usam-se os sistemas testes IEEE 14, 30, 57 e 118 barras. Os resultados obtidos são validados comparando-os com resultados fornecidos pelo Matpower, que é um simulador para FPO. Como contribuição desta tese, o modelo convexo de FPO obtido é utilizado como exemplo de aplicações no problema de despacho ótimo de potência ativa e reativa, considerando competições via programação binível. São apresentados dois modelos biníveis e dois modelos uníveis. O modelo iterativo convexo utiliza-se do modelo proposto de FPO convexo e as não linearidades são convexificadas fazendo uso dos envelopes de McCormick. O conceito de dualidade forte é empregado afim de obter um mod... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: In this work, the basic nonlinear mathematical model for the optimal power flow (OPF) problem is analyzed and manipulated algebraically in order to obtain a second-order conic convex programming model. The concept of convex envelopes is presented to deal with the nonlinearity and nonconvexity of the inverse trigonometric constraint that arises when transforming the nonconvex OPF model into an equivalent conic model. By applying two propositions presented in this work, the trigonometric constraint is solved in a pre-processing stage by a local optimization solver, in this case, the KNITRO solver, which considers all the possibilities of the KKT points to obtain the convex envelopes and find a completely convex OPF model, is used. The model is implemented in AMPL and is solved via global optimization solvers while to show the effectiveness of the model several IEEE systems such as the IEEE 14-, 30-, 57-, and 118-bus systems are used. The obtained results are validated by comparing them with the results provided by Matpower, which is an OPF solver. As a contribution of this thesis, the obtained convex OPF model is used as an application in the active and reactive optimal power dispatch problem, considering competition via bilevel programming. Two bilevel models and two single-level models are presented. The convex iterative model uses the proposed convex OPF model, and the nonlinearities are convexified using McCormick envelopes. The concept of strong duality is employed to obta... (Complete abstract click electronic access below) / Doutor