No description available.

Orientador: Rubén Augusto Romero Lázaro / Resumo: Neste trabalho, consideram-se a análise teórica e a implementação computacional dos algoritmos Primal Simplex Canalizado (PSC) e Dual Simplex Canalizado (DSC) especializados. Esses algoritmos foram incorporados em um algoritmo Branch and Bound (B&B) de modo a resolver o problema de Planejamento da Expansão de Sistemas de Transmissão (PEST). Neste caso, o problema PEST foi modelado usando os chamados modelo de Transportes e modelo Linear Disjuntivo (LD), o que produz um problema de Programação Linear Inteiro Misto (PLIM). O algoritmo PSC é utilizado na resolução do problema de Programação Linear (PL) inicial após desconsiderar a restrição de integralidade do problema PLIM original. Juntamente com o algoritmo PSC, foi implementada uma estratégia para reduzir o número de variáveis artificiais adicionadas ao PL, consequentemente reduzindo o número de iterações do algoritmo PSC. O algoritmo DSC é utilizado na reotimização eficiente dos subproblemas gerados pelo algoritmo B&B, através do quadro ótimo do PL inicial, excluindo, assim, a necessidade da resolução completa de cada subproblema e, consequentemente, reduzindo o consumo de processamento e memória. Nesta pesquisa, é apresentada uma nova proposta de otimização, e, consequentemente, a implementação computacional usando a linguagem de programação FORTRAN que opera independentemente de qualquer solver. / Doutor

Submitted by JEFERSON BACK VANDERLINDE null (jefersonbv@yahoo.com.br) on 2017-11-01T16:38:25Z No. of bitstreams: 1 jeferson_tese_final_20171101.pdf: 4860852 bytes, checksum: 2f99c37969be3815f82b1b4455a40230 (MD5) / Approved for entry into archive by LUIZA DE MENEZES ROMANETTO (luizamenezes@reitoria.unesp.br) on 2017-11-13T15:38:34Z (GMT) No. of bitstreams: 1 vanderlinde_jb_dr_ilha.pdf: 4860852 bytes, checksum: 2f99c37969be3815f82b1b4455a40230 (MD5) / Made available in DSpace on 2017-11-13T15:38:34Z (GMT). No. of bitstreams: 1 vanderlinde_jb_dr_ilha.pdf: 4860852 bytes, checksum: 2f99c37969be3815f82b1b4455a40230 (MD5) Previous issue date: 2017-09-06 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho, consideram-se a análise teórica e a implementação computacional dos algoritmos Primal Simplex Canalizado (PSC) e Dual Simplex Canalizado (DSC) especializados. Esses algoritmos foram incorporados em um algoritmo Branch and Bound (B&B) de modo a resolver o problema de Planejamento da Expansão de Sistemas de Transmissão (PEST). Neste caso, o problema PEST foi modelado usando os chamados modelo de Transportes e modelo Linear Disjuntivo (LD), o que produz um problema de Programação Linear Inteiro Misto (PLIM). O algoritmo PSC é utilizado na resolução do problema de Programação Linear (PL) inicial após desconsiderar a restrição de integralidade do problema PLIM original. Juntamente com o algoritmo PSC, foi implementada uma estratégia para reduzir o número de variáveis artificiais adicionadas ao PL, consequentemente reduzindo o número de iterações do algoritmo PSC. O algoritmo DSC é utilizado na reotimização eficiente dos subproblemas gerados pelo algoritmo B&B, através do quadro ótimo do PL inicial, excluindo, assim, a necessidade da resolução completa de cada subproblema e, consequentemente, reduzindo o consumo de processamento e memória. Nesta pesquisa, é apresentada uma nova proposta de otimização, e, consequentemente, a implementação computacional usando a linguagem de programação FORTRAN que opera independentemente de qualquer solver. / In this research, the theoretical analysis and computational implementation of the specialized dual simplex algorithm (DSA) and primal simplex algorithm (PSA) for bounded variables is considered. These algorithms have been incorporated in a Branch and Bound (B&B) algorithm to solve the Transmission Network Expansion Planning (TNEP) problem. In this case, the TNEP problem is modeled using transportation model and linear disjunctive model (DM), which produces a mixed-integer linear programming (MILP) problem. After relaxing the integrality of investment variables of the original MILP problem, the PSA is used to solve the initial linear programming (LP) problem. Also, it has been implemented a strategy in PSA to reduce the number of artificial variables which are added into the LP problem, and consequently reduces the number of iterations of PSA. Through optimal solution of the initial LP, the DSA is used in efficient reoptimization of subproblems, resulting from the B&B algorithm, thus excludes the need for complete resolution of each subproblems, which results reducing the CPU time and memory consumption. This research presents the implementation of the proposed approach using the FORTRAN programming language which operates independently and does not use any commercial solver.

