The quadratic assignment problem (QAP) is known to be one of the most computationally difficult combinatorial problems. Optimally solvable instances of the QAP remain of size n ≤ 40 with heuristics used to solve instances in the range 40 ≤ n ≤ 256. In this thesis we develop a local optimization algorithm called GradSwaps (GS). GS uses the first-order Taylor approximation (FOA) to efficiently determine improving swaps in the solution. We use GS to locally optimize instances of the QAP of size 1000 ≤ n ≤ 70000 where the data matrices are given in factored form, enabling efficient computations. We give theoretical background and justification for using the FOA and bound the error inherent in the approximation. A strategy for extending GS to larger scale QAPs using blocks of indices is described in detail. Three novel large-scale applications of the QAP are developed. First, a strategy for data visualization using an extreme learning machine (ELM) where the quality of the visualization is measured in the original data space instead of the projected space. Second, a version of the traveling salesperson problem (TSP) with the squared Euclidean distance metric; this distance metric allows the factorization of the data matrix, a key component for using GS. Third, a method for generating random data with designated distribution and correlation to an accuracy surpassing traditional techniques.

<p>This thesis consists of two papers.</p><p>The first paper is a study of the structure of the k-assignment polytope, whose vertices are the <em>m x n</em> (0; 1)-matrices with exactly <em>k</em> 1:s and at most one 1 in each row and each column. This is a natural generalisation of the Birkhoff polytope and many of the known properties of the Birkhoff polytope are generalised. Two equivalent representations of the faces are given, one as (0; 1)-matrices and one as ear decompositions of bipartite graphs. These tools are used to describe properties of the polytope, especially a complete description of the cover relation in the face lattice of the polytope and an exact expression for the diameter.</p><p>The second paper studies the edge-product space <em>Є(X)</em> for trees on <em>X</em>. This space is generated by the set of edge-weighted finite trees on <em>X</em>, and arises by multiplying the weights of edges on paths in trees. These spaces are closely connected to tree-indexed Markov processes in molecular evolutionary biology. It is known that <em>Є(X)</em> has a natural <em>CW</em>-complex structure, and a combinatorial description of the associated face poset exists which is a poset <em>S(X)</em> of <em>X</em>-forests. In this paper it is shown that the edge-product space is a regular cell complex. One important part in showing that is to conclude that all intervals <em>[Ô, Г], Г </em>Є<em> S(X),</em> have recursive coatom orderings.</p> / Report code: LiU-TEK-LIC-2004:46.

