No description available.

No description available.

Solving real world problems with mixed integer programming (MIP) involves efforts in modeling and efficient algorithms. To solve a minimization MIP problem, a lower bound is needed in a branch-and-bound algorithm to evaluate the quality of a feasible solution and to improve the efficiency of the algorithm. This thesis develops a new MIP model and studies algorithms for obtaining lower bounds for MIP. The first part of the thesis is dedicated to a new production planning model with pricing decisions. To increase profit, a company can use pricing to influence its demand to increase revenue, decrease cost, or both. We present a model that uses pricing discounts to increase production and delivery flexibility, which helps to decrease costs. Although the revenue can be hurt by introducing pricing discounts, the total profit can be increased by properly choosing the discounts and production and delivery decisions. We further explore the idea with variations of the model and present the advantages of using flexibility to increase profit. The second part of the thesis focuses on solving integer programming(IP) problems by improving lower bounds. Specifically, we consider obtaining lower bounds for the multi- dimensional knapsack problem (MKP). Because MKP lacks special structures, it allows us to consider general methods for obtaining lower bounds for IP, which includes various relaxation algorithms. A problem relaxation is achieved by either enlarging the feasible region, or decreasing the value of the objective function on the feasible region. In addition, dual algorithms can also be used to obtain lower bounds, which work directly on solving the dual problems. We first present some characteristics of the value function of MKP and extend some properties from the knapsack problem to MKP. The properties of MKP allow some large scale problems to be reduced to smaller ones. In addition, the quality of corner relaxation bounds of MKP is considered. We explore conditions under which the corner relaxation is tight for MKP, such that relaxing some of the constraints does not affect the quality of the lower bounds. To evaluate the overall tightness of the corner relaxation, we also show the worst-case gap of the corner relaxation for MKP. To identify parameters that contribute the most to the hardness of MKP and further evaluate the quality of lower bounds obtained from various algorithms, we analyze the characteristics that impact the hardness of MKP with a series of computational tests and establish a testbed of instances for computational experiments in the thesis. Next, we examine the lower bounds obtained from various relaxation algorithms com- putationally. We study methods of choosing constraints for relaxations that produce high- quality lower bounds. We use information obtained from linear relaxations to choose con- straints to relax. However, for many hard instances, choosing the right constraints can be challenging, due to the inaccuracy of the LP information. We thus develop a dual heuristic algorithm that explores various constraints to be used in relaxations in the Branch-and- Bound algorithm. The algorithm uses lower bounds obtained from surrogate relaxations to improve the LP bounds, where the relaxed constraints may vary for different nodes. We also examine adaptively controlling the parameters of the algorithm to improve the performance. Finally, the thesis presents two problem-specific algorithms to obtain lower bounds for MKP: A subadditive lifting method is developed to construct subadditive dual solutions, which always provide valid lower bounds. In addition, since MKP can be reformulated as a shortest path problem, we present a shortest path algorithm that uses estimated distances by solving relaxations problems. The recursive structure of the graph is used to accelerate the algorithm. Computational results of the shortest path algorithm are given on the testbed instances.

Thesis (M. Tech.) - Information and Communication Technology, Faculty of Applied and Computer Sciences - Vaal University of Technology / Research has found that learners find it difficult to solve programming problems in a logical way, therefore the failure rate in Programming I is high. The Entry-level Certificate in Information Technology was introduced as an intervention to address this problem. Four aspects were focused on in the Entry-level Certificate in Information Technology, namely English comprehension, academic competency, numerical skills and the problem-solving skills of learners. Basic computer literacy was the common theme used throughout the Information Technology Boot Camp (ITBC) to address the above-mentioned aspects, in order to broaden access to the Vaal University of Technology (VUT). The research indicates that English comprehension is a very important component of the Information and Communication Technology (ICT) modules, and that it is important for learners to have an English proficiency level of grade 12 before enroUing for a diploma in I CT. The ICT and numerical skills modules also narrowed the gap between secondary and tertiary education, by equipping the learners with prior knoWJledge that is crucial for being successful in the ICT diploma. To conclude access was broadened to the VUT and the intervention of the ITBC did impact positively on the cognitive functioning of learners.

This work deals with building a program system for solving dynamic programming problems on a computer. The theoretical part describes dynamic programming as a tool used for optimizing multistage decision processes and dynamic programming problems implemented in the program system. The practical part describes the design and implementation of the program system and verification of its functionality.

