An integer programming framework for sequencing cutting patterns based on interval graph completion

We derived a framework in integer programming, based on the properties of a linear ordering of the vertices in interval graphs, that acts as an edge completion model for obtaining interval graphs. This model can be applied to problems of sequencing cutting patterns, namely the minimization of open stacks problem (MOSP). By making small modifications in the objective function and using only some of the inequalities, the MOSP model is applied to another pattern sequencing problem that aims to minimize, not only the number of stacks, but also the order spread (the minimization of the stack occupation problem), and the model is tested.

An integer programming model for the minimum interval graph completion problem

The minimum interval graph completion problem consists of, given a graph G = ( V, E ), finding a supergraph H = ( V, E ∪ F ) that is an interval graph, while adding the least number of edges |F| . We present an integer programming formulation for solving the minimum interval graph completion problem recurring to a characteri- zation of interval graphs that produces a linear ordering of the maximal cliques of the solution graph.

Minimization of open orders using interval graphs

In this paper we address an order processing optimization problem known as the Minimization of Open Stacks Problem (MOSP). This problem consists in finding the best sequence for manufacturing the different products required by costumers, in a setting where only one product can be made at a time. The objective is to minimize the maximum number of incomplete orders from costumers that are being processed simultaneously. We present an integer programming model, based on the existence of a perfect elimination order in interval graphs, which finds an optimal sequence for the costumers orders. Among other economic advantages, manufacturing the products in this optimal sequence reduces the amount of space needed to store incomplete orders.

Sequencing cutting patterns with colored interval graphs

The problem addressed here originates in the industry of flat glass cutting and wood panel sawing, where smaller items are cut from larger items accordingly to predefined cutting patterns. In this type of industry the smaller pieces that are cut from the patterns are piled around the machine in stacks according to the size of the pieces, which are moved to the warehouse only when all items of the same size have been cut. If the cutting machine can process only one pattern at a time, and the workspace is limited, it is desirable to set the sequence in which the cutting patterns are processed in a way to minimize the maximum number of open stacks around the machine. This problem is known in literature as the minimization of open stacks (MOSP). To find the best sequence of the cutting patterns, we propose an integer programming model, based on interval graphs, that searches for an appropriate edge completion of the given graph of the problem, while defining a suitable coloring of its vertices.

Using interval graphs in an order processing optimization problem

In this paper we address an order processing optimization problem known as minimization of open stacks (MOSP). We present an integer pro gramming model, based on the existence of a perfect elimination scheme in interval graphs, which finds an optimal sequence for the costumers orders.

Adaptive Learning in Games: Defining Profiles of Competitor Players

Artificial Intelligence has been applied to dynamic games for many years. The ultimate goal is creating responses in virtual entities that display human-like reasoning in the definition of their behaviors. However, virtual entities that can be mistaken for real persons are yet very far from being fully achieved. This paper presents an adaptive learning based methodology for the definition of players’ profiles, with the purpose of supporting decisions of virtual entities. The proposed methodology is based on reinforcement learning algorithms, which are responsible for choosing, along the time, with the gathering of experience, the most appropriate from a set of different learning approaches. These learning approaches have very distinct natures, from mathematical to artificial intelligence and data analysis methodologies, so that the methodology is prepared for very distinct situations. This way it is equipped with a variety of tools that individually can be useful for each encountered situation. The proposed methodology is tested firstly on two simpler computer versus human player games: the rock-paper-scissors game, and a penalty-shootout simulation. Finally, the methodology is applied to the definition of action profiles of electricity market players; players that compete in a dynamic game-wise environment, in which the main goal is the achievement of the highest possible profits in the market.

Every normal logic program has a 2-valued semantics: theory, extensions, applications, implementations

Trabalho apresentado no âmbito do Doutoramento em Informática, como requisito parcial para obtenção do grau de Doutor em Informática

Social Media Integration in Video Games: A Social Overlay for Desktop Games

Simpósio de Informática (INForum 2015), Covilhã, Portugal. Notes: Best paper award nominee.

Sistema de Recomendação: Share GFS Games, Films & Series