Made available in DSpace on 2014-07-29T15:03:39Z (GMT). No. of bitstreams: 1 lilian pureza.pdf: 2774999 bytes, checksum: 2a074d04ee02c7e1c87fdbe8c2c68ef6 (MD5) Previous issue date: 2006-10-20 / The aim of this work is to present a formulation and corresponding computational implementation for sizing optimization of plane frames and cable-stayed columns considering geometric non liner behavior. The structural analysis is based on the finite element method using the updated lagrangian approach for plane frame and cable elements, which are represented by plane truss elements. The non linear system is solved by the Newton-Raphson method coupled to load increment strategies such as the arch length method and the generalized displacement parameter method, which allow the algorithm to transpose any critical point that happen to appear along the equilibrium path. In the optimization process the design variables are the heights of the crosssection of the frame elements, the objective function represents the volume of the structure and the constraints impose limits to displacements and critical load. Lateral constraints impose limits to the design variables. The finite difference method is used in the sensitivity analysis of the displacement and critical load constraints. The optimization process is carried out using three different optimization strategies: the sequential quadratic programming algorithm; the interior points algorithm; and the branch and bound method. Some numerical experiments are carried out so as to test the analysis and the sensitivity strategies. Numerical experiments are presented to show the validity of the implementation presented in this dissertation. / O objetivo deste trabalho é a otimização de dimensões de pórticos planos e de colunas estaiadas planas pela minimização do volume da estrutura, considerando os efeitos da não-linearidade geométrica em seu comportamento. A formulação utiliza, para análise das estruturas, elementos finitos de pórtico e de treliça planos e referencial lagrangeano atualizado. O método de Newton-Raphson foi utilizado como estratégia para solução do sistema de equações não lineares. Foram acopladas estratégias especiais para ultrapassagem de pontos críticos que possam existir ao longo da trajetória de equilíbrio, tais como o comprimento de arco cilíndrico e o controle dos deslocamentos generalizados. Na otimização, as variáveis de projeto são as alturas das seções transversais dos elementos, a função objetivo é o volume do material e as restrições dizem respeito a limitações impostas a deslocamentos e à carga limite, além de limitações impostas aos valores das variáveis. A sensibilidade da função objetivo foi obtida por diferenciação direta e a sensibilidade das restrições pelo método das diferenças finitas. Foram utilizados o algoritmo de programação quadrática seqüencial, PQS, o algoritmo de pontos interiores, PI, e o algoritmo de Branch and Bound, B&B. São apresentados exemplos de validação das estratégias de análise não linear e da análise de sensibilidade, além dos exemplos de validação da formulação empregada para a otimização resolvidos pelos métodos implementados.

No description available.

No description available.