<p>Motiverade och engagerade medarbetare anses idag vara en av de viktigaste faktorerna för att skapa goda resultat inom företag och organisationer. Genom hela historien så har en ledares uppgift varit att inrikta människornas självbevarelsedrift på gemensamma mål, att uttrycka och att försvara en vision som fyller de ledda med hopp. Mediamakarna i Sverige AB, beläget i centrala Stockholm, startades av tre personer vid namn Richard Ehlesjö, Fredrik Sandblad och Sammy Jeridi. Som delägare i företaget arbetar de efter egen modell där öppen kommunikation anses vara extremt betydelsefullt. Med tanke på att de är relativt oerfarna som ledare ställer jag mig frågande till huruvida ledarna har en tillräcklig kompetens och personliga egenskaper för att leda sig själva samt att motivera ett säljteam till framgång.</p><p>Hur motiverar Mediamakarna säljarna till att prestera det yttersta och hur gör man för att få självmotiverade säljare? Anser cheferna att de har de egenskaper som gör dem till bra ledare som nyttjar varje ledares positiva egenskaper på rätt sätt? Dessutom ska jag granska företagets rollfördelning. Syftet med uppsatsen är att förstå vilka metoder cheferna använder för att skapa och framförallt bibehålla hög motivation hos säljpersonalen. För att förstå relationen mellan ledning och säljare är min avsikt också att studera ledarstruktur och roller.</p><p>Jag har intervjuat tre personer. För att intervjuerna skulle bli så bra som möjligt intervjuades den person med mest kunskap och ansvar inom det ämne jag skriver om. Det hermeneutiska förhållningssättet kommer att användas därför att de lämpar sig mer gentemot min forskning. Jag tolkar respondenternas åsikter med hjälp av min förståelse. Jag skall använda mig av en mer kvalitativ metod gentemot kvantitativ eftersom jag kommer att söka förståelse samt meningen med företeelsen av rapportens syfte.</p><p>Efter avslutande studier där jag främst granskat olika motivationsfaktorer hos Mediamakarna anser jag att de har en god struktur men att de bör fokusera på vissa specifika områden som kan skapa eventuella framtida problem. Jag tycker att de har en god syn på motivation där de främst vill bevara inre motivationsintressen kontra yttre sådana. Vad man däremot kan göra är att belöna de säljare som verkligen presterar bra med sådana ”belöningar som främjar den inre företagskulturen” i högre utsträckning så att de i sin tur är trogna gentemot företaget och på sikt kan bli viktiga aktörer när företaget expanderar. När det gäller huvuduppgifterna som en ledare bör ha så tycker jag att Mediamakarna uppfyller kraven. Visionerna och målen som är uppsatta tillsammans med säljarna betyder att den största pressen inte kommer från ledarna utan från säljarna själva. En säljare känner då att han kan utgå från sin egen förmåga och inte hela tiden bli jämförd med andra vilket bidrar till en ökad positiv energi istället för ett ökande tryck på axlarna. Synsättet ökar, enligt mig, förståelsen gentemot varandra och underlättar för ledarna att förmedla en gemensam vision som ska finnas hos respektive säljare.</p><p>Jag tycker att Fredrik och Rickard klarar av att vara ett föredöme utåt. De har, med tanke på sin ringa erfarenhet som ledare, lyckats etablera sig i en hård bransch där det gäller att synas och att skapa kontakter. Det Fredrik dock bör tänka på är att fortsätta med att sätta upp klara riktlinjer vad som är ledare kontra kamrat, vara rättvis och undvika favoriseringar. När det gäller rollfördelningen inom organisation ser jag i nuläget att det inte är några större problem. För att tillsätta en analytiker samt en riktig verkställare så måste Mediamakarna börja att fokusera mer på grupptänkandet. Ledningen har en viktig fråga framför sig, hur man ska bli ”bredare” i sitt urvalsmönster av säljare. De får inte vara rädda för att anställa ”udda” säljare som skiljer sig från den nuvarande säljgruppen. Ju större karaktärsbredd desto lättare är det att hitta den saknade ”pusselbiten” och göra gruppen mer dynamisk.</p> / <p>Motivated and absorbed co-workers is today considered as one of the most important factors in creating good results within companies and organisations. A leaders aim has always been, throughout the whole history, to concentrate human instinct of self-preservation towards common interests, to express and defend a vision which enhance co-workers with believe. Mediamakarna i Sverige AB, founded by Richard Ehlesjö, Fredrik Sandblad and Sammy Jeridi wants to emphasise open communication as something significant within their organisation. Considered their relative inexperienced qualities of leadership, I’m making inquiries about their qualifications and characteristics managing themselves and motivating a sales team to success. How is Mediamakarna motivating salesmen to perform their outmost and how to receive self- motivated members?</p><p>Considering the management, are they of that opinion having sufficient quality of being good leaders and do they use each others skills in a right, positive manner? Furthermore, I will revise the company’s role of structure. The purpose with this article is to understand what kind of methods the management are using to create and above all preserve a high level of motivation among the salesmen. To understand the relationship between management and salesman my purpose is also to study management structure and roles. I have had interviews with three persons. To receive maximum extent, I interviewed the person with the greatest knowledge and responsibility within each field. The hermeneutic approach will be used because it suits my study field. I interpret the respondents opinions with my comprehension. I’m using a more qualitative approach compare to a quantitative one seeing that I will be in search of comprehension and intention of the purpose of the report.</p><p>After completed studies at Mediamakarna, I consider the company having a good structure but also that the management must focus on certain specific fields that may lead to future complex of problems. My opinion is that they have an agreeable view regarding motivation where they foremost want to preserve internal motivation versus external ones. What the company can do is to reward those salesmen that perform on a constant high basis with ”such rewards that encourage the inner culture of company” in a higher extent that they in return are faithful towards the company and in the future can be major assets when the company expands. Regarding the main tasks a manager must have, I think that Mediamakarna fulfils the requirements. The vision and goals that are constructed together means that the great amount of pressure are not from the management but from the salesmen themselves. One salesman might then feel that he can emanate from his own capacity and not be judged on a constant basis which create a positive energy instead of a increasing pressure on the shoulders. In my point of view it increases the understanding towards each other and make it easier for the management to supply a common vision that must be found in each salesperson.</p><p>I’m finding Fredrik and Rickard being good examples of external acting. They have, in regard to their slight experience, manage to establish themselves in a tough line of business where you have to be visible and create contacts. Fredrik must however continue to follow his guiding principles – manager versus friend, to be impartial and avoid favouritism. Concerning the role division within the organisation I can’t in this moment see any major problems. To appoint an analysts and a performer, Mediamakarna must focused and intensify more on how to create dynamic groups. The management has an important task how to become more wider in the recruiting of salesperson. They can’t be afraid of appointing ”odd” salesmen that are separate from the current sales group. The more traits of character in a group the easier it might be to find the missing piece of a puzzle and accordingly make the group more dynamic.</p>

