Lagrangian-informed mixed integer programming reformulations

La programmation linéaire en nombres entiers est une approche robuste qui permet de résoudre rapidement de grandes instances de problèmes d'optimisation discrète. Toutefois, les problèmes gagnent constamment en complexité et imposent parfois de fortes limites sur le temps de calcul. Il devient alors nécessaire de développer des méthodes spécialisées afin de résoudre approximativement ces problèmes, tout en calculant des bornes sur leurs valeurs optimales afin de prouver la qualité des solutions obtenues. Nous proposons d'explorer une approche de reformulation en nombres entiers guidée par la relaxation lagrangienne. Après l'identification d'une forte relaxation lagrangienne, un processus systématique permet d'obtenir une seconde formulation en nombres entiers. Cette reformulation, plus compacte que celle de Dantzig et Wolfe, comporte exactement les mêmes solutions entières que la formulation initiale, mais en améliore la borne linéaire: elle devient égale à la borne lagrangienne. L'approche de reformulation permet d'unifier et de généraliser des formulations et des méthodes de borne connues. De plus, elle offre une manière simple d'obtenir des reformulations de moins grandes tailles en contrepartie de bornes plus faibles. Ces reformulations demeurent de grandes tailles. C'est pourquoi nous décrivons aussi des méthodes spécialisées pour en résoudre les relaxations linéaires. Finalement, nous appliquons l'approche de reformulation à deux problèmes de localisation. Cela nous mène à de nouvelles formulations pour ces problèmes; certaines sont de très grandes tailles, mais nos méthodes de résolution spécialisées les rendent pratiques.

A priori reformulations for joint rolling-horizon scheduling of materials processing and lot-sizing problem

In many production processes, a key material is prepared and then transformed into different final products. The lot sizing decisions concern not only the production of final products, but also that of material preparation in order to take account of their sequence-dependent setup costs and times. The amount of research in recent years indicates the relevance of this problem in various industrial settings. In this paper, facility location reformulation and strengthening constraints are newly applied to a previous lot-sizing model in order to improve solution quality and computing time. Three alternative metaheuristics are used to fix the setup variables, resulting in much improved performance over previous research, especially regarding the use of the metaheuristics for larger instances. © 2013 Elsevier Ltd. All rights reserved.

Patterns of query reformulation during web searching

Query reformulation is a key user behavior during Web search. Our research goal is to develop predictive models of query reformulation during Web searching. This article reports results from a study in which we automatically classified the query-reformulation patterns for 964,780 Web searching sessions, composed of 1,523,072 queries, to predict the next query reformulation. We employed an n-gram modeling approach to describe the probability of users transitioning from one query-reformulation state to another to predict their next state. We developed first-, second-, third-, and fourth-order models and evaluated each model for accuracy of prediction, coverage of the dataset, and complexity of the possible pattern set. The results show that Reformulation and Assistance account for approximately 45% of all query reformulations; furthermore, the results demonstrate that the first- and second-order models provide the best predictability, between 28 and 40% overall and higher than 70% for some patterns. Implications are that the n-gram approach can be used for improving searching systems and searching assistance.

Predicting query reformulation during web searching

This paper reports results from a study in which we automatically classified the query reformulation patterns for 964,780 Web searching sessions (composed of 1,523,072 queries) in order to predict what the next query reformulation would be. We employed an n-gram modeling approach to describe the probability of searchers transitioning from one query reformulation state to another and predict their next state. We developed first, second, third, and fourth order models and evaluated each model for accuracy of prediction. Findings show that Reformulation and Assistance account for approximately 45 percent of all query reformulations. Searchers seem to seek system searching assistant early in the session or after a content change. The results of our evaluations show that the first and second order models provided the best predictability, between 28 and 40 percent overall, and higher than 70 percent for some patterns. Implications are that the n-gram approach can be used for improving searching systems and searching assistance in real time.

User-web interactions : how wholistic/analytic web users search the web?

