Some reformulations for the quadratic assignment problem

Kombinatorisk optimering handlar om att hitta en bra eller rent av den bästa möjliga lösningen från ett känt antal lösningar eller kombinationer. Ofta är antalet lösningar så enormt att en genomgång av alla olika lösningar inte är möjlig. En av huvudorsakerna till att det forskas inom kombinatorisk optimering är att liknande frågeställningar eller problem uppkommer inom så många olika områden. Påståendet stämmer speciellt bra för kvadratiska tilldelningsproblem(eng. Quadratic Assignment Problem). Sådana problem uppstår då man försöker beskriva en stor mängd tillämpade frågeställningar. Vilken gate skall väljas för flygen på större flygplatser för att minimera den totala väg människorna behöver gå och bagaget förflyttas? Var skall olika avdelningar på en fabrik placeras för att minimera materialförflyttningar mellan avdelningarna? Hur ser ett optimalt tangentbord ut för olika språk? Var skall komponenterna placeras på ett kretskort? De här är alla frågor som kan besvaras genom att lösa kvadratiska tilldelningsproblem. Kvadratiska tilldelningsproblem är dock mycket svåra att lösa. Det beror på att problemet i den standardform det matematiskt formuleras i huvudsak består av produkter av binära variabler. I denna avhandling har problemet omformulerats till en linjär diskret form som innehåller färre variabler. Med omformuleringen har bland annat flera tidigare olösta kvadratiska tilldelningsproblem kunnat lösas till globalt optimum, den bästa möjliga lösningen, för första gången någonsin.

Cost Models for Routing and Wavelength Assignment in Wavelength-Division Multiplexing Optical Net

WDM (Wavelength-Division Multiplexing) optiset verkot on tällä hetkellä suosituin tapa isojen määrän tietojen siirtämiseen. Jokaiselle liittymälle määrätään reitin ja aallonpituus joka linkin varten. Tarvittavan reitin ja aallon pituuden löytäminen kutsutaan RWA-ongelmaksi. Tämän työn kuvaa mahdollisia kustannuksen mallein ratkaisuja RWA-ongelmaan. Olemassa on paljon erilaisia optimoinnin tavoitteita. Edellä mainittuja kustannuksen malleja perustuu näillä tavoitteilla. Kustannuksen malleja antavat tehokkaita ratkaisuja ja algoritmeja. The multicommodity malli on käsitelty tässä työssä perusteena RV/A-kustannuksen mallille. Myöskin OB käsitelty heuristisia menetelmiä RWA-ongelman ratkaisuun. Työn loppuosassa käsitellään toteutuksia muutamalle mallille ja erilaisia mahdollisuuksia kustannuksen mallein parantamiseen.

Algorithmic Solutions for Combinatorial Problems in Resource Management of Manufacturing Environments

This thesis studies the use of heuristic algorithms in a number of combinatorial problems that occur in various resource constrained environments. Such problems occur, for example, in manufacturing, where a restricted number of resources (tools, machines, feeder slots) are needed to perform some operations. Many of these problems turn out to be computationally intractable, and heuristic algorithms are used to provide efficient, yet sub-optimal solutions. The main goal of the present study is to build upon existing methods to create new heuristics that provide improved solutions for some of these problems. All of these problems occur in practice, and one of the motivations of our study was the request for improvements from industrial sources. We approach three different resource constrained problems. The first is the tool switching and loading problem, and occurs especially in the assembly of printed circuit boards. This problem has to be solved when an efficient, yet small primary storage is used to access resources (tools) from a less efficient (but unlimited) secondary storage area. We study various forms of the problem and provide improved heuristics for its solution. Second, the nozzle assignment problem is concerned with selecting a suitable set of vacuum nozzles for the arms of a robotic assembly machine. It turns out that this is a specialized formulation of the MINMAX resource allocation formulation of the apportionment problem and it can be solved efficiently and optimally. We construct an exact algorithm specialized for the nozzle selection and provide a proof of its optimality. Third, the problem of feeder assignment and component tape construction occurs when electronic components are inserted and certain component types cause tape movement delays that can significantly impact the efficiency of printed circuit board assembly. Here, careful selection of component slots in the feeder improves the tape movement speed. We provide a formal proof that this problem is of the same complexity as the turnpike problem (a well studied geometric optimization problem), and provide a heuristic algorithm for this problem.