A presente pesquisa aborda um problema de roteirização e programação de veículos incorporando uma nova restrição operacional: a requisição simultânea de múltiplos veículos para atendimento da demanda. Trata-se de uma característica encontrada em operações de apoio à exploração de petróleo \"offshore\", em que mais de uma embarcação é requerida para executar tarefas de reboque e lançamento de linhas de ancoragem. Esta imposição, somada às restrições de janela de tempo, precedência entre tarefas, autonomia das embarcações e atendimento integral da demanda, configuram este problema. A programação é orientada pela minimização dos custos variáveis da operação e dos custos associados ao nível de serviço no atendimento. Este problema é uma variação do problema clássico de roteirização e programação de veículos com janela de tempo, de classe NP-Difícil. Nesta pesquisa, propõe-se modelar e resolver o problema em escala real por meio do algoritmo \"branch and cut\" acoplado às heurísticas de busca em vizinhança \"local branching\" e \"variable neighborhood search\". Para gerar as soluções iniciais será empregado o método \"feasibility pump\" e uma heurística construtiva. / This research focuses a fleet scheduling problem with new operational constraints: each task requiring multiple types of vehicles simultaneously. This kind of operation occurs in offshore exploitation and production sites, when more than one vessel is needed to accomplish the tugging and mooring of oil platforms. Other constraints are maintained such as time windows, precedence between tasks, route duration and the demand attendance. The solution schedules are cost oriented, which encompasses the routing variable costs and the customer service costs. This is a variation of the classical fleet routing and scheduling, which is an NP-Hard problem. This research aims to solve the real scale problem through a combined use of branch and cut strategy with local search algorithms such as local branching and variable neighborhood search. An efficient heuristic rule will be used in order to generate initial solutions using the feasibility pump method.

This thesis focuses on the challenges that arise from the scheduling of heat exchanger network maintenance problems which undergo fouling and run continuously over time. The original contributions of the current research consist of the development of novel optimisation methodologies for the scheduling of cleaning actions in heat exchanger network problems, the application of the novel solution methodology developed to other general maintenance scheduling problems, the development of a stochastic programming formulation using this optimisation technique and its application to these scheduling problems with parametric uncertainty. The work presented in this thesis can be divided into three areas. To efficiently solve this non-convex heat exchanger network maintenance scheduling problem, new optimisation strategies are developed. The resulting contributions are outlined below. In the first area, a novel methodology is developed for the solution of the heat exchanger network maintenance scheduling problems, which is attributed towards a key discovery in which it is observed that these problems exhibit bang-bang behaviour. This indicates that when integrality on the binary decision variables is relaxed, the solution will tend to either the lower or the upper bound specified, obviating the need for integer programming solution techniques. Therefore, these problems are in ac- tuality optimal control problems. To suitably solve these problems, a feasible path sequential mixed integer optimal control approach is proposed. This methodology is coupled with a simple heuristic approach and applied to a range of heat exchanger network case studies from crude oil refinery preheat trains. The demonstrated meth- odology is shown to be robust, reliable and efficient. In the second area of this thesis, the aforementioned novel technique is applied to the scheduling of the regeneration of membranes in reverse osmosis networks which undergo fouling and are located in desalination plants. The results show that the developed solution methodology can be generalised to other maintenance scheduling problems with decaying performance characteristics. In the third and final area of this thesis, a stochastic programming version of the feasible path mixed integer optimal control problem technique is established. This is based upon a multiple scenario approach and is applied to two heat exchanger network case studies of varying size and complexity. Results show that this methodology runs automatically with ease without any failures in convergence. More importantly due to the significant impact on economics, it is vital that uncertainty in data is taken into account in the heat exchanger network maintenance scheduling problem, as well as other general maintenance scheduling problems when there is a level of uncertainty in parameter values.

