N–Dimensional Orthogonal Tile Sizing Problem

AMS subject classification: 68Q22, 90C90

A Fast Algorithm for Weber Problem on a Grid

AMS subject classification: 90B80.

On the Zeros of the Solutions to Nonlinear Hyperbolic Equations with Delays

2002 Mathematics Subject Classification: Primary 35В05; Secondary 35L15

Sensor Location Problem for a Multigraph

MSC 2010: 05C50, 15A03, 15A06, 65K05, 90C08, 90C35

Solution of the Least Squares Method problem of pairwise comparison matrices

The aim of the paper is to present a new global optimization method for determining all the optima of the Least Squares Method (LSM) problem of pairwise comparison matrices. Such matrices are used, e.g., in the Analytic Hierarchy Process (AHP). Unlike some other distance minimizing methods, LSM is usually hard to solve because of the corresponding nonlinear and non-convex objective function. It is found that the optimization problem can be reduced to solve a system of polynomial equations. Homotopy method is applied which is an efficient technique for solving nonlinear systems. The paper ends by two numerical example having multiple global and local minima.

A nettó jelenérték maximalizálása erőforrás-korlátos projektekben - egy új harmóniakereső metaheurisztika (A harmony search metaheuristic for the resourceconstrained project scheduling problem with discounted cash flows)

Ebben a tanulmányban a szerző egy új harmóniakereső metaheurisztikát mutat be, amely a minimális időtartamú erőforrás-korlátos ütemezések halmazán a projekt nettó jelenértékét maximalizálja. Az optimális ütemezés elméletileg két egész értékű (nulla-egy típusú) programozási feladat megoldását jelenti, ahol az első lépésben meghatározzuk a minimális időtartamú erőforrás-korlátos ütemezések időtartamát, majd a második lépésben az optimális időtartamot feltételként kezelve megoldjuk a nettó jelenérték maximalizálási problémát minimális időtartamú erőforrás-korlátos ütemezések halmazán. A probléma NP-hard jellege miatt az egzakt megoldás elfogadható idő alatt csak kisméretű projektek esetében képzelhető el. A bemutatandó metaheurisztika a Csébfalvi (2007) által a minimális időtartamú erőforrás-korlátos ütemezések időtartamának meghatározására és a tevékenységek ennek megfelelő ütemezésére kifejlesztett harmóniakereső metaheurisztika továbbfejlesztése, amely az erőforrás-felhasználási konfliktusokat elsőbbségi kapcsolatok beépítésével oldja fel. Az ajánlott metaheurisztika hatékonyságának és életképességének szemléltetésére számítási eredményeket adunk a jól ismert és népszerű PSPLIB tesztkönyvtár J30 részhalmazán futtatva. Az egzakt megoldás generálásához egy korszerű MILP-szoftvert (CPLEX) alkalmaztunk. _______________ This paper presents a harmony search metaheuristic for the resource-constrained project scheduling problem with discounted cash flows. In the proposed approach, a resource-constrained project is characterized by its „best” schedule, where best means a makespan minimal resource constrained schedule for which the net present value (NPV) measure is maximal. Theoretically the optimal schedule searching process is formulated as a twophase mixed integer linear programming (MILP) problem, which can be solved for small-scale projects in reasonable time. The applied metaheuristic is based on the "conflict repairing" version of the "Sounds of Silence" harmony search metaheuristic developed by Csébfalvi (2007) for the resource-constrained project scheduling problem (RCPSP). In order to illustrate the essence and viability of the proposed harmony search metaheuristic, we present computational results for a J30 subset from the well-known and popular PSPLIB. To generate the exact solutions a state-of-the-art MILP solver (CPLEX) was used.

Optimization of pavement maintenance and rehabilitation programming using shuffled complex evolution algorithm

The major barrier to practical optimization of pavement preservation programming has always been that for formulations where the identity of individual projects is preserved, the solution space grows exponentially with the problem size to an extent where it can become unmanageable by the traditional analytical optimization techniques within reasonable limit. This has been attributed to the problem of combinatorial explosion that is, exponential growth of the number of combinations. The relatively large number of constraints often presents in a real-life pavement preservation programming problems and the trade-off considerations required between preventive maintenance, rehabilitation and reconstruction, present yet another factor that contributes to the solution complexity. In this research study, a new integrated multi-year optimization procedure was developed to solve network level pavement preservation programming problems, through cost-effectiveness based evolutionary programming analysis, using the Shuffled Complex Evolution (SCE) algorithm.^ A case study problem was analyzed to illustrate the robustness and consistency of the SCE technique in solving network level pavement preservation problems. The output from this program is a list of maintenance and rehabilitation treatment (M&R) strategies for each identified segment of the network in each programming year, and the impact on the overall performance of the network, in terms of the performance levels of the recommended optimal M&R strategy. ^ The results show that the SCE is very efficient and consistent in the simultaneous consideration of the trade-off between various pavement preservation strategies, while preserving the identity of the individual network segments. The flexibility of the technique is also demonstrated, in the sense that, by suitably coding the problem parameters, it can be used to solve several forms of pavement management programming problems. It is recommended that for large networks, some sort of decomposition technique should be applied to aggregate sections, which exhibit similar performance characteristics into links, such that whatever M&R alternative is recommended for a link can be applied to all the sections connected to it. In this way the problem size, and hence the solution time, can be greatly reduced to a more manageable solution space. ^ The study concludes that the robust search characteristics of SCE are well suited for solving the combinatorial problems in long-term network level pavement M&R programming and provides a rich area for future research. ^