Zum Problem der Übersetzung von Gedichten : auch vom Gesichtspunkt des Computers

Abstract

Generating a raster map presentation of a forest resource by solving a transportation problem

Abstract

Product Line Profitability- Case Halton Indoors

Diplomityön tavoitteena on rakentaa malli kohdeyrityksen yhden strategisen liiketoimintayksikön tuoteryhmänkohtaisten kannattavuuksien selvittämiseksi yli kokotoimitusketjun. Työssä on keskitytty vain välillisiin kustannuksiin ja välittömien kustannusten osalta on luotettu toiminnanohjausjärjestelmän antamiin tietoihin. Työn lähtökohtana ja teoreettisena viitekehikkona on toimintoperustainen kustannuslaskenta, jonka periaatteita noudattaen kannattavuusmalli rakennettiin. Mallin periaatteet on esitetty työssä mutta sen tuottamia tuloksia ei ole syvemmin analysoitu. Ongelma osoittautui haasteelliseksi ja tulosten verifiointi lähes mahdottomaksi käytettyjen subjektiivisten arvioiden ja ennalta odottamattomien välittömien tuotekustannusten suurten virheiden vuoksi. Työn johtopäätöksissä keskitytään sisäisen laskentatoimen kulttuurin kehittämiseen tuotekustannuslaskennan ja yleisen kustannusvalvonnan näkökulmasta kohdeyrityksessä.

Peso problem anddevaluation expectations: Evidence from Latin America

Tämän tutkielman tavoitteena on tutkia peso-ongelmaa sekä devalvaatio-odotuksia seuraavissa Latinalaisen Amerikan maissa: Argentiina, Brasilia, Costa Rica, Uruguay ja Venezuela. Lisäksi tutkitaan, onko peso-ongelmalla mahdollista selittää korkojen epäsäännöllistä käyttäytymistä ennen todellisen devalvaation tapahtumista. Jotta näiden tutkiminen olisi mahdollista, lasketaan markkinoiden odotettu devalvaation todennäköisyys tutkittavissa maissa. Odotettu devalvaation todennäköisyys lasketaan aikavälillä tammikuusta 1996 joulukuuhun 2006 käyttäen kahta erilaista mallia. Korkoero-mallin mukaan maiden välisestä korkoerosta on mahdollista laskea markkinoiden devalvaatio-odotukset. Toiseksi, Probit-mallissa käytetään useita makrotaloudellisia tekijöitä selittävinä muuttujina laskettaessa odotettua devalvaation todennäköisyyttä. Lisäksi tutkitaan, miten yksittäisten makrotaloudellisten muuttujien kehitys vaikuttaa odotettuun devalvaation todennäköisyyteen. Empiiriset tulokset osoittavat, että tutkituissa Latinalaisen Amerikan maissa oli peso-ongelma aikavälillä tammikuusta 1996 joulukuuhun 2006. Korkoero-mallin tulosten mukaan peso-ongelma löytyi kaikista muista tutkituista maista lukuun ottamatta Argentiinaa. Vastaavasti Probit-mallin mukaan peso-ongelma löytyi kaikista tutkituista maista. Tulokset osoittavat myös, että korkojen epäsäännöllinen kehitys ennen varsinaista devalvaatiota on mahdollista selittää peso-ongelmalla. Probit-mallin tulokset osoittavat lisäksi, että makrotaloudellisten muuttujien kehityksellä ei ole mitään tiettyä kaavaa liittyen siihen, kuinka ne vaikuttavat markkinoiden devalvaatio-odotuksiin Latinalaisessa Amerikassa. Pikemmin vaikutukset näyttävät olevan maakohtaisia.

Patents in the Information and Communications Technology Sector - Development Trends, Problem Areas and Pressures for Change

