This dissertation is devoted to the development of new flow-based formulations for the asymmetric traveling salesman problem (ATSP) and to the demonstration of their applicability in effectively solving some scheduling problems. The ATSP is commonly encountered in the areas of manufacturing planning and scheduling, and transportation logistics. The integration of decisions pertaining to production and shipping, in the supply chain context, has given rise to an additional and practical relevance to this problem especially in situations involving sequence-dependent setups and routing of vehicles. Our objective is to develop new ATSP formulations so that algorithms can be built by taking advantage of their relaxations (of integer variables, thereby, resulting in linear programs) to effectively solve large-size problems. In view of our objective, it is essential to have a formulation that is amenable to the development of an effective solution procedure for the underlying problem. One characteristic of a formulation that is helpful in this regard is its tightness. The tightness of a formulation usually refers to the quality of its approximation to the convex hull of integer feasible solutions. Another characteristic is its compactness. The compactness of a formulation is measured by the number of variables and constraints that are used to formulate a given problem. Our formulations for the ATSP and the scheduling problems that we address are both tight and compact. We present a new class of polynomial length formulations for the asymmetric traveling salesman problem (ATSP) by lifting an ordered path-based model using logical restrictions in concert with the Reformulation-Linearization Technique (RLT). We show that a relaxed version of this formulation is equivalent to a flow-based ATSP model, which, in turn, is tighter than the formulation based on the exponential number of Dantzig-Fulkerson-Johnson (DFJ) subtour elimination constraints. The proposed lifting idea is applied to derive a variety of new formulations for the ATSP, and a detailed analysis of these formulations is carried out to show that some of these formulations are the tightest among those presented in the literature. Computational results are presented to exhibit the relative tightness of our formulations and the efficacy of the proposed lifting process.> While the computational results demonstrate the efficacy of employing the proposed theoretical RLT and logical lifting ideas, yet it remains of practical interest to take due advantage of the tightest formulations. The key requirement to accomplish this is the ability to solve the underlying LP relaxations more effectively. One approach, to that end, is to solve these LP relaxations to (near-) optimality by using deflected subgradient methods on Lagrangian dual formulations. We solve the LP relaxation of our tightest formulation, ATSP6, to (near-) optimality by using a deflected subgradient algorithm with average direction strategy (SA_ADS) (see Sherali and Ulular [69]). We also use two nondifferentiable optimization (NDO) methods, namely, the variable target value method (VTVM) presented by Sherali et al. [66] and the trust region target value method (TRTV) presented by Lim and Sherali [46], on the Lagrangian dual formulation of ATSP6. The preliminary results show that the near-optimal values obtained by the VTVM on solving the problem in the canonical format are the closest to the target optimal values. Another approach that we use is to derive a set of strong valid inequalities based on our tighter formulations through a suitable surrogation process for inclusion within the more compact manageable formulations. Our computational results show that, when the dual optimal solution is available, the associated strong valid inequalities generated from our procedure can successfully lift the LP relaxation of a less tight formulation, such as ATSP2R¯, to be as tight as the tightest formulation, such as ATSP6. We extend our new formulations to include precedence constraints in order to enforce a partial order on the sequence of cities to be visited in a tour. The presence of precedence constraints within the ATSP framework is encountered quite often in practice. Examples include: disassembly optimization (see Sarin et al. [62]), and scheduling of wafers/ ICs on automated testing equipments in a semiconductor manufacturing facility (see Chen and Hsia [17]); among others. Our flow-based ATSP formulation can very conveniently capture these precedence constraints. We also present computational results to depict the tightness of our precedence-constrained asymmetric traveling salesman problem (PCATSP) formulations. We, then, apply our formulations to the hot strip rolling scheduling problem, which involves the processing of hot steel slabs, in a pre-specified precedence order, on one or more rollers. The single-roller hot strip rolling scheduling problem can be directly formulated as a PCATSP. We also consider the multiple-roller hot strip rolling scheduling problem. This gives rise to the multiple-asymmetric traveling salesman problem (mATSP). Not many formulations have been presented in the literature for the mATSP, and there are none for the mATSP formulations involving a precedence order among the cities to be visited by the salesmen, which is the case for the multiple-roller hot strip rolling scheduling problem. To begin with, we develop new formulations for the mATSP and show the validity of our formulations, and present computational results to depict their tightness. Then, we extend these mATSP formulations to include a pre-specified, special type of precedence order in which to process the slabs, and designate the resulting formulations as the restricted precedence-constrained multiple-asymmetric traveling salesman problem (rPCmATSP) formulations. We directly formulate the multiple-roller hot strip rolling scheduling problem as a rPCmATSP. Furthermore, we consider the hot strip rolling scheduling problem with slab selection in which not all slabs need to be processed. We model the single-roller hot strip rolling scheduling problem with slab selection as a multiple-asymmetric traveling salesman problem with exactly two traveling salesmen. Similarly, the multiple-roller hot strip rolling scheduling problem with slab selection is modeled as a multiple-asymmetric traveling salesman problem with (m+1) traveling salesmen. A series of computational experiments are conducted to exhibit the effectiveness of our formulations for the solution of hot strip rolling scheduling problems. Furthermore, we develop two mixed-integer programming algorithms to solve our formulations. These are based on Benders΄ decomposition [13] and are designated Benders΄ decomposition and Modified Benders΄ methods. In concert with a special type of precedence order presented in the hot strip rolling scheduling problems, we further introduce an adjustable density ratio of the associated precedence network and we use randomly generated test problems to study the effect of various density ratios in solving these scheduling problems. Our experimentation shows the efficacy of our methods over CPLEX. Finally, we present a compact formulation for the job shop scheduling problem, designated as JSCD (job shop conjunctive-disjunctive) formulation, which is an extension of our ATSP formulations. We use two test problems given in Muth and Thompson [53] to demonstrate the optimal schedule and the lower bound values obtained by solving the LP relaxations of our formulations. However, we observe that the lower bound values obtained by solving the LP relaxations of all variations of our JSCD formulation equal to the maximum total processing time among the jobs in the problem. / Ph. D.