User-Web interactions have emerged as an important research in the field of information science. In this study, we examine extensively the Web searching performed by general users. Our goal is to investigate the effects of users’ cognitive styles on their Web search behavior in relation to two broad components: Information Searching and Information Processing Approaches. We use questionnaires, a measure of cognitive style, Web session logs and think-aloud as the data collection instruments. Our study findings show wholistic Web users tend to adopt a top-down approach to Web searching, where the users searched for a generic topic, and then reformulate their queries to search for specific information. They tend to prefer reading to process information. Analytic users tend to prefer a bottom-up approach to information searching and they process information by scanning search result pages.

Defining a session on Web search engines

Detecting query reformulations within a session by a Web searcher is an important area of research for designing more helpful searching systems and targeting content to particular users. Methods explored by other researchers include both qualitative (i.e., the use of human judges to manually analyze query patterns on usually small samples) and nondeterministic algorithms, typically using large amounts of training data to predict query modification during sessions. In this article, we explore three alternative methods for detection of session boundaries. All three methods are computationally straightforward and therefore easily implemented for detection of session changes. We examine 2,465,145 interactions from 534,507 users of Dogpile.com on May 6, 2005. We compare session analysis using (a) Internet Protocol address and cookie; (b) Internet Protocol address, cookie, and a temporal limit on intrasession interactions; and (c) Internet Protocol address, cookie, and query reformulation patterns. Overall, our analysis shows that defining sessions by query reformulation along with Internet Protocol address and cookie provides the best measure, resulting in an 82% increase in the count of sessions. Regardless of the method used, the mean session length was fewer than three queries, and the mean session duration was less than 30 min. Searchers most often modified their query by changing query terms (nearly 23% of all query modifications) rather than adding or deleting terms. Implications are that for measuring searching traffic, unique sessions may be a better indicator than the common metric of unique visitors. This research also sheds light on the more complex aspects of Web searching involving query modifications and may lead to advances in searching tools.

Human–computer interaction : the impact of users’ cognitive styles on query reformulation behaviour during web searching

This paper discusses users’ query reformulation behaviour while searching information on the Web. Query reformulations have emerged as an important component of Web search behaviour and human-computer interaction (HCI) because a user’s success of information retrieval (IR) depends on how he or she formulates queries. There are various factors, such as cognitive styles, that influence users’ query reformulation behaviour. Understanding how users with different cognitive styles formulate their queries while performing Web searches can help HCI researchers and information systems (IS) developers to provide assistance to the users. This paper aims to examine the effects of users’ cognitive styles on their query reformation behaviour. To achieve the goal of the study, a user study was conducted in which a total of 3613 search terms and 872 search queries were submitted by 50 users who engaged in 150 scenario-based search tasks. Riding’s (1991) Cognitive Style Analysis (CSA) test was used to assess users’ cognitive style as wholist or analytic, and verbaliser or imager. The study findings show that users’ query reformulation behaviour is affected by their cognitive styles. The results reveal that analytic users tended to prefer Add queries while all other users preferred New queries. A significant difference was found among wholists and analytics in the manner they performed Remove query reformulations. Future HCI researchers and IS developers can utilize the study results to develop interactive and user-cantered search model, and to provide context-based query suggestions for users.

Patterns of Transcendence : Classical Myth in Marina Tsvetaeva's Poetry of the 1920s

This study examines the position and meaning of Classical mythological plots, themes and characters in the oeuvre of the Russian Modernist poet Marina Tsvetaeva (1892-1941). The material consists of lyric poems from the collection Posle Rossii (1928) and two longer lyrical tragedies, Ariadna (1924) and Fedra (1927). These works are examined in the context of Russian Modernism and Tsvetaeva s own poetic development, also taking into account the author s biography, namely, her correspondence with Boris Pasternak. Tsvetaeva s appropriations of the myths enter into a dialogue with the Classical tradition and with the earlier Russian and Western literary manifestations of the source material. Her Classical texts are inextricably linked with her own authorial myth, they are used to project both her ideas about poetry as well as the authored self of her poems. An important context for Tsvetaeva s application of the Classical myths is the concept of the Platonic ladder of Eros. This plot evokes the process of transcendence of the mortal subject into the immaterial realm and is applied by the author as an extended metaphor of the poet s birth. Emphasizing the dialectical movement between the earthly and the divine, Tsvetaeva s Classical personae foreground various positions of the individual between these two realms. By means of kaleidoscopic reformulations of similar metaphors and concepts, Tsvetaeva s mythological poems illustrate the poet s position between the material and the immaterial and the various consequences of this dichotomy on the creative mission. At the heart of Tsvetaeva s appropriation of the Sibyl, Phaedra, Eurydice and Ariadne is the tension between the body and disembodiment. The two lyrical tragedies develop the dichotomous worldview further, nevertheless emphasizing the dual perspective of the divine and the earthly realms: immaterial existence is often evaluated from a material perspective and vice versa. The Platonic subtext is central for Ariadna, focussing on Theseus development from an earthly hero to a spiritual one. Fedra concentrates on Phaedra s divinely induced physical passion, which is nevertheless evoked in a creative light.