Esta dissertação incide sobre o estudo e análise de uma solução para a criação de um sistema de recomendação para uma comunidade de consumidores de media e no consequente desenvolvimento da mesma cujo âmbito inicial engloba consumidores de jogos, filmes e/ou séries, com o intuito de lhes proporcionar a oportunidade de partilharem experiências, bem como manterem um registo das mesmas. Com a informação adquirida, o sistema reúne condições para proceder a sugestões direccionadas a cada membro da comunidade. O sistema actualiza a sua informação mediante as acções e os dados fornecidos pelos membros, bem como pelo seu feedback às sugestões. Esta aprendizagem ao longo do tempo permite que as sugestões do sistema evoluam juntamente com a mudança de preferência dos membros ou se autocorrijam. O sistema toma iniciativa de sugerir mediante determinadas acções, mas também pode ser invocada uma sugestão directamente pelo utilizador, na medida em que este não precisa de esperar por sugestões, podendo pedir ao sistema que as forneça num determinado momento. Nos testes realizados foi possível apurar que o sistema de recomendação desenvolvido forneceu sugestões adequadas a cada utilizador específico, tomando em linha de conta as suas acções prévias. Para além deste facto, o sistema não forneceu qualquer sugestão quando o histórico destas tinha provado incomodar o utilizador.

Social Media Integration in Video Games GameNshare: A Social Overlay for Desktop Games

The ever increasing popularity of social media makes it a promising source for the personalization of gameplay experiences. Furthermore, involving social network friends in a game can greatly enrich the satisfaction of the player and also attract potential novel players to a game. This master thesis describes a social overlay designed for desktop games, called GameNshare. It allows players to easily capture and share with multiple social networks game-related screenshots, videos and stories. Additionally, it also provides asynchronous multiplayer game mechanics to directly integrate social network friends in the game. GameNshare was designed to interact with the users in a non-intrusive way allowing them to be in complete control of what is shared. It prevents unsolicited sharing of messages, a key problem in social media integration tools, by the use of built-in message monitoring and anti-spam measures. GameNshare was specially designed for players aged from 18 to 25 years that are regular users of Twitter and Facebook. It was tested by a group of 10 individuals from the target age range that were surveyed to capture their insights on the use of the social overlay. The implemented GameNshare features were well accepted by the testers that were also useful in highlighting features for future development. GameNshare ultimate goal is to make players look and ask for social integration and allow them to take full advantage of their social communities to improve gaming experiences.

A framework for developing motion-based games

Dissertação para obtenção do Grau de Mestre em Engenharia Informática

An existence result for discontinuous games

We introduce a notion of upper semicontinuity, weak upper semicontinuity, and show that it, together with a weak form of payoff security, is enough to guarantee the existence of Nash equilibria in compact, quasiconcave normal form games. We show that our result generalizes the pure strategy existence theorem of Dasgupta and Maskin (1986) and that it is neither implied nor does it imply the existence theorems of Baye, Tian, and Zhou (1993) and Reny (1999). Furthermore, we show that an equilibrium may fail to exist when, while maintaining weak payoff security, weak upper semicontinuity is weakened to reciprocal upper semicontinuity.

On the existence of pure-strategy equilibria in large games

Over the years, several formalizations and existence results for games with a continuum of players have been given. These include those of Schmeidler (1973), Rashid (1983), Mas-Colell (1984), Khan and Sun (1999) and Podczeck (2007a). The level of generality of each of these existence results is typically regarded as a criterion to evaluate how appropriate is the corresponding formalization of large games. In contrast, we argue that such evaluation is pointless. In fact, we show that, in a precise sense, all the above existence results are equivalent. Thus, all of them are equally strong and therefore cannot rank the different formalizations of large games.

Collusion and reciprocity in infinitely repeated games

This paper extends the standard industrial organization models of repeated interaction between firms by incorporating preferences for reciprocity. A reciprocal firm responds to unkind behavior of rivals with unkind actions (destructive reciprocity), while at the same time, it responds to kind behavior of rivals with kind actions (constructive reciprocity). The main finding of the paper is that, for plausible perceptions of fairness, preferences for reciprocity facilitate collusion in infinitely repeated market games, that is, the critical discount rate at wish collusion can be sustained tends to be lower when firms have preferences for reciprocity than when firms are selfish. The paper also finds that the best collusive outcome that can be sustained in the infinitely repeated Cournot game with reciprocal firms is worse for consumers than the best collusive outcome that can be sustained in the infinitely repeated Cournot game with selfish firms.

Narrative Memory in Hyperfiction and Games

The aim of this paper is to address some theoretical issues concerning the narrative practice in cyberspace. From a narratological perspective it intends to clarify the functioning of time and space in storytelling. For that purpose it traces the concept(s) of memory inherited from rhetoric; the use of memory as a narrative device in traditional accounts; the adaptations imposed by hyperfiction. Using practical examples (including two Portuguese case studies - InStory 2006, and Noon 2007) it will show how narrative memory strategies can be helpful in game literacy. The main purpose is to contribute to serious game research and (trans)literary studies.