This dissertation develops efficient solution techniques for general and problem-specific applications within nonconvex optimization, exploiting the constructs of the Reformulation-Linearization Technique (RLT). We begin by developing a technique to enhance general problems in nonconvex optimization through the use of a new class of RLT cuts, called semidefinite cuts. While these cuts are valid for any general problem for which RLT is applicable, we demonstrate their effectiveness in optimizing a nonconvex quadratic objective function over a simplex. Computational results indicate that on average, the semidefinite cuts have reduced the number of nodes in the branch-and-bound tree by a factor of 37.6, while decreasing solution time by a factor of 3.4. The semidefinite cuts have also led to a significant reduction in the optimality gap at termination, in some cases producing optimal solutions for problems that could not be solved using RLT alone. We then narrow our focus to the class of mixed-integer programming (MIP) problems, and develop a modification of Benders' decomposition method using concepts from RLT and lift-and-project cuts. This method is particularly motivated by the class of two-stage stochastic programs with integer recourse. The key idea is to design an RLT or lift-and-project cutting plane scheme for solving the subproblems where the cuts generated have right-hand sides that are functions of the first-stage variables. An illustrative example is provided to elucidate the proposed approach. The focus is on developing a first comprehensive finitely convergent extension of Benders' methodology for problems having 0-1 mixed-integer subproblems. We next address a specific challenging MIP application known as the facility layout problem, and we significantly improve its formulation through outer-linearization techniques and concepts from disjunctive programming. The enhancements produce a substantial increase in the accuracy of the layout produced, while at the same time, providing a dramatic reduction in computational effort. Overall, the maximum error in department size was reduced from about 6% to nearly zero, while solution time decreased by a factor of 110. Previously unsolved test problems from the literature that had defied even approximate solution methods have been solved to exact optimality using our proposed approach. / Ph. D.

L’objectif principal de la présente étude était de dresser un portrait développemental des reformulations orales d’apprenants adultes anglophones (n=124) ayant participé à un programme d’immersion à l’étranger (PIE) de cinq semaines en français langue seconde (FLS). Plus particulièrement, cette étude s’est servi des autoreformulations autoamorcées (ARAA) produites, c’est-à-dire les réparations du discours initiées personnellement par le locuteur et ce, lors de deux épreuves de narration (T1 et T2) pour comprendre les comportements d’ARAA en FLS chez ces apprenants, plus spécifiquement leur nature et leur précision. L’étude visait deux groupes de participants distincts, soit ceux qui étaient les plus débutants et les plus avancés en FLS lors de leur entrée au PIE, et cherchait à comprendre leur développement par rapport à la nature, la compétence et la précision de leurs ARAA. Les résultats ont montré une augmentation du nombre et de la précision des ARAA peu importe le niveau des apprenants.