Identidade pessoal uma análise crítica da teoria da memória

O objetivo dessa dissertação é realizar uma análise crítica da teoria que intenta explicar a natureza e a evidência da identidade pessoal através da memória. A primeira versão dessa teoria foi proposta por John Locke, a qual, devido à sua distinção entre pessoa, homem e substância, traçou os parâmetros fundamentais das discussões posteriores acerca da natureza da identidade pessoal. No entanto, essa proposta apresenta sérias fragilidades e inconsistências, apontadas de forma vigorosa principalmente por Joseph Butler e Thomas Reid. Posteriormente, autores como Parfit, Shoemaker e Grice realizaram reformulações na teoria lockeana com o objetivo de sanar suas inconsistências e assim responder à suas principais objeções, sem com isso perder seu aspecto central e característico, que é conceber a memória como elemento fundamental para o entendimento da identidade pessoal. Esse processo envolvendo a teoria lockeana, suas objeções e reformulações terá como resultado final a noção de identidade pessoal como continuidade psicológica não-ramificada.

Refigurando monstros: a perspectiva parcial de Donna Haraway como crítica da ciência

Esta dissertação trata das relações de poder que marcam a produção científica ocidental moderna a partir da abordagem dos estudos sobre Gênero e Ciência da feminista historiadora da ciência estadunidense Donna Haraway. Esta autora propõe a concepção de toda a produção de conhecimento como pratica política, assumindo a perspectiva parcial como fundamento para uma ciência objetiva e apontando a perspectiva de objetividade calcada na ideia de imparcialidade como produtora de um tipo de saber que historicamente serviu como instrumento de dominação: o conhecimento que se propõe como universal. Em sua narrativa, o androcentrismo, o etnocentrismo, o racismo e as divisões de classe operam na conformação e nas transformações desta ciência a partir da construção de um sujeito privilegiado do conhecimento, o cientista, figura constituída a imagem e semelhança do homem branco ocidental independente. Meu recorte de sua obra são as reformulações dessas relações ao longo da historia da ciência ocidental moderna observadas por ela na emergência e nas produções de um conjunto especifico de disciplinas do campo das ciências naturais biológicas, fortemente marcadas pelas teorias e tecnologias da informação e da comunicação produzidas no campo da cibernética. Na construção de um discurso critico sobre os saberes / poderes hegemônicos, Haraway traz para a cena da ciência figuras monstruosas, entre elas o ciborgue, tanto como meio de revelar categorias culturais atuando na produção do conhecimento como para materializar novos significados para natureza, os corpos e as relações de diferença. Em conexão com esses monstros, refigurados em suas narrativas, a autora defende uma relação de conexão, e não de divisão, entre sujeito e objeto do saber.

O PROEJA na Rede de Ensino FAETEC: um estudo sobre a implementação e organização curricular na ETE Ferreira Viana - caminhos e descaminhos

