Guilherme A. Derenievicz

Este artigo apresenta os resultados de um estudo sobre a logística do PNLD - Programa Nacional do Livro e do Material Didático. O Brasil é um país de dimensões continentais, fazendo com que a distribuição dos livros didáticos às escolas públicas de todas as regiões do país, antes do início das aulas e com o menor custo viável possível, seja um problema crítico e de alta complexidade. A análise apresentada neste artigo mostra o processo de Distribuição do PNLD por uma perspectiva técnica, contemplando uma análise inicial do problema e sua complexidade. Um modelo de programação por restrições é proposto, com o objetivo de formalizar os agentes e as restrições do problema. Os resultados produzidos ajudam a entender o processo e identificar pontos de possível melhoria.

Na Universidade Federal do Paraná (UFPR), desde 2019 oferecemos uma disciplina obrigatória para estudantes ingressantes que foi concebida para promover o desenvolvimento de habilidades que serão necessárias para todo o curso e para a prática profissional ao longo da vida. A disciplina tem o propósito de apresentar o curso escolhido, a Computação e suas diferentes áreas, favorecer o desenvolvimento do Pensamento Computacional, e promover o pensamento crítico. Neste artigo, apresentamos o relato de experiência sobre o uso de uma narrativa distópica conectando todos os conteúdos e atividades da disciplina para: 1. promover o engajamento e o interesse de estudantes na disciplina; 2. apresentar conceitos e tópicos relevantes sobre a área e sobre o curso escolhido; e 3. trabalhar questões não técnicas, como questões éticas e de responsabilidade profissional. Com base em opiniões de 45 discentes, obtidas por meio de um questionário aplicado ao final da disciplina, foi possível identificar que a narrativa atendeu aos seus três propósitos, contribuindo positivamente com o início do curso.

Several hybrid approaches have been proposed to solve numerical constrained optimization problems. In this paper we present an Improved Interval Differential Evolution (I2DE) that uses structural information of the instance during the optimization process. We extend the math operations supported by a multi-interval core implementation that allows pruning infeasible solutions by using local consistency techniques and a backtrack-free local search. Furthermore, we propose a reformulation of interval evolutionary mutation strategies. A comprehensive experimental analysis is conducted over COCONUT and CEC2018 competition benchmarks and indicates that the hybridization between metaheuristics and constraint programming significantly improves the quality of the solutions. The experimental evaluation shows that our black-box version of I2DE outperformed several state-of-the-art solvers.

Differential Evolution (DE) algorithms are a promising strategy to Numerical Constrained Global Optimization Problems (NCOP). Most DE recent variants are applied to black-box optimization problems, where the analytical structure of the NCOP instance is unknown. In this paper we present an Interval Differential Evolution (InDE) algorithm that explores the structural information of the problem. The instance structure is represented by a hypergraph Epiphytic decomposition, where the variables are intervals. InDE algorithm is based on several strategies used in state-of-the-art DE implementations. Based on structural information, our approach extracts a subset of variables of the instance that are critical to the search process. The DE population individuals encode only this subset of variables. The other variables of the instance are valuated by a linear cost constraint propagation over the hypergraph structure. Our experiments show that the use of structural information associated with interval local consistency techniques significantly improves the performance of DE algorithm.

Much effort has been spent to identify classes of CSPs in terms of the relationship between network structure and the amount of consistency that guarantees a backtrack-free solution. In this paper, we address Numerical Constrained global Optimization Problems (NCOPs) encoded as ternary networks, characterizing a class of such problems for which a combination of Generalized Arc-Consistency (GAC) and Relational Arc-Consistency (RAC) is sufficient to ensure a backtrack-free solution, called Epiphytic Trees. While GAC is a domain filtering technique, enforcing RAC creates new constraints in the network. Alternatively, we propose a branch and bound method to achieve a relaxed form of RAC, thus finding an approximation of the solution of NCOPs. We empirically show that Epiphytic Trees are relevant in practice. In addition, we extend this class to cover all ternary NCOPs, for which Strong Directional Relational k-Consistency ensures a backtrack-free solution.