Ce mémoire porte sur l'analyse des brouillons scolaires d'étudiants de niveau collégial de la ville de Chicoutimi. Nous nous inspirons des recherches en génétique textuelle et surtout de leurs développements en linguistique et en didactique des langues. Nous avons analysé des brouillons de textes argumentatifs pour identifier les types de rature (remplacement, ajout, suppression et déplacement) opérés sur les connecteurs et les marqueurs d'intégration linéaire (MIL) et pour voir comment, par les ratures et les réécritures, les étudiants géraient le processus rédactionnel. Quatre-vingt-dix brouillons et copie finales, produits en classe, ont été analysés. Cependant, l'exhaustivité des données recueillies, nous a amené à nous concentrer davantage sur les seules opérations de remplacement. Notre recherche montre que les connecteurs et les MIL sont objets d'un grand investissement par des ratures et des réécritures de la part des collégiens. Il se dégage chez les étudiants une représentation du texte argumentatif comme construit par les connecteurs et les MIL de cohérence relationnelle, logique et pragmatique. Les connecteurs sont plus sujets de réécriture que les MIL. Il nous est apparu que le dispositif macro textuel que les MIL permettent de construire est plus stable que celui des connecteurs dont l'utilisation paraissait plus complexe aux étudiants. Cette complexité se situe à différents niveaux : constructions syntaxiques, relations inter propositionnelles, relations interphrastiques, relations logico-sémantiques et valeurs pragmatiques. Les connecteurs Et et Donc ont été ceux qui ont le plus occasionné des réécritures. L'observation des ratures montre que la réécriture pouvait déboucher sur des améliorations mais pas toujours. Nous avons ainsi décelé quelques observations sur la maîtrise ou non des connecteurs et des MIL par les étudiants et avons avancé quelques pistes pédagogiques pour amener les enseignants à considérer les brouillons comme un outil didactique pour l'appui à l'amélioration de la compétence rédactionnelle des étudiants.

本篇論文的目的在於探討兒童在親子對話中行使重新請求 (request reformulation) 的情況，研究問題如下: 1.兒童採取哪些重新請求的策略以達到請求的目的? 2.親子對話中，常見的重新請求的序列模式（patterns of request reformulation sequences）為何？ 2.如何從兒童重新請求的使用反映出角色取代能力 (perspective-taking ability )的發展? 研究對象為一位三歲和一位六歲的男孩。研究結果顯示隨著年紀的增長，兒童能使用更多元的重新請求策略。研究也發現造成請求失敗的原因隨著不同年齡的兒童有所差異。隨著年紀的增長，兒童面臨的失敗原因和挑戰日漸複雜、困難，兒童會依據不同的失敗原因採取重新請求的策略。最後，研究顯示不同年齡兒童採取的重新請求策略可以展現出他們不同階段的角色取代能力的發展。三歲的兒童無法跳脫自己的觀點而從別人的角度來看待自己的請求，所以重新請求著重於強調自己的需求。六歲的兒童較能夠從別人的立場看待自己的請求，所以他較有能力在考量對方的觀點和利益之後採用對雙方有益的策略。 / The purpose of this study is to explore how children at different age make reformulation to compensate for an unsuccessful request. Firstly, we aim to investigate what reformulation strategies children apply and the patterns of reformulation sequences. Second, we further aim to explore how children’s use of reformulation strategies reveals the development of perspective-taking ability. The data analyzed are natural conversations of two Mandarin-speaking mother-child dyads. Subjects in this present study are two male children. One subject is three years and six months old and the other is six years old. The strategies of request reformulation adopted in this study are mainly based on Levin and Rubin’s (1984) categorization. The results show that children would have a greater variety of reformulation strategies as they get older. Furthermore, aggravation and explanation are both children’s main strategies of reformulation. With the growth of age, children decrease the use of aggravation and increase the use of bargain and mitigation. Furthermore, the results of reformulation sequences reveal that the two children are confronted with different causes of the failure to obtain compliance, which influences their adoption of reformulation strategies. The younger child faced the communicative breakdown and his mother’s ignorance while the older child encountered his mother’s queries and disagreements. Finally, the two children’s application of reformulation strategies revealed their different ability to take the other’s perspectives. The younger child’s reliance on aggravation and speaker-oriented negotiation reveals that he is embedded in his own viewpoints and is less able to view his request from the hearer’s viewpoints while the older child is more able to view the request from the hearer’ perspective and take her benefits into account. Our findings throw some light on children’s use of request reformulation strategy and the development of the perspective-taking ability.