The order selection and lot sizing problem in the make-to-order environment

This research is motivated by the need for considering lot sizing while accepting customer orders in a make-to-order (MTO) environment, in which each customer order must be delivered by its due date. Job shop is the typical operation model used in an MTO operation, where the production planner must make three concurrent decisions; they are order selection, lot size, and job schedule. These decisions are usually treated separately in the literature and are mostly led to heuristic solutions. The first phase of the study is focused on a formal definition of the problem. Mathematical programming techniques are applied to modeling this problem in terms of its objective, decision variables, and constraints. A commercial solver, CPLEX is applied to solve the resulting mixed-integer linear programming model with small instances to validate the mathematical formulation. The computational result shows it is not practical for solving problems of industrial size, using a commercial solver. The second phase of this study is focused on development of an effective solution approach to this problem of large scale. The proposed solution approach is an iterative process involving three sequential decision steps of order selection, lot sizing, and lot scheduling. A range of simple sequencing rules are identified for each of the three subproblems. Using computer simulation as the tool, an experiment is designed to evaluate their performance against a set of system parameters. For order selection, the proposed weighted most profit rule performs the best. The shifting bottleneck and the earliest operation finish time both are the best scheduling rules. For lot sizing, the proposed minimum cost increase heuristic, based on the Dixon-Silver method performs the best, when the demand-to-capacity ratio at the bottleneck machine is high. The proposed minimum cost heuristic, based on the Wagner-Whitin algorithm is the best lot-sizing heuristic for shops of a low demand-to-capacity ratio. The proposed heuristic is applied to an industrial case to further evaluate its performance. The result shows it can improve an average of total profit by 16.62%. This research contributes to the production planning research community with a complete mathematical definition of the problem and an effective solution approach to solving the problem of industry scale.

Nonlinear quantum transport in low-dimensional electronic devices

The study of transport processes in low-dimensional semiconductors requires a rigorous quantum mechanical treatment. However, a full-fledged quantum transport theory of electrons (or holes) in semiconductors of small scale, applicable in the presence of external fields of arbitrary strength, is still not available. In the literature, different approaches have been proposed, including: (a) the semiclassical Boltzmann equation, (b) perturbation theory based on Keldysh's Green functions, and (c) the Quantum Boltzmann Equation (QBE), previously derived by Van Vliet and coworkers, applicable in the realm of Kubo's Linear Response Theory (LRT). ^ In the present work, we follow the method originally proposed by Van Wet in LRT. The Hamiltonian in this approach is of the form: H = H 0(E, B) + λV, where H0 contains the externally applied fields, and λV includes many-body interactions. This Hamiltonian differs from the LRT Hamiltonian, H = H0 - AF(t) + λV, which contains the external field in the field-response part, -AF(t). For the nonlinear problem, the eigenfunctions of the system Hamiltonian, H0(E, B), include the external fields without any limitation on strength. ^ In Part A of this dissertation, both the diagonal and nondiagonal Master equations are obtained after applying projection operators to the von Neumann equation for the density operator in the interaction picture, and taking the Van Hove limit, (λ → 0, t → ∞, so that (λ2 t)n remains finite). Similarly, the many-body current operator J is obtained from the Heisenberg equation of motion. ^ In Part B, the Quantum Boltzmann Equation is obtained in the occupation-number representation for an electron gas, interacting with phonons or impurities. On the one-body level, the current operator obtained in Part A leads to the Generalized Calecki current for electric and magnetic fields of arbitrary strength. Furthermore, in this part, the LRT results for the current and conductance are recovered in the limit of small electric fields. ^ In Part C, we apply the above results to the study of both linear and nonlinear longitudinal magneto-conductance in quasi one-dimensional quantum wires (1D QW). We have thus been able to quantitatively explain the experimental results, recently published by C. Brick, et al., on these novel frontier-type devices. ^

