•Three algorithms to generate Pareto front representations are developed.•The algorithms are based on the epsilon-constraint method.•Diverse multi-objective integer linear programming problems are ...studied.•The algorithms were efficient on an extensive set of tests.
Dealing with multi-objective problems by using generation methods has some interesting advantages since it provides the decision-maker with the complete information about the set of non-dominated criterion vectors (Pareto front) and a clear overview of the different trade-offs of the problem. However, providing many solutions to the decision-maker may also be overwhelming. As an alternative approach, showing a representative set of the Pareto front may be advantageous. Choosing such a representative set is by itself also a multi-objective problem that must consider the number of alternatives to present, the uniformity, and/or the coverage of the representation, to guarantee its quality. This paper proposes three algorithms for the representation problem for multi-objective integer linear programming problems with two or more objective functions, each one of them dealing with each dimension of the problem (cardinality, coverage, and uniformity). Such algorithms are all based on the ϵ-constraint approach. In addition, the paper also presents strategies to overcome poor estimations of the Pareto front bounds. The algorithms were tested on the ability to efficiently generate the whole Pareto front or a representation of it. The uniformity and cardinality algorithms proved to be very efficient both on binary and on integer problems, being amongst the best in the literature. Both coverage and uniformity algorithms provide good quality representations on their targeted objective, while the cardinality algorithm appears to be the most flexible, privileging uniformity for lower cardinality representations and coverage on higher cardinality.
•We consider the nonstationary lot-sizing problem under correlated demand.•We present the first mathematical programming-based solution method.•Our method can tackle demand under various ...assumptions.•Our method leads to near-optimal solutions and low dispersions.
This paper extends the single-item single-stocking location nonstationary stochastic inventory problem to relax the assumption of independent demand. We present a mathematical programming-based solution method built upon an existing piecewise linear approximation strategy under the receding horizon control framework. Our method can be implemented by leveraging off-the-shelf mixed-integer linear programming solvers. It can tackle demand under various assumptions: the multivariate normal distribution, a collection of time-series processes, and the Martingale Model of Forecast Evolution. We compare against exact solutions obtained via stochastic dynamic programming to demonstrate that our method leads to near-optimal plans.
This article reviews the recent development of adaptive dynamic programming (ADP) with applications in control. First, its applications in optimal regulation are introduced, and some skilled and ...efficient algorithms are presented. Next, the use of ADP to solve game problems, mainly nonzero-sum game problems, is elaborated. It is followed by applications in large-scale systems. Note that although the functions presented in this article are based on continuous-time systems, various applications of ADP in discrete-time systems are also analyzed. Moreover, in each section, not only some existing techniques are discussed, but also possible directions for future work are pointed out. Finally, some overall prospects for the future are given, followed by conclusions of this article. Through a comprehensive and complete investigation of its applications in many existing fields, this article fully demonstrates that the ADP intelligent control method is promising in today's artificial intelligence era. Furthermore, it also plays a significant role in promoting economic and social development.
•Surveys literature starting from 1950s era military applications.•Covers interdiction problems dealing with asymmetric information and stochasticity.•Focuses on mathematical programming based ...analyses of interdiction problems.
This paper discusses the development of interdiction optimization models and algorithms, with an emphasis on mathematical programming techniques and future research challenges in the field. After presenting basic interdiction concepts and notation, we recount the motivation and models behind founding research in the network interdiction field. Next, we examine some of the most common means of solving interdiction problems, focusing on dualization models and extended formulations solvable by row-generation techniques. We then examine contemporary interdiction problems involving incomplete information, information asymmetry, stochasticity, and dynamic play. We conclude by discussing several emerging applications in the field of network interdiction.
Coding, once considered an arcane craft practiced by solitary techies, is now recognized by educators and theorists as a crucial skill, even a new literacy, for all children. Programming is often ...promoted in K-12 schools as a way to encourage "computational thinking" -- which has now become the umbrella term for understanding what computer science has to contribute to reasoning and communicating in an ever-increasingly digital world.InConnected Code,Yasmin Kafai and Quinn Burke argue that although computational thinking represents an excellent starting point, the broader conception of "computational participation" better captures the twenty-first-century reality. Computational participation moves beyond the individual to focus on wider social networks and a DIY culture of digital "making." Kafai and Burke describe contemporary examples of computational participation: students who code not for the sake of coding but to create games, stories, and animations to share; the emergence of youth programming communities; the practices and ethical challenges of remixing (rather than starting from scratch); and the move beyond stationary screens to programmable toys, tools, and textiles.
This study implemented an intervention using a visual programming language (VPL) to improve students' understanding of basic programming concepts. The VPL learning environment may reduce the ...difficulties in programming language learning and is suitable for teaching students who are not computer science majors. Meanwhile, the difference in learning performance of students with different levels of self-efficacy was explored. The basic programming concepts included sequence, condition, and loop. A quasi-experimental design was employed in this study. The participants consisted of 180 students taking general courses at a university in southern Taiwan. Instruments included the Test of Basic Programming Concept and a self-efficacy questionnaire. The results indicated that the VPL teaching improved learners' understanding of basic programming concepts in the experimental group. The effect on basic programming concepts was especially large in students with moderate and low self-efficacy. The implication is that the VPL has extensive potential for programming courses in the general education of universities.
•This study implemented an intervention using the visual programming language.•App Inventor 2 was used to improve students' basic programming concepts.•The design-based learning strategy was used to the better understanding of the effects.•The visual programming language teaching improved learners' concepts.•The effect was especially large in students with moderate and low self-efficacy.
•We propose an exact mixed integer linear program for agile satellites scheduling.•The model includes time window distributions and observation resource capacities.•Conflict indicators of visible ...time windows constitute central decision variables.•Using 5-index variables obviates the need for a Big-M approach.•We feasibly reach an optimality gap of less than 2.5% on all test instances.
We address the multi-satellite scheduling problem with limited observation capacities that arises from the need to observe a set of targets on the Earth’s surface using imaging resources installed on a set of satellites. We define and analyze the conflict indicators of all available visible time windows of missions, as well as the feasible time intervals of resources. The problem is then formulated as a mixed integer linear programming model, in which constraints are derived from a careful analysis of the interdependency between feasible time intervals that are eligible for observations. We apply the proposed model to several different problem instances that reflect real-world situations. The computational results verify that our approach is effective for obtaining optimum solutions or solutions with a very good quality.
•We address the integration of passenger demand oriented train scheduling and rolling stock circulation for urban rail transit lines.•We propose three optimization methods to construct the train ...schedule and rolling stock circulation plan simultaneously.•We investigate the benefits of the integration, the performance comparison between the proposed approaches, and the sensitivity analysis.•Our integrated model and solution methods can be used in rail practice to obtain better train schedules and circulation plans automatically.
We study the integration of train scheduling and rolling stock circulation planning under time-varying passenger demand for an urban rail transit line, where the practical train operation constraints, e.g., the capacity of trains, the number of available rolling stocks, and the entering/exiting depot operations, are considered. Three solution approaches are proposed to solve the resulting multi-objective mixed-integer nonlinear programming (MINLP) problem to deliver both an irregular train schedule (i.e., departure and arrival times of all train services) and a rolling stock circulation plan (including entering/exiting depot operations of rolling stocks and connections between train services) simultaneously. We first present an iterative nonlinear programming (INP) approach, where the solutions of the original MINLP problem are obtained by solving a nonlinear programming problem and a mixed integer linear programming (MILP) problem iteratively. Moreover, an equivalent MILP formulation of the original MINLP model is developed and an approximated MILP approach is proposed to reduce the number of constraints introduced by passenger demand. A case study is conducted based on the practical data of the Beijing Yizhuang line, where the three proposed approaches are compared with a state-of-the-art approach and a practical method used by the traffic planners. This comparison shows the effectiveness and efficiency of the three proposed approaches.
This paper proposes three strong second order cone programming (SOCP) relaxations for the AC optimal power flow (OPF) problem. These three relaxations are incomparable to each other and two of them ...are incomparable to the standard SDP relaxation of OPF. Extensive computational experiments show that these relaxations have numerous advantages over existing convex relaxations in the literature: (i) their solution quality is extremely close to that of the standard SDP relaxation (the best one is within 99.96% of the SDP relaxation on average for all the IEEE test cases) and consistently outperforms previously proposed convex quadratic relaxations of the OPF problem, (ii) the solutions from the strong SOCP relaxations can be directly used as a warm start in a local solver such as IPOPT to obtain a high quality feasible OPF solution, and (iii) in terms of computation times, the strong SOCP relaxations can be solved an order of magnitude faster than the standard SDP relaxation. For example, one of the proposed SOCP relaxations together with IPOPT produces a feasible solution for the largest instance in the IEEE test cases (the 3375-bus system) and also certifies that this solution is within 0.13% of global optimality, all this computed within 157.20 seconds on a modest personal computer. Overall, the proposed strong SOCP relaxations provide a practical approach to obtain feasible OPF solutions with extremely good quality within a time framework that is compatible with the real-time operation in the current industry practice.
This second edition of Grune and Jacobs' brilliant work presents new developments and discoveries that have been made in the field of parsing, or syntax analysis. Parsing has been and continues to be ...an essential part of computer science and linguistics.
PDF
