| 1. |
- Blikstad, Mathias, et al.
(författare)
-
A constraint generation procedure for pre-runtime scheduling of integrated modular avionic systems
- 2017
-
Ingår i: Proceedings of the 13th Workshop on Models and Algorithms for Planning and Scheduling Problems.
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)abstract
- In modern integrated modular avionic systems, applications share hardware resources on a common avionic platform. Such an architecture necessitates strict requirements on the spatial and temporal partitioning of the system to prevent fault propagation between different aircraft functions. One way to establish a temporal partitioning is through pre-runtime scheduling of the system, which involves creating a schedule for both tasks and a communication network.While the avionic systems are growing more and more complex, so is the challenge of scheduling them. Scheduling of the system has an important role in the development of new avionic systems since functionality typically is added to the system over a period of several years and a scheduling tool is used both to detect if the platform can host the new functionality and, in case this is possible, to create a new schedule. For this reason an exact solution strategy for avionics scheduling is preferred over a heuristic one.In this paper we present a mathematical model for an industrially relevant avionic system and present a constraint generation procedure for scheduling of such systems. We apply our optimisation approach to instances provided by our industrial partner. These instances are of relevance for the development of future avionic systems and contain up to 20 000 tasks to be scheduled. The computational results show that our optimisation approach can be used to create schedules for such instances within reasonable time.
|
|
| 2. |
- Blikstad, Mathias, et al.
(författare)
-
An optimisation approach for pre-runtime scheduling of tasks and communication in an integrated modular avionic system
- 2018
-
Ingår i: Optimization and Engineering. - : Springer Science and Business Media LLC. - 1389-4420 .- 1573-2924. ; 19:4, s. 977-1004
-
Tidskriftsartikel (refereegranskat)abstract
- In modern integrated modular avionic systems, applications share hardware resources on a common avionic platform. Such an architecture necessitates strict requirements on the spatial and temporal partitioning of the system to prevent fault propagation between different aircraft functions. One way to establish a temporal partitioning is through pre-runtime scheduling of the system, which involves creating a schedule for both tasks and a communication network. While avionic systems are growing more and more complex, so is the challenge of scheduling them. The scheduling of the system has an important role in the development of new avionic systems, since functionality is typically added to the system over a period of several years and a scheduling tool is used both to detect if the platform can host the new functionality and, if this is possible, to create a new schedule. For this reason an exact solution strategy for avionics scheduling is preferred over a heuristic one. In this paper we present a mathematical model for an industrially relevant avionic system and present a constraint generation procedure for the scheduling of such systems. We apply our optimisation approach to instances provided by our industrial partner. These instances are of relevance for the development of future avionic systems and contain up to 20,000 tasks to be scheduled. The computational results show that our optimisation approach can be used to create schedules for such instances within a reasonable time.
|
|
| 3. |
- Hajizadeh, Roghayeh, 1986-
(författare)
-
Optimization of Snow Removal in Cities
- 2023
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Removing snow in a city is an unavoidable task in Nordic countries like Sweden. A number of streets in an area need to be cleared of snow by a limited number of vehicles and the tours for the vehicles must be planned in order to minimize the time and/or cost. Since the amount of snow can vary significantly from one year to another, the plans/tours of one year cannot be used for the next year. Hence, new tours need to be planned each time. Snow removal can be done in rural or urban areas and in addition during snowfall or after a snowfall. In this thesis, we study urban snow removal after a snowfall. There are different relevant specifics of the urban snow removal problem. For instance, there are different types of streets which need different numbers of sweeps in order to remove the snow. In addition, some tasks must be done before other tasks can be started. This leads to precedence constraints. Furthermore, each vehicle needs a certain time to switch from a task to another task. The problem can be formulated as a huge time-indexed mixed integer programming which often is not directly solvable in practice. The contributions of this thesis include the study of different relaxations and heuristics to find feasible solutions and improve the bounds on the optimal objective function values which are discussed in five papers. Paper I deals with single vehicle snow removal. A branch-and-dive heuristic based on branch-and-bound principles is given in order to improve the solutions and bounds. In Paper II, feasible solutions for the snow removal problem with a limited number of identical vehicles are obtained. First, the work is broken down into smaller parts, one for each vehicle. Based on the obtained allocation, a feasible tour for each single vehicle snow removal is obtained. Finally, combined solution approaches and co-ordination of the vehicles to find a feasible solution for the original problem are discussed. In order to improve the computational efficiency, one can take advantage of the tree structure, since modern real life city networks often contain parts that are trees. In Paper III, tree parts are studied and a tree elimination procedure is given for the snow removal problem, to be used before searching for optimal tours. Two variations encountered in practice for normal streets are compared in Paper IV. The first variant is doing a middle sweep before the two side sweeps and the second one is doing only side sweeps. Paper V studies the problem from modeling perspective. The problem is formulated as a mixed integer programming model and different relaxations of it are investigated. Finally, Lagrangian relaxation of the problem is studied in Paper VI. Different possibilities for Lagrangian relaxations are investigated and subgradient optimization is used to solve the Lagrangian dual.
|
|
| 4. |
- Horn, Matthias, et al.
(författare)
-
A*-based construction of decision diagrams for a prize-collecting scheduling problem
- 2021
-
Ingår i: Computers & Operations Research. - : Elsevier. - 0305-0548 .- 1873-765X. ; 126
-
Tidskriftsartikel (refereegranskat)abstract
- Decision diagrams (DDs) have proven to be useful tools in combinatorial optimization. Relaxed DDs represent discrete relaxations of problems, can encode essential structural information in a compact form, and may yield strong dual bounds. We propose a novel construction scheme for relaxed multi-valued DDs for a scheduling problem in which a subset of elements has to be selected from a ground set and the selected elements need to be sequenced. The proposed construction scheme builds upon A search guided by a fast-to-calculate problem-specific dual bound heuristic. In contrast to traditional DD compilation methods, the new approach does not rely on a correspondence of DD layers to decision variables. For the considered kind of problem, this implies that multiple nodes representing the same state at different layers can be avoided, and consequently also many redundant isomorphic substructures. For keeping the relaxed DD compact, a new mechanism for merging nodes in a layer-independent way is suggested. For our prize-collecting job sequencing problem, experimental results show that the DDs from our A -based approach provide substantially better bounds while frequently being an order-ofmagnitude smaller than DDs obtained from traditional compilation methods, given about the same time. To obtain a heuristic solution and a corresponding lower bound, we further propose to construct a restricted DD based on the relaxed one, thereby substantially exploiting already gained information. This approach outperforms a standalone restricted DD construction, basic constraint programming and mixed integer linear programming approaches, and a variable neighborhood search in terms of solution quality on most of our benchmark instances.
|
|
| 5. |
|
|
| 6. |
- Karlsson, Emil, 1990-, et al.
(författare)
-
A matheuristic approach to large-scale avionic scheduling
- 2019
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Pre-runtime scheduling of avionic systems is used to ensure that the systems provide the desired functionality at the correct time. This paper considers scheduling of an integrated modular avionic system which from a more general perspective can be seen as a multiprocessor scheduling problem that includes a communication network. The addressed system is practically relevant and the computational evaluations are made on large-scale instances developed together with the industrial partner Saab. A subset of the instances is made publicly available.Our contribution is a matheuristic for solving these large-scale instances and it is obtained by improving the model formulations used in a previously suggested constraint generation procedure and by including an adaptive large neighbourhood search to extend it into a matheuristic. Characteristics of our adaptive large neighbourhood search are that it is made over both discrete and continuous variables and that it needs to balance the search for feasibility and profitable objective value. The repair operation is to apply a mixed-integer programming solver on a model where most of the constraints are treated as soft and a violation of them is instead penalised in the objective function. The largest solved instance, with respect to the number of tasks, has 45 988 tasks and 2 011 communication messages.
|
|
| 7. |
|
|
| 8. |
- Karlsson, Emil, et al.
(författare)
-
Explicit modelling of multiple intervals in a constraint generation procedure for multiprocessor scheduling
- 2017
-
Ingår i: Operations Research Proceedings 2017. - Cham : Springer. - 9783319899190 - 9783319899206 ; , s. 567-572
-
Konferensbidrag (refereegranskat)abstract
- Multiprocessor scheduling is a well studied NP-hard optimisation problem that occurs in variety of forms. The focus of this paper is explicit modelling of multiple task intervals. This work extends a constraint generation procedure previously developed for an avionics scheduling context. We here address a relaxation of the original problem and this relaxation can be considered as multiprocessor scheduling with precedence relations and multiple intervals.The explicit modelling of multiple intervals strengthens the formulation used in the constraint generation procedure and we illustrate the computational effects on an industrial relevant avionics scheduling problem.
|
|
| 9. |
|
|
| 10. |
- Karlsson, Emil, 1990-, et al.
(författare)
-
Instance dataset for a multiprocessor scheduling problem with multiple time windows and time lags : Similar instances with large differences in difficulty
- 2022
-
Ingår i: Data in Brief. - : Elsevier. - 2352-3409. ; 45
-
Tidskriftsartikel (refereegranskat)abstract
- The dataset presented in this paper introduces 384 new instances for the feasibility version of a multiprocessor scheduling problem with multiple time windows, positive time lags and exact time lags. The instances are constructed from subproblems in a logic-based Benders decomposition scheme introduced in "Logic-based Benders decomposition with a partial assignment acceleration technique for an avionics scheduling problem" (Karlsson, E., Rönnberg, E., Computers & Operations Research, 2022) [1]. A key aspect of the dataset is that even if two instances are highly similar, the computational performance of solving them with an IBM ILOG CP Optimizer model can be vastly different. There exists for example 47 pairs of instances with the same number of tasks and exact time lags, and the number of positive time lags differs with at most two, where one instance can be solved within 5 minutes and the other instance cannot be solved within 24 hours. Such differences make the instance dataset useful for investigating differences in computational performance of constraint programming solvers. The dataset can also be used to benchmark methods for multiprocessor scheduling. The dataset has been released under the Creative Commons Attribution 4.0 International license and can be used as it is or be adapted.
|
|
| 11. |
- Karlsson, Emil, 1990-, et al.
(författare)
-
Logic-based Benders decomposition with a partial assignment acceleration technique for avionics scheduling
- 2022
-
Ingår i: Computers & Operations Research. - : Elsevier. - 0305-0548 .- 1873-765X. ; 146
-
Tidskriftsartikel (refereegranskat)abstract
- Pre-runtime scheduling of large-scale electronic systems, as those in modern aircraft, can be computationally challenging. In this paper, we study a distributed integrated modular avionic system of practical relevance where the scheduling includes to assign communication messages to time slots and to sequence tasks on modules. For this problem, the challenge is the huge number of tasks to be scheduled and the intricate interaction between the communication and task scheduling. We present a method based on Logic-Based Benders Decomposition (LBBD) to solve this problem. In a master problem, formulated as a mixed-integer program, communication messages are assigned to time slots and in a subproblem, formulated as a constraint program, tasks are scheduled.Our LBBD scheme is accelerated by using cut strengthening, a subproblem relaxation, and components for preprocessing and initialisation of the scheme. The cut strengthening is of the kind that systematically investigates subsets of variables to include in the cut by solving additional subproblems. To further enhance the efficiency of the scheme, we propose a new strategy that extends cut strengthening to also try to construct feasible solutions by using information from solving the additional subproblems. Our computational evaluation is based on publicly available instances with up to 2530 messages and 54,731 tasks. It shows that our method outperforms previous methods for the problem with respect to both solution times and RAM usage. A further evaluation of the different components in the method shows that our new acceleration strategy is important to achieve these results.
|
|
| 12. |
- Karlsson, Emil, 1990-
(författare)
-
Optimisation-based scheduling of an avionic system
- 2019
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Modern computer systems in aircraft are often based on an integrated modular avionic architecture. In this architecture, software applications share hardware resources on a common avionic platform. Many functions in an aircraft are controlled by software and a failure in such software can have severe consequences. In order to avoid malfunction, there are many aspects to consider. One aspect is to ensure that the activities in the system is done at the right time with the right resources. To analyse if this is possible or not is often called schedulability analysis.When multiple functions are using the same resources, the schedulability analysis becomes increasingly challenging. This thesis focuses on a pre-runtime scheduling problem of an integrated modular avionic system proposed by our industrial partner Saab. The purpose of this problem is to find a feasible schedule or prove that none exists as part of a schedulability analysis.For the system that we study, there are two major challenges. One is that task and communication scheduling are integrated and the other is that there is a large amount of tasks to schedule. For the largest instances, there are more than 10 000 tasks on a single module. In order to solve such problems, we have developed a matheuristic. At the core of this matheuristic is a constraint generation procedure designed to handle the challenges of the scheduling problem.The constraint generation procedure is based on first making a relaxed scheduling decision and then evaluating this in a separate problem where a complete schedule is produced. This yields a decomposition where most technical details are considered in the relaxed problem, and the actual scheduling of tasks is handled in a subproblem. Both the relaxed problem and the subproblem are formulated and solved as mixed integer programs.The heuristic component of the matheuristic is that the relaxed problem is solved using an adaptive large neighbourhood search method. Instead of solving the relaxed problem as a single mixed integer program, the adaptive large neighbourhood search explores neighbourhoods through solving a series of mixed integer programs. Features of this search method are that it is made over both discrete and continuous variables and it needs to balance feasibility against profitable objective value.The matheuristic described in this thesis has been implemented in a scheduling tool. This scheduling tool has been applied to instances provided by our industrial partner and to a set of public instances that we have developed. With this tool, we have solved instances with more than 45 000 tasks.
|
|
| 13. |
- Karlsson, Emil, 1990-
(författare)
-
Optimisation methods for solving a large-scale avionics scheduling problem
- 2021
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Modern computer systems in aircraft are based on an integrated modular avionic architecture. In this architecture, software applications share hardware resources on a common avionic platform. Many functions in an aircraft are controlled by software and a failure in such software can have severe consequences. To avoid malfunction, there are many aspects to consider. One aspect is to ensure that the activities in the system get sufficient computing and network communication resources while being completed in time. This thesis contributes to addressing this challenge by studying an avionics scheduling problem proposed by Saab.In this problem, tasks are performed on modules and the messages are sent on a communication network that links the modules. A schedule specifies start times for tasks on modules and the choices of time slots for messages on the communication network. For a schedule to be feasible, constraints must be respected: precedence constraints between tasks, timing constraints on tasks and messages, and communication network constraints involving both tasks and messages. For future platforms, it is expected that large-scale instances need to be solved. The methods introduced in this thesis solve instances with up to 55,000 tasks and 2500 messages.The thesis includes three papers that introduce methods for solving the avionics scheduling problem and one paper that compares techniques to improve the performance of a specific type of decomposition method. The solution methods for the avionics problem differ in how the decomposition is made, how the subproblems are solved, and if the algorithm is guaranteed to find a feasible solution or not, given enough time. Together, the contributions of these papers give an insight into the structure of this type of avionics scheduling problem and how this structure can be exploited to construct efficient exact and matheuristic scheduling methods.Paper A introduces a constraint generation procedure tailored for the avionics scheduling problem. In the constraint generation procedure, a preliminary, possibly infeasible, schedule is constructed by solving a master problem. This schedule is used to define a restriction of the problem, which is solved to find a complete schedule. If no schedule is found within a time-limit, constraints are added to the master problem, which is then solved again. This procedure relies on solving Mixed-Integer Programming (MIP) models. In Paper B, the constraint generation procedure is extended into a matheuristic, where the master problem is solved with a MIP-based adaptive large neighbourhood search. The methods in Paper A and Paper B can solve instances with up to 37,000 tasks and 1700 messages, and 55,000 tasks and 2500 messages, respectively.Logic-Based Benders Decomposition (LBBD) algorithms are treated in Paper C and Paper D. In both papers, a MIP solver is applied to the master problem while a constraint programming solver is used for the subproblem. Paper C addresses the avionics scheduling problem and introduces a new acceleration technique for LBBD. This technique exploits information obtained during cut strengthening to make educated guesses about where feasible solutions might be found. With this technique, the LBBD algorithm outperforms the methods from Paper A and Paper B both with respect to solution time and RAM usage. Paper D investigates cut strengthening for LBBD in a wider context, by evaluating different cut-strengthening algorithms for LBBD on three problems from the literature. The computational evaluation shows that it is advantageous to invest time in finding strong cuts.
|
|
| 14. |
- Karlsson, Emil, 1990-, et al.
(författare)
-
Strengthening of feasibility cuts in logic-based Benders decomposition
- 2021
-
Ingår i: INTEGRATION OF CONSTRAINT PROGRAMMING, ARTIFICIAL INTELLIGENCE, AND OPERATIONS RESEARCH. - Cham : Springer. - 9783030782290 - 9783030782306 ; , s. 45-61
-
Konferensbidrag (refereegranskat)abstract
- As for any decomposition method, the computational performance of a logic-based Benders decomposition (LBBD) scheme relies on the quality of the feedback information. Therefore, an important acceleration technique in LBBD is to strengthen feasibility cuts by reducing their sizes. This is typically done by solving additional subproblems to evaluate potential cuts. In this paper, we study three cut-strengthening algorithms that differ in the computational efforts made to find stronger cuts and in the guarantees with respect to the strengths of the cuts. We give a unified description of these algorithms and present a computational evaluation of their impact on the efficiency of a LBBD scheme. This evaluation is made for three different problem formulations, using over 2000 instances from five different applications. Our results show that it is usually beneficial to invest the time needed to obtain irreducible cuts. In particular, the use of the depth-first binary search cut-strengthening algorithm gives a good performance. Another observation is that when the subproblem can be separated into small independent problems, the impact of cut strengthening is dominated by that of the separation, which has an automatic strengthening effect.
|
|
| 15. |
- Lindh, Emil, et al.
(författare)
-
Scheduling of an underground mine by combining logic-based Benders decomposition and a priority-based heuristic
- 2022
-
Ingår i: Proceedings of the 13th International Conference on the Practice and Theory of Automated Timetabling - PATAT 2022.
-
Konferensbidrag (refereegranskat)abstract
- Underground mining is a complex operation that requires careful planning. The short-term scheduling, which is the scheduling of the tasks involved in the excavation process, is an important part of the planning process. In this paper, we propose a new method for the short-term scheduling of cut-and-fill mines.Our problem formulation includes a new aspect of the problem, which is to handle that different excavation locations of the mine can have different priorities. The inclusion of this aspect allows the user to control the output of the scheduling and to direct resources to the locations where they are most needed according to the long-term plans. Our solution method consists of two components: a priority-based heuristic that constructs a complete solution by iteratively solving partial scheduling problems containing subsets of tasks, and a logic-based Benders decomposition scheme for solving these partial problems.The computational performance of the proposed method is evaluated on industrially relevant large-scale instances generated from data provided by the mining company Boliden. Comparisons are made both with applying a constraint programming solver instead of the logic-based Benders decomposition scheme and with applying a constraint programming solver directly on the complete problem. The results show that our method outperforms the other two methods and yields schedules with a shorter makespan. The used instances are made publicly available to support further research in this area.
|
|
| 16. |
- Maher, Stephen J., et al.
(författare)
-
Integer programming column generation: accelerating branch-and-price using a novel pricing scheme for finding high-quality solutions in set covering, packing, and partitioning problems
- 2023
-
Ingår i: Mathematical Programming Computation. - : SPRINGER HEIDELBERG. - 1867-2949 .- 1867-2957. ; 15, s. 509-548
-
Tidskriftsartikel (refereegranskat)abstract
- Large-neighbourhood search (LNS) heuristics are important mathematical programming techniques that search for primal feasible solutions by solving an auxiliary problem with a restricted feasible region. Extending such powerful generic LNS heuristics to the branch-and-price context is inherently challenging. The most prominent challenges arise from the fact that in branch-and-price algorithms, columns are generated with the sole aim to solve linear programming relaxations. Hence, the ability to form integer feasible solutions is not considered during the generation of columns. Without any changes to the standard pricing schemes, the potential of deploying generic LNS heuristics within a branch-and-price procedure is severely limited. This paper proposes a matheuristic, based on an LNS heuristic framework, where the novelty is a customised pricing scheme for generating columns to solve an auxiliary problem. The theoretical foundation for this pricing scheme is a set of optimality conditions for integer programs. From this foundation, a column generation strategy is developed for finding columns that are likely to be of use in high-quality primal feasible solutions for the original problem. The proposed matheuristic is implemented in the generic branch-price-and-cut solver GCG. On a broad test set comprising classical block diagonal structured instances and general instances from the MIPLIB 2017 Collection, the computational results show a significant improvement to the solving performance of GCG.
|
|
| 17. |
- Mayambala, Fred, 1985-, et al.
(författare)
-
Eigendecomposition of the mean-variance portfolio optimization model
- 2015
-
Ingår i: Optimization, control, and applications in the information age. - Cham : Springer. - 9783319185668 - 9783319185675 ; , s. 209-232
-
Bokkapitel (refereegranskat)abstract
- We provide new insights into the mean-variance portfolio optimization problem, based on performing eigendecomposition of the covariance matrix. The result of this decomposition can be given an interpretation in terms of uncorrelated eigenportfolios. When only some of the eigenvalues and eigenvectors are used, the resulting mean-variance problem is an approximation of the original one. A solution to the approximation yields lower and upper bounds on the original mean-variance problem; these bounds are tight if sufficiently many eigenvalues and eigenvectors are used in the approximation. Even tighter bounds are obtained through the use of a linearized error term of the unused eigenvalues and eigenvectors.We provide theoretical results for the upper bounding quality of the approximate problem and the cardinality of the portfolio obtained, and also numerical illustrations of these results. Finally, we propose an ad hoc linear transformation of the mean-variance problem, which in practice significantly strengthens the bounds obtained from the approximate mean-variance problem.
|
|
| 18. |
- Oberweger, Fabio F., et al.
(författare)
-
A Learning Large Neighborhood Search for the Staff Rerostering Problem
- 2022
-
Ingår i: Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2022. - Cham : Springer International Publishing. - 9783031080104 - 9783031080111 ; , s. 300-317
-
Konferensbidrag (refereegranskat)abstract
- To effectively solve challenging staff rerostering problems, we propose to enhance a large neighborhood search (LNS) with a machine learning guided destroy operator. This operator uses a conditional generative model to identify variables that are promising to select and combines this with the use of a special sampling strategy to make the actual selection. Our model is based on a graph neural network (GNN) and takes a problem-specific graph representation as input. Imitation learning is applied to mimic a time-expensive approach that solves a mixed-integer program (MIP) for finding an optimal destroy set in each iteration. An additional GNN is employed to predict a suitable temperature for the destroy set sampling process. The repair operator is realized by solving a MIP. Our learning LNS outperforms directly solving a MIP with Gurobi and yields improvements compared to a well-performing LNS with a manually designed destroy operator, also when generalizing to schedules with various numbers of employees.
|
|
| 19. |
|
|
| 20. |
- Rönnberg, Elina, 1981-, et al.
(författare)
-
All-integer column generation: Basic principles and extensions
- 2014
-
Ingår i: European Journal of Operational Research. - : Elsevier. - 0377-2217 .- 1872-6860. ; 233:3, s. 529-538
-
Tidskriftsartikel (refereegranskat)abstract
- Column generation is a linear programming method in which a dual solution of the master problem is essential when deriving new columns by solving a subproblem. When combined with appropriate integer programming techniques, column generation has successfully been used for solving huge integer programs. In many applications where column generation is used, the master problem is of a set partitioning type.The set partitioning polytope has the quasi-integrality property, which enables the use of simplex pivot based methods for finding improved integer solutions where each integer solution is associated with a linear programming basis a corresponding dual solution. By combining these kinds of simplex pivots with column generation, one obtains a method where each successively found solution to a restricted master problem is feasible, integer, and associated with a dual solution to be used in the column generation step. The column generation subproblem can either be of a regular type, or it can be tailored to produce columns that maintain integrality when pivoted into the basis.In this paper, a framework for this kind of column generation, which we here name all-integer column generation for set partitioning problems, is presented. The strategies proposed are primarily of a meta-heuristic nature, but with the proper settings, optimal or near-optimal solutions can be obtained.
|
|
| 21. |
- Rönnberg, Elina, 1981-, et al.
(författare)
-
An All-Integer Column Generation Methodology for Set Partitioning Problems
- 2008
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- The set partitioning polytope has the quasi-integrality propertythat enables the use of simplex pivot based methods for finding animproved integer solution, which thereby is associated with a linearprogramming basis and a corresponding dual solution. Presented in thispaper is a framework for an all-integer column generation methodologyfor set partitioning problems that utilises the quasi-integralityproperty of the feasible polytope.In the presented methodology, each successively found solution to arestricted master problem is feasible, integer and associated with acorresponding dual solution, which is then used in the columngeneration step. The column generation problem is tailored to producecolumns that maintain integrality when pivoted into the basis.Furthermore, criteria for verifying optimality are presented.
|
|
| 22. |
- Rönnberg, Elina, 1981-, et al.
(författare)
-
An integer optimality condition for column generation on zero-one linear programs
- 2019
-
Ingår i: Discrete Optimization. - : Elsevier. - 1572-5286 .- 1873-636X. ; 31, s. 79-92
-
Tidskriftsartikel (refereegranskat)abstract
- Column generation is a linear programming method that, when combined with appropriate integer programming techniques, has been successfully used for solving huge integer programs. The method alternates between a restricted master problem and a column generation subproblem. The latter step is founded on dual information from the former one; often an optimal dual solution to the linear programming relaxation of the restricted master problem is used.We consider a zero–one linear programming problem that is approached by column generation and present a generic sufficient optimality condition for the restricted master problem to contain the columns required to find an integer optimal solution to the complete problem. The condition is based on dual information, but not necessarily on an optimal dual solution. It is however most natural to apply the condition in a situation when an optimal or near-optimal dual solution is at hand.We relate our result to a few special cases from the literature, and make some suggestions regarding possible exploitation of the optimality condition in the construction of column generation methods for integer programs.
|
|
| 23. |
- Rönnberg, Elina, 1981-, et al.
(författare)
-
Automatic scheduling of nurses : What does it take in practice?
- 2013
-
Ingår i: Systems Analysis Tools for Better Healthcare Delivery. - New York, NY : Springer Science+Business Media B.V.. - 9781461450931 - 9781461450948 ; , s. 151-178
-
Bokkapitel (refereegranskat)abstract
- This book presents some recent systems engineering and mathematical tools for health care along with their real-world applications by health care practitioners and engineers. Advanced approaches, tools, and algorithms used in operating room scheduling and patient flow are covered. State-of-the-art results from applications of data mining, business process modeling, and simulation in healthcare, together with optimization methods, form the core of the volume. Systems Analysis Tools for Better Health Care Delivery illustrates the increased need of partnership between engineers and health care professionals. This book will benefit researchers and practitioners in health care delivery institutions, staff members and professionals of specialized hospital units, and lecturers and graduate students in engineering, applied mathematics, business administration and health care.
|
|
| 24. |
- Rönnberg, Elina, 1981-, et al.
(författare)
-
Automating the Self-Scheduling Process of Nurses in Swedish Healthcare : A Pilot Study
- 2008
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Hospital wards need to be staffed by nurses round the clock, resultingin irregular working hours for many nurses. Over the years, thenurses' influence on the scheduling have been increased in order toimprove their working conditions. In Sweden it is common to apply a kindof self-scheduling where each nurse individually proposes a schedule,and then the final schedule is determined through informalnegotiations between the nurses. This kind of self-scheduling is verytime-consuming and does often lead to conflicts.We present a pilot study which aims at determining if it is possibleto create an optimisation tool that automatically delivers a usableschedule based on the schedules proposed by the nurses. The study isperformed at a typical Swedish nursing ward, for which we havedeveloped a mathematical model and delivered schedules. The results ofthis study are very promising.
|
|
| 25. |
- Rönnberg, Elina, 1981-
(författare)
-
Co-allocation of communication messages in an integrated modular avionic system
- 2017
-
Ingår i: Operations Research Proceedings 2017.. - Cham : Springer. - 9783319899206 - 9783319899190 ; , s. 459-465
-
Konferensbidrag (refereegranskat)abstract
- Pre-runtime scheduling of the kind of Integrated Modular Avionic (IMA) system addressed in this paper can be considered as multiprocessor scheduling with additional constraints on precedence relations between tasks and the concurrent scheduling of a communication network with discrete time slots for sending messages. This paper extends an existing constraint generation procedure for such IMA-systems to facilitate co-allocation of messages in the time slots. To send a communication message involves the execution of a set of tasks. Co-allocation of messages means that tasks of the same type that originate from these messages are merged and their total execution requirements are shortened. The reduction of the execution requirements induces capacity savings that can have a positive impact on the feasibility of the problem.
|
|
| 26. |
- Rönnberg, Elina, 1981-, et al.
(författare)
-
Column Generation in the Integral Simplex Method
- 2009
-
Ingår i: European Journal of Operational Research. - : Elsevier. - 0377-2217 .- 1872-6860. ; 192:1, s. 333-342
-
Tidskriftsartikel (refereegranskat)abstract
- The integral simplex method for set partitioning problems allows onlypivots-on-one to be made, which results in a primal all-integer method. Inthis technical note we outline how to tailor the column generationprinciple to this method. Because of the restriction topivots-on-one, only local optimality can be guaranteed, and to ensureglobal optimality we consider the use of implicit enumeration.
|
|
| 27. |
- Rönnberg, Elina, 1981-, et al.
(författare)
-
Column generation using non-optimal dual solutions: Optimality conditions and over-generation
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- Column generation is a linear programming method that, when combined with appropriate integer programming techniques, has been successfully used for solving huge integer programs. The use of a dual solution to the restricted master problem is essential when new columns are derived by solving a subproblem. Even if the problem to be solved is an integer programming one, this dual solution is usually optimal with respect to the linear programming relaxation of either the original problem or of a restriction thereof formed further down a branch-and-price-tree. This paper addresses the situation that arises when columns of a binary problem are generated using any dual solution, and we derive optimality conditions for determining when the master problem has been augmented with enough columns to contain an integer optimal solution to the complete master problem. We discuss the concept of over-generation of columns, which means to augment the restricted master problem with a set of columns, to ensure progress of the algorithm and also to make sure that the columns of the restricted master problem eventually comply with the optimality conditions. To illustrate the over-generation strategy, we compare our results with special cases that are already known from the literature, and we make some new suggestions.
|
|
| 28. |
- Rönnberg, Elina, 1981-
(författare)
-
Contributions within two topics in integer programming : nurse scheduling and column generation
- 2012
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Integer programming can be used to provide solutions to complex decision and planning problems occurring in a wide variety of situations. The application of integer programming to solve real world problems requires a modelling phase in which the problem at hand is translated into a mathematical description of the problem, and a solution phase that aims at developing methods for producing solutions to the mathematical formulation of the problem.The first two papers of this thesis have their focus on the modelling phase, and the application of integer programming for solving nurse scheduling problems. Common to both papers is that the research has been conducted in collaboration with health care representatives, and that the models presented can be used for providing schedules that can be used by nurses. In the latter paper, a meta-heuristic approach is suggested for providing the schedules.The last three papers address method development and specifically the design of column generation methods. The first of these papers presents optimality conditions that are useful in methods where columns are generated using dual solutions that are not necessarily optimal with respect to a linear programming relaxation, and the usefulness of these conditions are illustrated by examples from the literature.Many applications of column generation yield master problems of a set partitioning type, and the fourth and fifth paper present methodologies for solving such problems. The characteristics of these methodologies are that all solutions derived are feasible and integral, where the preservation of integrality is a major distinction from other column generation methods presented in the literature.
|
|
| 29. |
- Rönnberg, Elina, 1981-, et al.
(författare)
-
Integral Simplex Methods for the Set Partitioning Problem : Globalisation and Anti-Cycling
- 2018
-
Ingår i: Open Problems in Optimization and Data Analysis. - Cham : Springer. - 9783319991412 - 9783319991429 ; , s. 285-303
-
Bokkapitel (refereegranskat)abstract
- The set partitioning problem is a generic optimisation model with many applications, especially within scheduling and routing. It is common in the context of column generation, and its importance has grown due to the strong developments in this field. The set partitioning problem has the quasi-integrality property, which means that every edge of the convex hull of the integer feasible solutions is also an edge of the polytope of the linear programming relaxation. This property enables, in principle, the use of solution methods that find improved integer solutions through simplex pivots that preserve integrality; pivoting rules with this effect can be designed in a few different ways. Although seemingly promising, the application of these approaches involves inherent challenges. Firstly, they can get be trapped at local optima, with respect to the pivoting options available, so that global optimality can be guaranteed only by resorting to an enumeration principle. Secondly, set partitioning problems are typically massively degenerate and a big hurdle to overcome is therefore to establish anti-cycling rules for the pivoting options available. The purpose of this chapter is to lay a foundation for research on these topics.
|
|
| 30. |
- Rönnberg, Elina, 1981-
(författare)
-
Methods and Applications in Integer Programming : All-Integer Column Generation and Nurse Scheduling
- 2008
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Integer programming can be used to provide solutionsto complex decision and planning problems occurring in a wide varietyof situations. Applying integer programming to a real life problembasically involves a first phase where a mathematical model isconstructed, and a second phase where the problem described by themodel is solved. While the nature of the challenges involved in therespective two phases differ, the strong relationship between theproperties of models, and which methods that are appropriate for theirsolution, links the two phases. This thesis constitutes of threepapers, of which the third one considers the modeling phase, while thefirst and second one consider the solution phase. Many applications of column generation yield master problems of setpartitioning type, and the first and second papers presentmethodologies for solving such problems. The characteristics of themethodologies presented are that all successively found solutions arefeasible and integral, where the retention of integrality is a majordistinction from other column generation methods presented in theliterature. The third paper concerns nurse scheduling and describes the results ofa pilot implementation of a scheduling tool at a Swedish nursing ward.This paper focuses on the practical aspects of modeling and thechallenges of providing a solution to a complex real life problem.
|
|
| 31. |
|
|
| 32. |
- Varga, Johannes, et al.
(författare)
-
Interactive Job Scheduling with Partially Known Personnel Availabilities
- 2023
-
Ingår i: Optimization and Learning. - : Springer. - 9783031340192 - 9783031340208
-
Konferensbidrag (refereegranskat)abstract
- When solving a job scheduling problem that involves humans, the times in which they are available must be taken into account. For practical acceptance of a scheduling tool, it is further crucial that the interaction with the humans is kept simple and to a minimum. Requiring users to fully specify their availability times is typically not reasonable. We consider a scenario in which initially users only suggest single starting times for their jobs and an optimized schedule shall then be found within a small number of interaction rounds. In each round users may only be suggested a small set of alternative time intervals, which are accepted or rejected. To make the best out of these limited interaction possibilities, we propose an approach that utilizes integer linear programming and a theoretically derived probability calculation for the users’ availabilities based on a Markov model. Educated suggestions of alternative time intervals for performing jobs are determined from these acceptance probabilities as well as the optimization’s current state. The approach is experimentally evaluated and compared to diverse baselines. Results show that an initial schedule can be quickly improved over few interaction rounds, and the final schedule may come close to the solution of the full-knowledge case despite the limited interaction.
|
|
| 33. |
- Varga, Johannes, et al.
(författare)
-
Scheduling jobs using queries to interactively learn human availability times
- 2024
-
Ingår i: Computers & Operations Research. - : Elsevier. - 0305-0548 .- 1873-765X. ; 167
-
Tidskriftsartikel (refereegranskat)abstract
- The solution to a job scheduling problem that involves humans as well some other shared resource has to consider the humans’ availability times. For practical acceptance of a scheduling tool, it is crucial that the interaction with the humans is kept simple and to a minimum. It is rarely practical to ask users to fully specify their availability times or to let them enumerate all possible starting times for their jobs. In the scenario we are considering, users initially only propose a single starting time for each of their jobs and a feasible and optimized schedule shall then be found within a small number of interaction rounds. In each such interaction round, our scheduling approach may propose each user a small number of alternative time intervals for scheduling the user’s jobs, and then the user may accept or reject these. To make the best out of these limited interaction possibilities, we propose an approach that utilizes integer linear programming and an exact and computationally efficient probability calculation for the users’ availabilities assuming two different stochastic models. In this way, educated proposals of alternative time intervals for performing the jobs are determined based on the computed availability probabilities and the improvements these time intervals would enable. The approach is experimentally evaluated on a variety of artificial benchmark scenarios, and different variants are compared with each other and to diverse baselines. Results show that an initial schedule can usually be quickly improved over few interaction rounds even when assuming a quite simple stochastic model, and the final schedule may come close to the solution of the full-knowledge case despite the strongly limited interaction.
|
|
| 34. |
- Varga, Johannes, et al.
(författare)
-
Speeding Up Logic-Based Benders Decomposition by Strengthening Cuts with Graph Neural Networks
- 2023
-
Ingår i: Machine Learning, Optimization, and Data Science. - Cham. - 9783031539688 - 9783031539695 ; , s. 24-38
-
Konferensbidrag (refereegranskat)abstract
- Logic-based Benders decomposition is a technique to solve optimization problems to optimality. It works by splitting the problem into a master problem, which neglects some aspects of the problem, and a subproblem, which is used to iteratively produce cuts for the master problem to account for those aspects. It is critical for the computational performance that these cuts are strengthened, but the strengthening of cuts comes at the cost of solving additional subproblems. In this work we apply a graph neural network in an autoregressive fashion to approximate the compilation of an irreducible cut, which then only requires few postprocessing steps to ensure its validity. We test the approach on a job scheduling problem with a single machine and multiple time windows per job and compare to approaches from the literature. Results show that our approach is capable of considerably reducing the number of subproblems that need to be solved and hence the total computational effort.
|
|
| 35. |
|
|
| 36. |
- Zhao, Yixin, et al.
(författare)
-
An integer programming column generation principlefor heuristic search methods
- 2020
-
Ingår i: International Transactions in Operational Research. - : Wiley-Blackwell. - 0969-6016 .- 1475-3995. ; 27:1, s. 665-695
-
Tidskriftsartikel (refereegranskat)abstract
- There is an increasing interest in integrating column generation and heuristic approaches to efficiently solve large-scale discrete optimisation problems. We contribute in this direction. Based on the insights from Lagrangian duality theory, we present an auxiliary problem that can be used for finding near-optimal solutions to a discrete column-oriented model. The structure of this auxiliary problem makes it suitable for being addressed with a heuristic search method involving column generation. To this end, we suggest a large neighbourhood search strategy where the repair step is to solve a column generation type subproblem. The suggested search strategy and mathematical models involved need to be tailored to the problem structure. To illustrate important design options and computational behaviour, four applications are studied: bin packing, generalised assignment, a resource allocation problem and the fixed-charge transportation problem.
|
|
| 37. |
- Zhao, Yixin, et al.
(författare)
-
The fixed charge transportation problem: a strong formulation based on Lagrangian decomposition and column generation
- 2018
-
Ingår i: Journal of Global Optimization. - : Springer Publishing Company. - 0925-5001 .- 1573-2916. ; 72:3, s. 517-538
-
Tidskriftsartikel (refereegranskat)abstract
- A new and strong convexified formulation of the fixed charge transportation problem is provided. This formulation is obtained by integrating the concepts of Lagrangian decomposition and column generation. The decomposition is made by splitting the shipping variables into supply and demand side copies, while the columns correspond to extreme flow patterns for single sources or sinks. It is shown that the combination of Lagrangian decomposition and column generation provides a formulation whose strength dominates those of three other convexified formulations of the problem. Numerical results illustrate that our integrated approach has the ability to provide strong lower bounds. The Lagrangian decomposition yields a dual problem with an unbounded set of optimal solutions. We propose a regularized column generation scheme which prioritizes an optimal dual solution with a small 1-norm. We further demonstrate numerically that information gained from the strong formulation can also be used for constructing a small-sized core problem which yields high-quality upper bounds.
|
|