Esta pesquisa tem por objetivo analisar a organização curricular do PROEJA na Escola Técnica Estadual Ferreira Viana, uma das unidades da rede de ensino FAETEC, suas implicações no processo da formação humana e nos processos de subjetivação balizados em Foucault. Desta forma, buscouse descrever o desenvolvimento das políticas públicas implementadas pelo governo federal no período de 2009 a 2014, para a Educação Profissional de Jovens e Adultos, bem como discutir os efeitos desta implementação nesta rede de ensino. Adotouse a utilização de procedimentos metodológicos inicialmente através de uma análise documental e levantamento de dados estatísticos sobre entrada, retenção e saída de alunos. Após esta identificação foi realizado um registro de campo e entrevistas semi-estruturadas com os agentes envolvidos neste processo, no sentido de maior aproximação com o cotidiano de ensino desta unidade escolar. Por último e como foco principal, foi desenvolvido uma análise sobre a organização curricular do PROEJA na Escola Técnica Estadual Ferreira Viana da Rede de Ensino FAETEC, com o intuito de melhor compreender como se estabelecem as relações neste processo de sistematização curricular, tendo em vista a análise de sua estrutura, as ações estabelecidas pelos docentes na aplicação do ensino, a realidade vivida no processo de aprendizagem dos alunos, e os desafios da integração curricular e suas possíveis reformulações, frente às exigências da educação profissional no contexto atual da educação brasileira

Convex relaxation of mixture regression with efficient algorithms

We develop a convex relaxation of maximum a posteriori estimation of a mixture of regression models. Although our relaxation involves a semidefinite matrix variable, we reformulate the problem to eliminate the need for general semidefinite programming. In particular, we provide two reformulations that admit fast algorithms. The first is a max-min spectral reformulation exploiting quasi-Newton descent. The second is a min-min reformulation consisting of fast alternating steps of closed-form updates. We evaluate the methods against Expectation-Maximization in a real problem of motion segmentation from video data.

Dialogic Signals In Argumentative Discussions of Advanced Polish Learners Of English

The first part of the paper deals with characteristics of classroom interaction as a type of institutional talk in a conversational analytic perspective. Next, the thesis is discussed concerning developing learners' interactional competence to foster learner discursive independence in argumentative discussions in English as a foreign language. Finally, after a short review of dialogic signals, the article presents a preliminary analysis of selected dialogic signals: evaluating reformulations and piggybacking as the ways of achieving reciprocity in argumentative discussions.

Dialogic Signals In Argumentative Discussions of Advanced Polish Learners Of English

The first part of the paper deals with characteristics of classroom interaction as a type of institutional talk in a conversational analytic perspective. Next, the thesis is discussed concerning developing learners' interactional competence to foster learner discursive independence in argumentative discussions in English as a foreign language. Finally, after a short review of dialogic signals, the article presents a preliminary analysis of selected dialogic signals: evaluating reformulations and piggybacking as the ways of achieving reciprocity in argumentative discussions.

From the demise of theory to its resurgence. A retrospective on the postmodern turn to rethink the 'desire for narrative' and the sublime untimeliness of emancipation

Cultural Marxist Theory, commonly known as theory, enjoyed a moment of extraordinary success in the 1970s, when the works of leading post-war French philosophers were published in English. After relocating to Anglophone academia, however, theory disavowed its original concerns and lost its ambition to understand the world as a whole, becoming the play of heterogeneities associated with postcolonialism, multiculturalism and identity politics, commonly referred to as postmodern theory. This turn, which took place during a period that seemed to have spelt the death of Marxism, the 1990s, induced many of its supporters to engage in an ongoing funeral wake designating the merits of theory and dreaming its resurgence. According to them, had theory been resurrected in historical circumstances completely different from those which had led to its rise, it would have never reacquired the significance that had originally connoted it. This thesis demonstrates how theory has survived its demise and entirely regained its prominence in our socio-political context marked by the effects of the latest crisis of capitalism and by the global threat of terrorisms rooted in messianic eschatologies. In its current form theory does no longer need to show allegiance to certain intellectual stances or political groupings in order to produce important reformulations of the projects it once gave life to. Though less overtly radical and epistemologically bounded, theory remains a necessary form of enquiry justified by the political commitment which originated it in the first place. Its voice continues to speak to us about justice ‘where it is not yet, not yet there, where it is no longer’ (Derrida, 1993, XVIII).