The Weapon Target Assignment (WTA) problem is a fundamental problem arising in defense-related applications of operations research. This problem consists of optimally assigning n weapons to m targets so that the total expected survival value of the targets after all the engagements is minimum. The WTA problem can be formulated as a nonlinear integer programming problem and is known to be NP-complete. There do not exist any exact methods for the WTA problem which can solve even small size problems (for example, with 20 weapons and 20 targets). Though several heuristic methods have been proposed to solve the WTA problem, due to the absence of exact methods, no estimates are available on the quality of solutions produced by such heuristics. In this paper, we suggest linear programming, integer programming, and network flow based lower bounding methods using which we obtain several branch and bound algorithms for the WTA problem. We also propose a network flow based construction heuristic and a very large-scale neighborhood (VLSN) search algorithm. We present computational results of our algorithms which indicate that we can solve moderately large size instances (up to 80 weapons and 80 targets) of the WTA problem optimally and obtain almost optimal solutions of fairly large instances (up to 200 weapons and 200 targets) within a few seconds

In large controller-datapath systems, the switching activity of datapath is administered by controller. The unnecessary switching activity will cause more power consumption, and therefore the design of controllers (i.e. Finite State Machines, FSMs) will influence the whole power consumption of the systems. The state assignment and output encoding are the two major factors influencing the power of system under the hardware implementation of controllers. In this paper, we present an integer linear programming (ILP) method to solve the state assignment and output encoding problems. The purpose is to reduce switching activity such that the goal of power optimization can be achieved. It has not to reschedule the operations of datapath under timing and resource constraints and has no extra area overhead. In order to verify the effectiveness of our proposed ILP approach, we use this approach to implement several controller-datapath systems. Experimental results show that our proposed approach achieves an average of 30.513% power savings compared to the traditional area optimal synthesis tool, SIS, where power is not considered. Our proposed approach does not cause extra area overhead while achieving a significant power saving of systems.