Nonlinear quantum transport in low-dimensional electronic devices

The study of transport processes in low-dimensional semiconductors requires a rigorous quantum mechanical treatment. However, a full-fledged quantum transport theory of electrons (or holes) in semiconductors of small scale, applicable in the presence of external fields of arbitrary strength, is still not available. In the literature, different approaches have been proposed, including: (a) the semiclassical Boltzmann equation, (b) perturbation theory based on Keldysh's Green functions, and (c) the Quantum Boltzmann Equation (QBE), previously derived by Van Vliet and coworkers, applicable in the realm of Kubo's Linear Response Theory (LRT). In the present work, we follow the method originally proposed by Van Vliet in LRT. The Hamiltonian in this approach is of the form: H = H°(E, B) + λV, where H0 contains the externally applied fields, and λV includes many-body interactions. This Hamiltonian differs from the LRT Hamiltonian, H = H° - AF(t) + λV, which contains the external field in the field-response part, -AF(t). For the nonlinear problem, the eigenfunctions of the system Hamiltonian, H°(E, B) , include the external fields without any limitation on strength. In Part A of this dissertation, both the diagonal and nondiagonal Master equations are obtained after applying projection operators to the von Neumann equation for the density operator in the interaction picture, and taking the Van Hove limit, (λ → 0 , t → ∞ , so that (λ2 t)n remains finite). Similarly, the many-body current operator J is obtained from the Heisenberg equation of motion. In Part B, the Quantum Boltzmann Equation is obtained in the occupation-number representation for an electron gas, interacting with phonons or impurities. On the one-body level, the current operator obtained in Part A leads to the Generalized Calecki current for electric and magnetic fields of arbitrary strength. Furthermore, in this part, the LRT results for the current and conductance are recovered in the limit of small electric fields. In Part C, we apply the above results to the study of both linear and nonlinear longitudinal magneto-conductance in quasi one-dimensional quantum wires (1D QW). We have thus been able to quantitatively explain the experimental results, recently published by C. Brick, et al., on these novel frontier-type devices.

Parallel Problem Solving from Nature – PPSN XIV:14th International Conference, Edinburgh, UK, September 17-21, 2016, Proceedings

This book constitutes the refereed proceedings of the 14th International Conference on Parallel Problem Solving from Nature, PPSN 2016, held in Edinburgh, UK, in September 2016. The total of 93 revised full papers were carefully reviewed and selected from 224 submissions. The meeting began with four workshops which offered an ideal opportunity to explore specific topics in intelligent transportation Workshop, landscape-aware heuristic search, natural computing in scheduling and timetabling, and advances in multi-modal optimization. PPSN XIV also included sixteen free tutorials to give us all the opportunity to learn about new aspects: gray box optimization in theory; theory of evolutionary computation; graph-based and cartesian genetic programming; theory of parallel evolutionary algorithms; promoting diversity in evolutionary optimization: why and how; evolutionary multi-objective optimization; intelligent systems for smart cities; advances on multi-modal optimization; evolutionary computation in cryptography; evolutionary robotics - a practical guide to experiment with real hardware; evolutionary algorithms and hyper-heuristics; a bridge between optimization over manifolds and evolutionary computation; implementing evolutionary algorithms in the cloud; the attainment function approach to performance evaluation in EMO; runtime analysis of evolutionary algorithms: basic introduction; meta-model assisted (evolutionary) optimization. The papers are organized in topical sections on adaption, self-adaption and parameter tuning; differential evolution and swarm intelligence; dynamic, uncertain and constrained environments; genetic programming; multi-objective, many-objective and multi-level optimization; parallel algorithms and hardware issues; real-word applications and modeling; theory; diversity and landscape analysis.

Dynamic Programming Approaches for Estimating and Applying Large-scale Discrete Choice Models