The patent system was created for the purpose of promoting innovation by granting the inventors a legally defined right to exclude others in return for public disclosure. Today, patents are being applied and granted in greater numbers than ever, particularly in new areas such as biotechnology and information andcommunications technology (ICT), in which research and development (R&D) investments are also high. At the same time, the patent system has been heavily criticized. It has been claimed that it discourages rather than encourages the introduction of new products and processes, particularly in areas that develop quickly, lack one-product-one-patent correlation, and in which theemergence of patent thickets is characteristic. A further concern, which is particularly acute in the U.S., is the granting of so-called 'bad patents', i.e. patents that do not factually fulfil the patentability criteria. From the perspective of technology-intensive companies, patents could,irrespective of the above, be described as the most significant intellectual property right (IPR), having the potential of being used to protect products and processes from imitation, to limit competitors' freedom-to-operate, to provide such freedom to the company in question, and to exchange ideas with others. In fact, patents define the boundaries of ownership in relation to certain technologies. They may be sold or licensed on their ownor they may be components of all sorts of technology acquisition and licensing arrangements. Moreover, with the possibility of patenting business-method inventions in the U.S., patents are becoming increasingly important for companies basing their businesses on services. The value of patents is dependent on the value of the invention it claims, and how it is commercialized. Thus, most of them are worth very little, and most inventions are not worth patenting: it may be possible to protect them in other ways, and the costs of protection may exceed the benefits. Moreover, instead of making all inventions proprietary and seeking to appropriate as highreturns on investments as possible through patent enforcement, it is sometimes better to allow some of them to be disseminated freely in order to maximize market penetration. In fact, the ideology of openness is well established in the software sector, which has been the breeding ground for the open-source movement, for instance. Furthermore, industries, such as ICT, that benefit from network effects do not shun the idea of setting open standards or opening up their proprietary interfaces to allow everyone todesign products and services that are interoperable with theirs. The problem is that even though patents do not, strictly speaking, prevent access to protected technologies, they have the potential of doing so, and conflicts of interest are not rare. The primary aim of this dissertation is to increase understanding of the dynamics and controversies of the U.S. and European patent systems, with the focus on the ICT sector. The study consists of three parts. The first part introduces the research topic and the overall results of the dissertation. The second part comprises a publication in which academic, political, legal and business developments that concern software and business-method patents are investigated, and contentiousareas are identified. The third part examines the problems with patents and open standards both of which carry significant economic weight inthe ICT sector. Here, the focus is on so-called submarine patents, i.e. patentsthat remain unnoticed during the standardization process and then emerge after the standard has been set. The factors that contribute to the problems are documented and the practical and juridical options for alleviating them are assessed. In total, the dissertation provides a good overview of the challenges and pressures for change the patent system is facing,and of how these challenges are reflected in standard setting.

Measurement Problems and Problem-Solving in Kraft Pulping

Tämän työn tarkoituksena on koota yhteen selluprosessin mittausongelmat ja mahdolliset mittaustekniikat ongelmien ratkaisemiseksi. Pääpaino on online-mittaustekniikoissa. Työ koostuu kolmesta osasta. Ensimmäinen osa on kirjallisuustyö, jossa esitellään nykyaikaisen selluprosessin perusmittaukset ja säätötarpeet. Mukana on koko kuitulinja puunkäsittelystä valkaisuun ja kemikaalikierto: haihduttamo, soodakattila, kaustistamo ja meesauuni. Toisessa osassa mittausongelmat ja mahdolliset mittaustekniikat on koottu yhteen ”tiekartaksi”. Tiedot on koottu vierailemalla kolmella suomalaisella sellutehtaalla ja haastattelemalla laitetekniikka- ja mittaustekniikka-asiantuntijoita. Prosessikemian paremmalle ymmärtämiselle näyttää haastattelun perusteella olevan tarvetta, minkä vuoksi konsentraatiomittaukset on valittu jatkotutkimuskohteeksi. Viimeisessä osassa esitellään mahdollisia mittaustekniikoita konsentraatiomittausten ratkaisemiseksi. Valitut tekniikat ovat lähi-infrapunatekniikka (NIR), fourier-muunnosinfrapunatekniikka (FTIR), online-kapillaarielektroforeesi (CE) ja laserindusoitu plasmaemissiospektroskopia (LIPS). Kaikkia tekniikoita voi käyttää online-kytkettyinä prosessikehitystyökaluina. Kehityskustannukset on arvioitu säätöön kytketylle online-laitteelle. Kehityskustannukset vaihtelevat nollasta miestyövuodesta FTIR-tekniikalle viiteen miestyövuoteen CE-laitteelle; kehityskustannukset riippuvat tekniikan kehitysasteesta ja valmiusasteesta tietyn ongelman ratkaisuun. Työn viimeisessä osassa arvioidaan myös yhden mittausongelman – pesuhäviömittauksen – ratkaisemisen teknis-taloudellista kannattavuutta. Ligniinipitoisuus kuvaisi nykyisiä mittauksia paremmin todellista pesuhäviötä. Nykyään mitataan joko natrium- tai COD-pesuhäviötä. Ligniinipitoisuutta voidaan mitata UV-absorptiotekniikalla. Myös CE-laitetta voitaisiin käyttää pesuhäviön mittauksessa ainakin prosessikehitysvaiheessa. Taloudellinen tarkastelu pohjautuu moniin yksinkertaistuksiin ja se ei sovellu suoraan investointipäätösten tueksi. Parempi mittaus- ja säätöjärjestelmä voisi vakauttaa pesemön ajoa. Investointi ajoa vakauttavaan järjestelmään on kannattavaa, jos todellinen ajotilanne on tarpeeksi kaukana kustannusminimistä tai jos pesurin ajo heilahtelee eli pesuhäviön keskihajonta on suuri. 50 000 € maksavalle mittaus- ja säätöjärjestelmälle saadaan alle 0,5 vuoden takaisinmaksuaika epävakaassa ajossa, jos COD-pesuhäviön vaihteluväli on 5,2 – 11,6 kg/odt asetusarvon ollessa 8,4 kg/odt. Laimennuskerroin vaihtelee tällöin välillä 1,7 – 3,6 m3/odt asetusarvon ollessa 2,5 m3/odt.