[pt] Com um número crescente de antenas em sistemas MIMO, o consumo de energia e os custos das interfaces de rádio correspondentes tornam-se relevantes. Nesse contexto, uma abordagem promissora é a utilização de conversores de dados de baixa resolução. Neste estudo, propomos dois novos pré-codificadores ótimos para a sinais de envelope constante e quantização de fase. O primeiro maximiza a distância mínima para o limite de decisão (MMDDT) nos receptores, enquanto o segundo minimiza o erro médio quadrático entre os símbolos dos usuários e o sinal de recepção. O design MMDDT apresetado nesse estudo é uma generalização de designs anteriores que baseiam-se em quantização de 1-bit. Além disso, ao contrário do projeto MMSE anterior que se baseia na resolução de 1-bit, a abordagem proposta emprega quantização de fase uniforme e a etapa de limite no método branch-and-bound é diferente em termos de considerar o relaxamento mais restritivo do problema não convexo, que é então utilizado para um design sub ótimo também. Além disso, três métodos diferentes de detecção suave e um esquema iterativo de detecção e decodificação que permite a utilização de codificação de canal em conjunto com pré-codificação de baixa resolução são propostos. Além de uma abordagem exata para calcular a informação extrínseca, duas aproximações com reduzida complexidade computacional são propostas. Os algoritmos propostos de pré-codificação branch-and-bound são superiores aos métodos existentes em termos de taxa de erro de bit. Resultados numéricos mostram que as abordagens propostas têm complexidade significativamente menor do que a busca exaustiva. Finalmente, os resultados baseados em um código de bloco LDPC indicam que os esquemas de processamento de recepção geram uma taxa de erro de bit menor em comparação com o projeto convencional. / [en] With an increasing number of antennas in multiple-input multiple-output (MIMO) systems, the energy consumption and costs of the corresponding front ends become relevant. In this context, a promising approach is the consideration of low-resolution data converters. In this study two novel optimal precoding branch-and-bound algorithms constrained to constant envelope signals and phase quantization are proposed. The first maximizes the minimum distance to the decision threshold (MMDDT) at the receivers, while the second minimizes the MSE between the users data symbols and the receive signal. This MMDDT design presented in this study is a generalization of prior designs that rely on 1-bit quantization. Moreover, unlike the prior MMSE design that relies on 1-bit resolution, the proposed MMSE approach employs uniform phase quantization and the bounding step in the branch-and-bound method is different in terms of considering the most restrictive relaxation of the nonconvex problem, which is then utilized for a suboptimal design also. Moreover, three different soft detection methods and an iterative detection and decoding scheme that allow the utilization of channel coding in conjunction with low-resolution precoding are proposed. Besides an exact approach for computing the extrinsic information, two approximations with reduced computational complexity are devised. The proposed branch-and-bound precoding algorithms are superior to the existing methods in terms of bit error rate. Numerical results show that the proposed approaches have significantly lower complexity than exhaustive search. Finally, results based on an LDPC block code indicate that the proposed receive processing schemes yield a lower bit-error-rate compared to the conventional design.