A oferta de cursos de Licenciatura em Computação vem sendo ampliada no Brasil. Esse curso pertencente a uma área de conhecimento recente: a Computação, agregando outras áreas como a Educação. Ele encerra dificuldades que exigem discussão acadêmica e social. Uma das dificuldades é a produção de material didático para ensino de Computação; esse material é desenvolvido pelos estudantes, mas, geralmente, sem base teórica adequada. Para contribuir com a superação dessa lacuna a pesquisa objetiva analisar a influência do estudo de Epistemologia Genética e Neurociência Cognitiva na produção didática de estudantes de Licenciatura em Computação, através da elaboração de problemas ou desafios de Linguagem de Programação, para o ensino de Computação no Ensino Fundamental. As atividades foram realizadas na disciplina Práticas Articuladoras em Computação IV do curso de Licenciatura em Computação, da Universidade de Santa Cruz do Sul – UNISC, com a participação de onze estudantes. As linguagens de programação exploradas para a produção do material didático foram FMSLogo, Scratch e Robokit. O levantamento dos dados contou com quatro etapas que compreenderam a produção didática dos estudantes através do desenvolvimento de problemas ou desafios de programação, o estudo das referidas teorias, em especial as categorias “Aprendizagem”, “Emoções e Sentimentos”, “Estímulo Emocional Competente”, “Abstração Reflexionante” e “Self”, a reelaboração da produção didática com base no estudo realizado e a análise dessa produção Os dados junto aos estudantes matriculados na disciplina foram coletados através de entrevista oral e de questionário online. A análise do material didático, desenvolvido pelos estudantes, verifica a presença textual dos três primeiros elementos de referência da prática computacional estabelecidos pelo Instituto de Tecnologia de Massachusetts – MIT: 1. Ação interativa-incremental, 2. Teste-depuração, 3.Reutilização-reformulação e 4.Abstração-modulação. A análise dos processos de abstração pseudoempírica e reflexionante permitiram entender que os resultados apontam a influência do estudo de Epistemologia Genética e Neurociência Cognitiva na produção didática dos estudantes de Licenciatura em Computação. Os problemas de programação reelaborados por nove estudantes apresentam modificações intermediárias ou muitas modificações. Conclui-se que a produção de material didático para o ensino de Computação no Ensino Fundamental pode assumir um caráter desafiador, através de descrição textual que privilegia a ação de quem resolve problemas de programação. / The offer of graduation programs in Computer Science for Teaching has been expended in Brazil. This graduation program belongs to a recent area of knowledge: Computing, adding other areas such as Education. It entails difficulties that require academic and social discussion. One of the difficulties is the production of didactic material for Computing Teaching; this material is developed by the students, but generally without adequate theoretical basis. In order to contribute to overcoming this gap, the objective research decided to analyze the influence of the study Genetic Epistemology and Cognitive Neuroscience in the didactic production of undergraduate students in Computer Science for Teaching, through the elaboration of problems or challenges of Programming Language, for the Computing Teaching in Elementary School. The Method relied on activities carried out in the subject Articulating Practices in Computing IV of the in Computer Science for Teaching course of the University of Santa Cruz do Sul – UNISC, with the participation of eleven students. The programming languages explored for the production of didactic material were FMSLogo, Scratch and ROBOKIT. The data collection had four stages that comprised the didactic production of the students through the development of problems or programming challenges, the study of these theories, in particular the categories “learning”, “emotions and feelings”, “competent emotional stimulus”, “reflective abstraction” and “self” the re-elaboration of didactic production based on the realized study and the analysis of this production The collected data from the enrolled students in the subject were collected through an interview based on the Jean Piaget Clinical Method and an online questionnaire. The analysis of the didactic material, developed by the students, verifies the textual presence of the first three elements of computational practice established by the Massachusetts Institute of Technology - MIT: 1. Interactive-incremental action, 2. Test-Depuration, 3. Reuse-reformulation and 4. Abstraction-modulation. The analysis of the processes of pseudoempirical and reflective abstraction processes allowed to understand that the results point to the influence of Genetic Epistemology and Cognitive Neuroscience study in the didactic production of Computer Science for Teaching students. Programming problems reworked by nine students present intermediate modifications or many modifications. It is concluded that the production of didactic material for the Computing teaching in the elementary school can assume a challenging character, through a textual description that privileges the action of those who solve programming problems.