People go through their life making all kinds of decisions, and some of these decisions affect their demand for transportation, for example, their choices of where to live and where to work, how and when to travel and which route to take. Transport related choices are typically time dependent and characterized by large number of alternatives that can be spatially correlated. This thesis deals with models that can be used to analyze and predict discrete choices in large-scale networks. The proposed models and methods are highly relevant for, but not limited to, transport applications. We model decisions as sequences of choices within the dynamic discrete choice framework, also known as parametric Markov decision processes. Such models are known to be difficult to estimate and to apply to make predictions because dynamic programming problems need to be solved in order to compute choice probabilities. In this thesis we show that it is possible to explore the network structure and the flexibility of dynamic programming so that the dynamic discrete choice modeling approach is not only useful to model time dependent choices, but also makes it easier to model large-scale static choices. The thesis consists of seven articles containing a number of models and methods for estimating, applying and testing large-scale discrete choice models. In the following we group the contributions under three themes: route choice modeling, large-scale multivariate extreme value (MEV) model estimation and nonlinear optimization algorithms. Five articles are related to route choice modeling. We propose different dynamic discrete choice models that allow paths to be correlated based on the MEV and mixed logit models. The resulting route choice models become expensive to estimate and we deal with this challenge by proposing innovative methods that allow to reduce the estimation cost. For example, we propose a decomposition method that not only opens up for possibility of mixing, but also speeds up the estimation for simple logit models, which has implications also for traffic simulation. Moreover, we compare the utility maximization and regret minimization decision rules, and we propose a misspecification test for logit-based route choice models. The second theme is related to the estimation of static discrete choice models with large choice sets. We establish that a class of MEV models can be reformulated as dynamic discrete choice models on the networks of correlation structures. These dynamic models can then be estimated quickly using dynamic programming techniques and an efficient nonlinear optimization algorithm. Finally, the third theme focuses on structured quasi-Newton techniques for estimating discrete choice models by maximum likelihood. We examine and adapt switching methods that can be easily integrated into usual optimization algorithms (line search and trust region) to accelerate the estimation process. The proposed dynamic discrete choice models and estimation methods can be used in various discrete choice applications. In the area of big data analytics, models that can deal with large choice sets and sequential choices are important. Our research can therefore be of interest in various demand analysis applications (predictive analytics) or can be integrated with optimization models (prescriptive analytics). Furthermore, our studies indicate the potential of dynamic programming techniques in this context, even for static models, which opens up a variety of future research directions.

Improved Implicit Optimal Modeling of the Labor Shift Scheduling Problem

This paper presents an integer programming model for developing optimal shift schedules while allowing extensive flexibility in terms of alternate shift starting times, shift lengths, and break placement. The model combines the work of Moondra (1976) and Bechtold and Jacobs (1990) by implicitly matching meal breaks to implicitly represented shifts. Moreover, the new model extends the work of these authors to enable the scheduling of overtime and the scheduling of rest breaks. We compare the new model to Bechtold and Jacobs' model over a diverse set of 588 test problems. The new model generates optimal solutions more rapidly, solves problems with more shift alternatives, and does not generate schedules violating the operative restrictions on break timing.

Climbing Up the Leaderboard: An Empirical Study of Applying Gamification Techniques to a Computer Programming Class

Conventional taught learning practices often experience difficulties in keeping students motivated and engaged. Video games, however, are very successful at sustaining high levels of motivation and engagement through a set of tasks for hours without apparent loss of focus. In addition, gamers solve complex problems within a gaming environment without feeling fatigue or frustration, as they would typically do with a comparable learning task. Based on this notion, the academic community is keen on exploring methods that can deliver deep learner engagement and has shown increased interest in adopting gamification – the integration of gaming elements, mechanics, and frameworks into non-game situations and scenarios – as a means to increase student engagement and improve information retention. Its effectiveness when applied to education has been debatable though, as attempts have generally been restricted to one-dimensional approaches such as transposing a trivial reward system onto existing teaching materials and/or assessments. Nevertheless, a gamified, multi-dimensional, problem-based learning approach can yield improved results even when applied to a very complex and traditionally dry task like the teaching of computer programming, as shown in this paper. The presented quasi-experimental study used a combination of instructor feedback, real time sequence of scored quizzes, and live coding to deliver a fully interactive learning experience. More specifically, the “Kahoot!” Classroom Response System (CRS), the classroom version of the TV game show “Who Wants To Be A Millionaire?”, and Codecademy’s interactive platform formed the basis for a learning model which was applied to an entry-level Python programming course. Students were thus allowed to experience multiple interlocking methods similar to those commonly found in a top quality game experience. To assess gamification’s impact on learning, empirical data from the gamified group were compared to those from a control group who was taught through a traditional learning approach, similar to the one which had been used during previous cohorts. Despite this being a relatively small-scale study, the results and findings for a number of key metrics, including attendance, downloading of course material, and final grades, were encouraging and proved that the gamified approach was motivating and enriching for both students and instructors.

Database evolution on an orthogonal persistent programming system: A semi-transparent approach

In this paper the problem of the evolution of an object-oriented database in the context of orthogonal persistent programming systems is addressed. We have observed two characteristics in that type of systems that offer particular conditions to implement the evolution in a semi-transparent fashion. That transparency can further be enhanced with the obliviousness provided by the Aspect-Oriented Programming techniques. Was conceived a meta-model and developed a prototype to test the feasibility of our approach. The system allows programs, written to a schema, access semi-transparently to data in other versions of the schema.