Durante as décadas de 70 e 80, desenvolveram-se métodos baseados em penalidades exatas diferenciáveis para resolver problemas de otimização não linear com restrições. Uma desvantagem dessas penalidades é que seus gradientes contêm termos de segunda ordem em suas fórmulas, o que impede a utilização de métodos do tipo Newton para resolver o problema. Para contornar essa dificuldade, utilizamos uma ideia de construção de penalidade exata para desigualdades variacionais, introduzida recentemente por André e Silva. Essa construção consiste em incorporar um estimador de multiplicadores, proposto por Glad e Polak, no lagrangiano aumentado para desigualdades variacionais. Nesse trabalho, estendemos o estimador de multiplicadores para restrições gerais de igualdade e desigualdade, e enfraquecemos a hipótese de regularidade. Como resultado, obtemos uma função penalidade exata continuamente diferenciável e uma nova reformulação do sistema KKT associado a problemas não lineares. A estrutura dessa reformulação permite a utilização do método de Newton semi-suave, e a taxa de convergência local superlinear pode ser provada. Além disso, verificamos que a penalidade exata construída pode ser usada para globalizar o método, levando a uma abordagem do tipo Gauss-Newton. Por fim, realizamos experimentos numéricos baseando-se na coleção CUTE de problemas de teste. / During the 1970\'s and 1980\'s, methods based on differentiable exact penalty functions were developed to solve constrained optimization problems. One drawback of these functions is that they contain second-order terms in their gradient\'s formula, which do not allow the use of Newton-type methods. To overcome such difficulty, we use an idea for construction of exact penalties for variational inequalities, introduced recently by André and Silva. This construction consists on incorporating a multipliers estimate, proposed by Glad and Polak, in the augmented Lagrangian function for variational inequalities. In this work, we extend the multipliers estimate to deal with both equality and inequality constraints and we weaken the regularity assumption. As a result, we obtain a continuous differentiable exact penalty function and a new equation reformulation of the KKT system associated to nonlinear problems. The formula of such reformulation allows the use of semismooth Newton method, and the local superlinear convergence rate can be also proved. Besides, we note that the exact penalty function can be used to globalize the method, resulting in a Gauss-Newton-type approach. We conclude with some numerical experiments using the collection of test problems CUTE.

The presented thesis discusses bilevel programming problems with the focus on solution algorithms. Bilevel programming problem is a hierarchical programming problem, where constraints contain another programming problem. We formulate basic bilevel optimization theory and describe three types of so- lution algorithms for bilevel programming problems: Algorithms based on KKT reformulation where the lower level is replaced by its KKT conditions, algorithms based on optimal value function where the bilevel programming problem is re- duced to a single level problem using the optimal value function of the lower level problem, and algorithms solving linear bilevel programming problems. Using real data for portfolio optimization bilevel programming problems, we compare ability to solve the problems and computing time of some of the pre- sented algorithms. 1