On the Analysis and Control of a Linear Synchronous Servomotor with a Flexible Load

Industry's growing need for higher productivity is placing new demands on mechanisms connected with electrical motors, because these can easily lead to vibration problems due to fast dynamics. Furthermore, the nonlinear effects caused by a motor frequently reduce servo stability, which diminishes the controller's ability to predict and maintain speed. Hence, the flexibility of a mechanism and its control has become an important area of research. The basic approach in control system engineering is to assume that the mechanism connected to a motor is rigid, so that vibrations in the tool mechanism, reel, gripper or any apparatus connected to the motor are not taken into account. This might reduce the ability of the machine system to carry out its assignment and shorten the lifetime of the equipment. Nonetheless, it is usually more important to know how the mechanism, or in other words the load on the motor, behaves. A nonlinear load control method for a permanent magnet linear synchronous motor is developed and implemented in the thesis. The purpose of the controller is to track a flexible load to the desired velocity reference as fast as possible and without awkward oscillations. The control method is based on an adaptive backstepping algorithm with its stability ensured by the Lyapunov stability theorem. As a reference controller for the backstepping method, a hybrid neural controller is introduced in which the linear motor itself is controlled by a conventional PI velocity controller and the vibration of the associated flexible mechanism is suppressed from an outer control loop using a compensation signal from a multilayer perceptron network. To avoid the local minimum problem entailed in neural networks, the initial weights are searched for offline by means of a differential evolution algorithm. The states of a mechanical system for controllers are estimated using the Kalman filter. The theoretical results obtained from the control design are validated with the lumped mass model for a mechanism. Generalization of the mechanism allows the methods derived here to be widely implemented in machine automation. The control algorithms are first designed in a specially introduced nonlinear simulation model and then implemented in the physical linear motor using a DSP (Digital Signal Processor) application. The measurements prove that both controllers are capable of suppressing vibration, but that the backstepping method is superior to others due to its accuracy of response and stability properties.

Lautakuntien toiminnan arviointi Case: Lappeenrannan kaupunki

Pro gradu- tutkielma tehdään Lappeenrannan kaupungin tarkastuslautakunnan toimeksiannosta. Tutkimuksen kohteena on Lappeenrannan kaupungin neljä lautakuntaa. Tutkimuksen tarkoituksena on arvioida näiden lautakuntien toimintaa. Tutkimuksessa selvitetään, tekevätkö lautakunnat sitä työtä mitä niiden tulisi tehdä ja mitä niiden odotetaan tekevän. Varsinainen tutkimusongelma on: kuinka hyvin lautakunnan ja virkamiesjohdon väliset odotukset lautakuntien toiminnasta kohtaavat? Kyseessä on kvalitatiivinen casetutkimus. Haastatteluissa käytetään tutkimusmenetelmänä teemahaastattelua ja lautakuntien jäsenille tehdään kirjallinen kysely puolistrukturoidun kyselyn muodossa. Aineisto analysoidaan teemoittelemalla. Tutkimuksen johtopäätöksenä esitetään, että virkamiesjohdon, lautakuntien puheenjohtajien ja lautakunnan odotukset lautakuntien toimintaa kohtaan eivät aina kohtaa. Lautakunnan puheenjohtaja ja toimialajohtaja voivat olla odotuksissaan hyvin samoilla linjoilla, mutta lautakunnan jäsenet voivatkin odottaa aivan eri asioita.