In this thesis, we consider the k-edge connected L-hop-constrained network design problem. Given a weighted graph G=(N,E), a set D of pairs of terminal nodes, and two integers k,L > 1, it consists in finding in G the minimum cost subgraph containing at least k edge-disjoint paths of at most L edges between each pair in D. This problem is of great interest in today's telecommunication industry, where highly survivable networks need to be constructed. We first study the particular case where the set of demands D is reduced to a single pair {s,t}. We propose an integer programming formulation for the problem, which consists in the st-cut and trivial inequalities, along with the so-called L-st-path-cut inequalities. We show that these three classes of inequalities completely describe the associated polytope when k=2 and L=2 or 3, and give necessary and sufficient conditions for them to be facet-defining. We also consider the dominant of the associated polytope, and discuss how the previous inequalities can be separated in polynomial time. We then extend the complete and minimal description obtained above to any number k of required edge-disjoint L-st-paths, but when L=2 only. We devise a cutting plane algorithm to solve the problem, using the previous polynomial separations, and present some computational results. After that, we consider the case where there is more than one demand in D. We first show that the problem is strongly NP-hard, for all L fixed, even when all the demands in D have one root node in common. For k=2 and L=2,3, we give an integer programming formulation, based on the previous constraints written for all pairs {s,t} in D. We then proceed by giving several new classes of facet-defining inequalities, valid for the problem in general, but more adapted to the rooted case. We propose separation procedures for these inequalities, which are embedded within a Branch-and-Cut algorithm to solve the problem when L=2,3. Extensive computational results from it are given and analyzed for both random and real instances. Since those results appear less satisfactory in the case of arbitrary demands (non necessarily rooted), we present additional families of valid inequalites in that situation. Again, separation procedures are devised for them, and added to our previous Branch-and-Cut algorithm, in order to see the practical improvement granted by them. Finally, we study the problem for greater values of L. In particular, when L=4, we propose new families of constraints for the problem of finding a subgraph that contains at least two L-st-paths either node-disjoint, or edge-disjoint. Using these, we obtain an integer programming formulation in the space of the design variables for each case. ------------------------------------------------ Dans cette thèse, nous considérons le problème de conception de réseau k-arete connexe à chemins L-bornés. Etant donné un graphe pondéré G=(N,E), un ensemble D de paires de noeuds terminaux, et deux entiers k,L > 1, ce problème consiste à trouver, dans G, un sous-graphe de cout minimum tel que, entre chaque paire dans D, il existe au moins k chemins arete-disjoints de longueur au plus L. Ce problème est d'un grand intéret dans l'industrie des télécommunications, où des réseaux hautement fiables doivent etre construits. Nous étudions tout d'abord le cas particulier où l'ensemble des demandes D est réduit à une seule paire de noeuds. Nous proposons une formulation du problème sous forme de programme linéaire en nombres entiers, laquelle consiste en les inégalités triviales et de coupe, ainsi que les inégalités dites de L-chemin-coupe. Nous montrons que ces trois types d'inégalités décrivent complètement le polytope associé lorsque k=2 et L=2,3, et donnons des conditions nécessaires et suffisantes pour que celles-ci en définissent des facettes. Nous considérons également le dominant du polytope associé et discutons de la séparation polynomiale des trois classes précédentes. Nous étendons alors cette description complète et minimale à tout nombre k de chemins arete-disjoints de longueur au plus 2. De plus, nous proposons un algorithme de plans coupants utilisant les précédentes séparations polynomiales, et en présentons quelques résultats calculatoires, pour tout k>1 et L=2,3. Nous considérons ensuite le cas où plusieurs demandes se trouvent dans D. Nous montrons d'abord que le problème est fortement NP-dur, pour tout L fixé et ce, meme si les demandes sont toutes enracinées en un noeud. Pour k=2 et L=2,3, nous donnons une formulation du problème sous forme de programme linéaire en nombres entiers. Nous proposons également de nouvelles classes d'inégalités valides, pour lesquelles nous réalisons une étude faciale. Celles-ci sont alors séparées dans le cadre d'un algorithme de coupes et branchements pour résoudre des instances aléatoires et réelles du problème. Enfin, nous étudions le problème pour de plus grandes valeurs de L. En particulier, lorsque L=4, nous donnons de nouvelles familles de contraintes pour le problème consistant à déterminer un sous-graphe contenant entre deux noeuds fixés au moins deux chemins de longueur au plus 4, que ceux-ci doivent etre arete-disjoints ou noeud-disjoints. Grace à ces dernières, nous parvenons à donner une formulation naturelle du problème dans chacun de ces deux cas.

No description available.

This dissertation deals with court-executive relations in post-authoritarian Argentina (1983-2006). Specifically, I analyse Supreme Court behaviour in highly sensitive cases to determine whether the tribunal has cooperated with or obstructed the government’s policy preferences in three key policy areas: human rights, economic emergency and pensions. This innovative type of approach – i.e., focusing on a small number of highly sensitive decisions – allows me to concentrate on cases that are genuinely important for the government or, more precisely, for the country’s political administration. There are cases that are significant for the State apparatus but irrelevant for the president (thinking of politicians as self-interested actors). My research uses a rational choice approach to courts, underscoring the strategic nature of judicial behaviour. This vision of judges provides a more accurate account of judicial-executive relations by bringing politics into the study of courts. By focusing exclusively on attitudes and apolitical jurisprudence, other visions take for granted the institutional context. Political stability, for example, cannot be assumed in many developing democracies. My findings indicate that the Argentine Supreme Court has consistently avoided obstructing the president’s policy preferences. Such behaviour is motivated by strategic considerations: judges are risk-averse actors that avoid clashing with the executive. For most of the time, the Supreme Court has operated under unified government, which increases the chances of being punished for anti-government decisions. Two other factors also account for the court’s risk-averse behaviour. First, procedural rules grant the Supreme Court wide discretion over its docket. The tribunal has used such discretion to strategically select the timing of its decisions. Second, recurrent democratic breakdowns have repeatedly led to attacks against the court, such as impeachment, irregular dismissals, and/or enlargements. Third, politicians exert broad control of judicial promotions, allowing them to block the careers of independent, courageous judges that act as a check on political power.