Motiverade och engagerade medarbetare anses idag vara en av de viktigaste faktorerna för att skapa goda resultat inom företag och organisationer. Genom hela historien så har en ledares uppgift varit att inrikta människornas självbevarelsedrift på gemensamma mål, att uttrycka och att försvara en vision som fyller de ledda med hopp. Mediamakarna i Sverige AB, beläget i centrala Stockholm, startades av tre personer vid namn Richard Ehlesjö, Fredrik Sandblad och Sammy Jeridi. Som delägare i företaget arbetar de efter egen modell där öppen kommunikation anses vara extremt betydelsefullt. Med tanke på att de är relativt oerfarna som ledare ställer jag mig frågande till huruvida ledarna har en tillräcklig kompetens och personliga egenskaper för att leda sig själva samt att motivera ett säljteam till framgång. Hur motiverar Mediamakarna säljarna till att prestera det yttersta och hur gör man för att få självmotiverade säljare? Anser cheferna att de har de egenskaper som gör dem till bra ledare som nyttjar varje ledares positiva egenskaper på rätt sätt? Dessutom ska jag granska företagets rollfördelning. Syftet med uppsatsen är att förstå vilka metoder cheferna använder för att skapa och framförallt bibehålla hög motivation hos säljpersonalen. För att förstå relationen mellan ledning och säljare är min avsikt också att studera ledarstruktur och roller. Jag har intervjuat tre personer. För att intervjuerna skulle bli så bra som möjligt intervjuades den person med mest kunskap och ansvar inom det ämne jag skriver om. Det hermeneutiska förhållningssättet kommer att användas därför att de lämpar sig mer gentemot min forskning. Jag tolkar respondenternas åsikter med hjälp av min förståelse. Jag skall använda mig av en mer kvalitativ metod gentemot kvantitativ eftersom jag kommer att söka förståelse samt meningen med företeelsen av rapportens syfte. Efter avslutande studier där jag främst granskat olika motivationsfaktorer hos Mediamakarna anser jag att de har en god struktur men att de bör fokusera på vissa specifika områden som kan skapa eventuella framtida problem. Jag tycker att de har en god syn på motivation där de främst vill bevara inre motivationsintressen kontra yttre sådana. Vad man däremot kan göra är att belöna de säljare som verkligen presterar bra med sådana ”belöningar som främjar den inre företagskulturen” i högre utsträckning så att de i sin tur är trogna gentemot företaget och på sikt kan bli viktiga aktörer när företaget expanderar. När det gäller huvuduppgifterna som en ledare bör ha så tycker jag att Mediamakarna uppfyller kraven. Visionerna och målen som är uppsatta tillsammans med säljarna betyder att den största pressen inte kommer från ledarna utan från säljarna själva. En säljare känner då att han kan utgå från sin egen förmåga och inte hela tiden bli jämförd med andra vilket bidrar till en ökad positiv energi istället för ett ökande tryck på axlarna. Synsättet ökar, enligt mig, förståelsen gentemot varandra och underlättar för ledarna att förmedla en gemensam vision som ska finnas hos respektive säljare. Jag tycker att Fredrik och Rickard klarar av att vara ett föredöme utåt. De har, med tanke på sin ringa erfarenhet som ledare, lyckats etablera sig i en hård bransch där det gäller att synas och att skapa kontakter. Det Fredrik dock bör tänka på är att fortsätta med att sätta upp klara riktlinjer vad som är ledare kontra kamrat, vara rättvis och undvika favoriseringar. När det gäller rollfördelningen inom organisation ser jag i nuläget att det inte är några större problem. För att tillsätta en analytiker samt en riktig verkställare så måste Mediamakarna börja att fokusera mer på grupptänkandet. Ledningen har en viktig fråga framför sig, hur man ska bli ”bredare” i sitt urvalsmönster av säljare. De får inte vara rädda för att anställa ”udda” säljare som skiljer sig från den nuvarande säljgruppen. Ju större karaktärsbredd desto lättare är det att hitta den saknade ”pusselbiten” och göra gruppen mer dynamisk. / Motivated and absorbed co-workers is today considered as one of the most important factors in creating good results within companies and organisations. A leaders aim has always been, throughout the whole history, to concentrate human instinct of self-preservation towards common interests, to express and defend a vision which enhance co-workers with believe. Mediamakarna i Sverige AB, founded by Richard Ehlesjö, Fredrik Sandblad and Sammy Jeridi wants to emphasise open communication as something significant within their organisation. Considered their relative inexperienced qualities of leadership, I’m making inquiries about their qualifications and characteristics managing themselves and motivating a sales team to success. How is Mediamakarna motivating salesmen to perform their outmost and how to receive self- motivated members? Considering the management, are they of that opinion having sufficient quality of being good leaders and do they use each others skills in a right, positive manner? Furthermore, I will revise the company’s role of structure. The purpose with this article is to understand what kind of methods the management are using to create and above all preserve a high level of motivation among the salesmen. To understand the relationship between management and salesman my purpose is also to study management structure and roles. I have had interviews with three persons. To receive maximum extent, I interviewed the person with the greatest knowledge and responsibility within each field. The hermeneutic approach will be used because it suits my study field. I interpret the respondents opinions with my comprehension. I’m using a more qualitative approach compare to a quantitative one seeing that I will be in search of comprehension and intention of the purpose of the report. After completed studies at Mediamakarna, I consider the company having a good structure but also that the management must focus on certain specific fields that may lead to future complex of problems. My opinion is that they have an agreeable view regarding motivation where they foremost want to preserve internal motivation versus external ones. What the company can do is to reward those salesmen that perform on a constant high basis with ”such rewards that encourage the inner culture of company” in a higher extent that they in return are faithful towards the company and in the future can be major assets when the company expands. Regarding the main tasks a manager must have, I think that Mediamakarna fulfils the requirements. The vision and goals that are constructed together means that the great amount of pressure are not from the management but from the salesmen themselves. One salesman might then feel that he can emanate from his own capacity and not be judged on a constant basis which create a positive energy instead of a increasing pressure on the shoulders. In my point of view it increases the understanding towards each other and make it easier for the management to supply a common vision that must be found in each salesperson. I’m finding Fredrik and Rickard being good examples of external acting. They have, in regard to their slight experience, manage to establish themselves in a tough line of business where you have to be visible and create contacts. Fredrik must however continue to follow his guiding principles – manager versus friend, to be impartial and avoid favouritism. Concerning the role division within the organisation I can’t in this moment see any major problems. To appoint an analysts and a performer, Mediamakarna must focused and intensify more on how to create dynamic groups. The management has an important task how to become more wider in the recruiting of salesperson. They can’t be afraid of appointing ”odd” salesmen that are separate from the current sales group. The more traits of character in a group the easier it might be to find the missing piece of a puzzle and accordingly make the group more dynamic.