Durante as décadas de 70 e 80, desenvolveram-se métodos baseados em penalidades exatas diferenciáveis para resolver problemas de otimização não linear com restrições. Uma desvantagem dessas penalidades é que seus gradientes contêm termos de segunda ordem em suas fórmulas, o que impede a utilização de métodos do tipo Newton para resolver o problema. Para contornar essa dificuldade, utilizamos uma ideia de construção de penalidade exata para desigualdades variacionais, introduzida recentemente por André e Silva. Essa construção consiste em incorporar um estimador de multiplicadores, proposto por Glad e Polak, no lagrangiano aumentado para desigualdades variacionais. Nesse trabalho, estendemos o estimador de multiplicadores para restrições gerais de igualdade e desigualdade, e enfraquecemos a hipótese de regularidade. Como resultado, obtemos uma função penalidade exata continuamente diferenciável e uma nova reformulação do sistema KKT associado a problemas não lineares. A estrutura dessa reformulação permite a utilização do método de Newton semi-suave, e a taxa de convergência local superlinear pode ser provada. Além disso, verificamos que a penalidade exata construída pode ser usada para globalizar o método, levando a uma abordagem do tipo Gauss-Newton. Por fim, realizamos experimentos numéricos baseando-se na coleção CUTE de problemas de teste. / During the 1970\'s and 1980\'s, methods based on differentiable exact penalty functions were developed to solve constrained optimization problems. One drawback of these functions is that they contain second-order terms in their gradient\'s formula, which do not allow the use of Newton-type methods. To overcome such difficulty, we use an idea for construction of exact penalties for variational inequalities, introduced recently by André and Silva. This construction consists on incorporating a multipliers estimate, proposed by Glad and Polak, in the augmented Lagrangian function for variational inequalities. In this work, we extend the multipliers estimate to deal with both equality and inequality constraints and we weaken the regularity assumption. As a result, we obtain a continuous differentiable exact penalty function and a new equation reformulation of the KKT system associated to nonlinear problems. The formula of such reformulation allows the use of semismooth Newton method, and the local superlinear convergence rate can be also proved. Besides, we note that the exact penalty function can be used to globalize the method, resulting in a Gauss-Newton-type approach. We conclude with some numerical experiments using the collection of test problems CUTE.

Made available in DSpace on 2015-04-22T22:16:06Z (GMT). No. of bitstreams: 1 daiana santos.pdf: 1011976 bytes, checksum: 0d1f23d4c01774fbad224c1c0fbe0359 (MD5) Previous issue date: 2013-09-23 / FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas / In this dissertation, we present a proximal point method for solving problems balance in Hilbert spaces proposed by Alfredo Iusem and Wilfredo Sosa in [1]. We analyzed the convergence of this mehtod for troubleshooting balance. We verified the sequence generated by the method of classical proximal point and generated sequence the proximal point method to balance problems are the same. These results were obtained using variations of monotonicity of the function that defines the balance problem. In the final analysis is made on the weakening of the hypothesis assumed by function. / Nesta dissertação, apresentamos um método de ponto proximal para resolução de problemas de equilíbrio em espaços de Hilbert proposto por Alfredo Iusem e Wilfredo Sosa em [1]. Analisamos a convergência deste método para soluções de problemas de equilíbrio. Verificamos que a sequência gerada pelo método de ponto proximal clássico e a sequência gerada pelo método de ponto proximal para problemas de equilíbrio coincidem. Esses resultados foram obtidos usando variações de monotonicidade sobre a função que define o problema de equilíbrio. Uma análise final é feita sobre o enfraquecimento das hipóteses assumidas pela função.

In many institutional settings in today’s globalized job market, people have to deal with different role asymmetries in the co-construction of meaning. In this study, institutional, cultural and linguistic asymmetries are focused on in interviews at an employment agency in Sweden. Interviews between a recruiter and fourteen female job candidates with an academic background from other countries were video taped. Three sequences on personality were analysed: What do you consider to be your strengths? What personal characteristics do you want to improve? and What has made an impact on you? The general aim of the study was to gain knowledge of the processes whereby self-presentations are co-constructed and how participants try to reach common understanding when they do not share common linguistic and cultural resources. Theoretically, the study has a dialogical framework. Discourse is seen as the place where society, culture, situation, individual and language meet and where meaning is constructed through social action. Within an interactional sociolinguistics framework, an holistic approach to methods combines ethnography of communication with ethnomethodology and conversation analysis. The results show that the meaning-making project in this institutional situation is institutionally framed, culturally hidden, socially constrained by face-work and interactionally embedded. The recruiter orients to the institutional frame by embedding reformulations of the candidates’ answers in her uptake, often an adjective, which is filled in on a form and later transferred to a data base. The recruiter also takes on the face-work of the communicative dilemmas that the questions exhibit, for example by using explanations when candidates admit to low self-confidence. It is also shown that for some candidates the hidden agenda of the situation is concealed and that their communicative styles clash with the recruiter’s expectations. The asymmetrical situation can for the candidates be seen as both a resource and a constraint. The linguistic asymmetry is not foregrounded. Instead, the negotiation of meaning concerns the institutional and cultural frame rather than linguistic meanings. On the other hand, the recruiter shows a tendency to normalize the candidates according to her own institutional and cultural knowledge. This dynamic interplay between heterogenization and homogenization tendencies is an important feature in the interviews.