Harjoitustöiden vertaisarviointi opetusvälineenä

Harjoitustöiden vertaisarvioinnissa opiskelijat tarkastavat toistensa töitä ja antavat niistä palautteen annettujen ohjeiden mukaan. Yleensä opiskelijoille annetaan tätä tehtävää tukemaan tietty joukko arviointikriteereitä, joiden osalta työtä ainakin on kommentoitava. Vertaisarviointi voi antaa opiskelijoille monipuolisempaa palautetta kuin ilman sitä olisi mahdollista, mahdollisuuden tehtävien vaihtoehtoisiin ratkaisuihin tutustumiseen sekä kokemusta ongelmanratkaisun analyyttisestä ja kriittisestä tarkastelusta. Lisäksi vertaisarviointi voi tukea opettajien työtä helpottamalla riittävän palautteen antamista opiskelijoille ja antamalla jonkinlaista kuvaa opiskelijoiden näkemyksistä tehtävän aihealueeseen liittyen. Tämän työn tavoitteena on selvittää, mitä mainituista vertaisarviointiin liitetyistä hyödyistä voidaan todellisuudessa saavuttaa ohjelmointipainotteisilla kursseilla. Ohjelmointikurssin opiskelijat arvioivat kurssiin kuuluvien harjoitustöiden yhteydessä toistensa ratkaisuja yhteen tehtävistä. Opiskelijoille suunnatulla kyselyllä pyritään kartoittamaan, kuinka hyvin vertaisarvioinnille asetetut tavoitteet toteutuvat. Kokemuksia opettajan näkökulmasta selvitetään haastattelujen avulla. Testauksen toteutuksessa käytetään verkkosovellusta, johon opiskelijat tallentavat omat työnsä, josta he lataavat itselleen määrätyt työt arvioitavaksi, johon he tallentavat arvionsa ja jonka kautta he lopulta saavat palautteen omasta työstään.

Våld i parrelationer : en begreppslig undersökning av ett moraliskt och samhälleligt problem

Mäns våld mot kvinnor i parrelationer är ett förekommande problem i det finländska samhället. Som en moralisk fråga råder det ingen tvekan om att våld i parrelationer är orätt. Den moraliska diskussionen kan ändå inte stanna där. När våldsproblematiken studeras närmare träder flera aspekter av moralfilosofiskt intresse fram. Detta är dock sammanlänkat med hela avhandlingens utgångspunkt: att moralfrågor i första hand är frågor i första person. Det handlar om hur var och en av oss som de personer vi är förhåller oss till andra människor i olika situationer. Det handlar om hur varje enskild person berörs av, möter eller står tyst inför t.ex. en problematik som våld i parrelationer. Genom den här utgångspunkten problematiserar avhandlingen en vanlig syn på etik och moral som en uppsättning yttre regler eller som något vi helt objektivt kan resonera kring utan att själva egentligen beröras och bli indragna i det vi diskuterar, eller utan hänsyn till dem som faktiskt berörs. Tyngdpunkten i avhandlingen läggs på en moralisk begreppslig undersökning kring ett antal begrepp som stiger fram som relevanta i mötet med våld i parrelationer. De för avhandlingen centrala begreppen är offentligt-privat, rättvisa, rättigheter, makt, skam, skuld, förlåtelse, omsorg, tillit och ansvar. I avhandlingen har jag beskrivit, kritiskt analyserat samt fördjupat en förståelse av dessa begrepp och uttryck som både rör ett individ- och ett samhällsplan. Hur dessa begrepp och uttryck används och fungerar i olika sammanhang uttrycker moraliska förhållningssätt gentemot våld, offer och förövare. I avhandlingen synliggörs detta och en konkret förankring sker med hjälp av följande material: finländskt lagstiftningsmaterial (förarbeten till lagar som berör våld i parrelationer under perioden 1991-2006) och berättelser av kvinnor som upplevt våld. Den begreppsliga analysen, där bl.a. olika feministiska teoretiker används, visar att språket inte är neutralt. Språket kan vara färgat av flera självklara förutsättningar och distanserande begrepp kan användas på ett sådant sätt att det moraliskt mest centrala och brännande döljs.