We present versions of the Frank-Wolfe method for linearly constrained convex programs, in which consecutive search directions are made conjugate. Preliminary computational studies in a MATLAB environment applying pure Frank-Wolfe, Conjugate direction Frank-Wolfe (CFW), Bi-conjugate Frank-Wolfe (BFW) and ”PARTANized” Frank-Wolfe methods to some classical Traffic Assignment Problems show that CFW and BFW compare favorably to the other methods. This spurred a more detailed study, comparing our methods to Bar-Gera’s origin-based algorithm. This study indicates that our methods are competitive for accuracy requirements suggested by Boyce et al. We further show that CFW is globally convergent. We moreover point at independent studies by other researchers that show that our methods compare favourably with recent bush-based and gradient projection algorithms on computers with several cores. / <p>Updated from "E-publ" to published. QC 20130625</p>

This thesis is concerned with the channel assignment (CA) problem in multi-channel multi-interface wireless mesh networks (M2WNs). First, for M2WNs with general topologies, we rigorously demonstrate using the combinatorial principle of inclusion/exclusion that the CA solution space can be quantified, indicating that its cardinality is greatly influenced by the number of radio interfaces installed on each router. Based on this analysis, a novel scheme is developed to construct a new reduced search space, represented by a lattice structure, that is searched more efficiently for a CA solution. The elements in the reduced lattice-based space, labeled Solution Structures (SS), represent groupings of feasible CA solutions satisfying the radio constraints at each node. Two algorithms are presented for searching the lattice structure. The first is a greedy algorithm that finds a good SS in polynomial time, while the second provides a user-controlled depthfirst search for the optimal SS. The obtained SS is used to construct an unconstrained weighted graph coloring problem which is then solved to satisfy the soft interference constraints. For the special class of full M2WNs (fM2WNs), we show that an optimal CA solution can only be achieved with a certain number of channels; we denote this number as the characteristic channel number and derive upper and lower bounds for that number as a function of the number of radios per router. Furthermore, exact values for the required channels for minimum interference are obtained when certain relations between the number of routers and the radio interfaces in a given fM2WN are satisfied. These bounds are then employed to develop closed-form expressions for the minimum channel interference that achieves the maximum throughput for uniform traffic on all communication links. Accordingly, a polynomial-time algorithm to find a near-optimal solution for the channel assignment problem in fM2WN is developed. Experimental results confirm the obtained theoretical results and demonstrate the performance of the proposed schemes.

The agent-based micro-simulation modelling technique for transportation planning is rapidly developing and is being applied to practice in recent years. In contrast to conventional four-step modelling with static assignment theory, this emerging technique employs a dynamic assignment principle. Based on summary of various types of traffic assignment models and algorithms, the thesis elucidates in detail the theories of two models, MATSim and EMME/2, which represent two genres of traffic assignment, i.e., dynamic stochastic stationary state assignment and static deterministic user equilibrium assignment. In the study, the two models are compared and validated to reflect both spatial and temporal variation of the traffic flow pattern. The comparison results indicate that numerical outputs produced by MATSim are not only compatible to those by EMME/2 but more realistic from a temporal point of view. Therefore, agent-based micro-simulation models reflect a promising direction of next generation of transportation planning models.

This thesis proposes a potential solution for future ubiquitous broadband wireless access networks, called a cellular wireless mesh network (CMESH), and investigates a number of its performance issues. A CMESH is organized in multi-radio, multi-channel, multi-rate and multi-hop radio cells. It can operate on abundant high radio frequencies, such as 5-50 GHz, and thus may satisfy the bandwidth requirements of future ubiquitous wireless applications.<p> Each CMESH cell has a single Internet-connected gateway and serves up to hundreds of mesh nodes within its coverage area. This thesis studies performance issues in a CMESH, focusing on cell capacity, expressed in terms of the max-min throughput. In addition to introducing the concept of a CMESH, this thesis makes the following contributions.<p> The first contribution is a new method for analyzing theoretical cell capacity. This new method is based on a new concept called Channel Transport Capacity (CTC), and derives new analytic expressions for capacity bounds for carrier-sense-based CMESH cells.<p> The second contribution is a new algorithm called the Maximum Channel Collision Time (MCCT) algorithm and an expression for the nominal capacity of CMESH cells. This thesis proves that the nominal cell capacity is achievable and is the exact cell capacity for small cells within the abstract models.<p> Finally, based on the MCCT algorithm, this thesis proposes a series of greedy algorithms for channel assignment and routing in CMESH cells. Simulation results show that these greedy algorithms can significantly improve the capacity of CMESH cells, compared with algorithms proposed by other researchers.