A oferta de cursos de Licenciatura em Computação vem sendo ampliada no Brasil. Esse curso pertencente a uma área de conhecimento recente: a Computação, agregando outras áreas como a Educação. Ele encerra dificuldades que exigem discussão acadêmica e social. Uma das dificuldades é a produção de material didático para ensino de Computação; esse material é desenvolvido pelos estudantes, mas, geralmente, sem base teórica adequada. Para contribuir com a superação dessa lacuna a pesquisa objetiva analisar a influência do estudo de Epistemologia Genética e Neurociência Cognitiva na produção didática de estudantes de Licenciatura em Computação, através da elaboração de problemas ou desafios de Linguagem de Programação, para o ensino de Computação no Ensino Fundamental. As atividades foram realizadas na disciplina Práticas Articuladoras em Computação IV do curso de Licenciatura em Computação, da Universidade de Santa Cruz do Sul – UNISC, com a participação de onze estudantes. As linguagens de programação exploradas para a produção do material didático foram FMSLogo, Scratch e Robokit. O levantamento dos dados contou com quatro etapas que compreenderam a produção didática dos estudantes através do desenvolvimento de problemas ou desafios de programação, o estudo das referidas teorias, em especial as categorias “Aprendizagem”, “Emoções e Sentimentos”, “Estímulo Emocional Competente”, “Abstração Reflexionante” e “Self”, a reelaboração da produção didática com base no estudo realizado e a análise dessa produção Os dados junto aos estudantes matriculados na disciplina foram coletados através de entrevista oral e de questionário online. A análise do material didático, desenvolvido pelos estudantes, verifica a presença textual dos três primeiros elementos de referência da prática computacional estabelecidos pelo Instituto de Tecnologia de Massachusetts – MIT: 1. Ação interativa-incremental, 2. Teste-depuração, 3.Reutilização-reformulação e 4.Abstração-modulação. A análise dos processos de abstração pseudoempírica e reflexionante permitiram entender que os resultados apontam a influência do estudo de Epistemologia Genética e Neurociência Cognitiva na produção didática dos estudantes de Licenciatura em Computação. Os problemas de programação reelaborados por nove estudantes apresentam modificações intermediárias ou muitas modificações. Conclui-se que a produção de material didático para o ensino de Computação no Ensino Fundamental pode assumir um caráter desafiador, através de descrição textual que privilegia a ação de quem resolve problemas de programação. / The offer of graduation programs in Computer Science for Teaching has been expended in Brazil. This graduation program belongs to a recent area of knowledge: Computing, adding other areas such as Education. It entails difficulties that require academic and social discussion. One of the difficulties is the production of didactic material for Computing Teaching; this material is developed by the students, but generally without adequate theoretical basis. In order to contribute to overcoming this gap, the objective research decided to analyze the influence of the study Genetic Epistemology and Cognitive Neuroscience in the didactic production of undergraduate students in Computer Science for Teaching, through the elaboration of problems or challenges of Programming Language, for the Computing Teaching in Elementary School. The Method relied on activities carried out in the subject Articulating Practices in Computing IV of the in Computer Science for Teaching course of the University of Santa Cruz do Sul – UNISC, with the participation of eleven students. The programming languages explored for the production of didactic material were FMSLogo, Scratch and ROBOKIT. The data collection had four stages that comprised the didactic production of the students through the development of problems or programming challenges, the study of these theories, in particular the categories “learning”, “emotions and feelings”, “competent emotional stimulus”, “reflective abstraction” and “self” the re-elaboration of didactic production based on the realized study and the analysis of this production The collected data from the enrolled students in the subject were collected through an interview based on the Jean Piaget Clinical Method and an online questionnaire. The analysis of the didactic material, developed by the students, verifies the textual presence of the first three elements of computational practice established by the Massachusetts Institute of Technology - MIT: 1. Interactive-incremental action, 2. Test-Depuration, 3. Reuse-reformulation and 4. Abstraction-modulation. The analysis of the processes of pseudoempirical and reflective abstraction processes allowed to understand that the results point to the influence of Genetic Epistemology and Cognitive Neuroscience study in the didactic production of Computer Science for Teaching students. Programming problems reworked by nine students present intermediate modifications or many modifications. It is concluded that the production of didactic material for the Computing teaching in the elementary school can assume a challenging character, through a textual description that privileges the action of those who solve programming problems.

A presente pesquisa aborda um problema de roteirização e programação de veículos incorporando uma nova restrição operacional: a requisição simultânea de múltiplos veículos para atendimento da demanda. Trata-se de uma característica encontrada em operações de apoio à exploração de petróleo \"offshore\", em que mais de uma embarcação é requerida para executar tarefas de reboque e lançamento de linhas de ancoragem. Esta imposição, somada às restrições de janela de tempo, precedência entre tarefas, autonomia das embarcações e atendimento integral da demanda, configuram este problema. A programação é orientada pela minimização dos custos variáveis da operação e dos custos associados ao nível de serviço no atendimento. Este problema é uma variação do problema clássico de roteirização e programação de veículos com janela de tempo, de classe NP-Difícil. Nesta pesquisa, propõe-se modelar e resolver o problema em escala real por meio do algoritmo \"branch and cut\" acoplado às heurísticas de busca em vizinhança \"local branching\" e \"variable neighborhood search\". Para gerar as soluções iniciais será empregado o método \"feasibility pump\" e uma heurística construtiva. / This research focuses a fleet scheduling problem with new operational constraints: each task requiring multiple types of vehicles simultaneously. This kind of operation occurs in offshore exploitation and production sites, when more than one vessel is needed to accomplish the tugging and mooring of oil platforms. Other constraints are maintained such as time windows, precedence between tasks, route duration and the demand attendance. The solution schedules are cost oriented, which encompasses the routing variable costs and the customer service costs. This is a variation of the classical fleet routing and scheduling, which is an NP-Hard problem. This research aims to solve the real scale problem through a combined use of branch and cut strategy with local search algorithms such as local branching and variable neighborhood search. An efficient heuristic rule will be used in order to generate initial solutions using the feasibility pump method.