liu.seSearch for publications in DiVA
Change search
Link to record
Permanent link

Direct link
BETA
Rönnberg, Elina
Publications (10 of 23) Show all publications
Karlsson, E., Rönnberg, E., Stenberg, A. & Uppman, H. (2019). A matheuristic approach to large-scale avionic scheduling. Linköping: Linköping University Electronic Press
Open this publication in new window or tab >>A matheuristic approach to large-scale avionic scheduling
2019 (English)Report (Other academic)
Abstract [en]

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.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2019. p. 40
Series
LiTH-MAT-R, ISSN 0348-2960 ; 2019:2
Keywords
Multiprocessor scheduling; avionic system; matheuristic; adaptive large neighbourhood search; integer programming; scheduling
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-157140 (URN)LiTH-MAT-R--2019/02--SE (ISRN)
Available from: 2019-05-29 Created: 2019-05-29 Last updated: 2019-05-29
Rönnberg, E. & Larsson, T. (2019). An integer optimality condition for column generation on zero-one linear programs. Discrete Optimization, 31, 79-92
Open this publication in new window or tab >>An integer optimality condition for column generation on zero-one linear programs
2019 (English)In: Discrete Optimization, ISSN 1572-5286, E-ISSN 1873-636X, Vol. 31, p. 79-92Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Elsevier, 2019
Keywords
Zero–one linear programming, Integer linear programming, Discrete optimisation, Column generation, Optimality conditions
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-151698 (URN)10.1016/j.disopt.2018.09.001 (DOI)000461538300006 ()2-s2.0-85053921680 (Scopus ID)
Funder
Swedish Research Council, 621- 2005-2874
Note

Funding agencies Swedish Research Council [621-2005-2874]

Available from: 2018-10-02 Created: 2018-10-02 Last updated: 2019-04-01Bibliographically approved
Horn, M., Raidl, G. R. & Rönnberg, E. (2018). An A* Algorithm for Solving a Prize-Collecting Sequencing Problem with One Common and Multiple Secondary Resources and Time Windows. In: E. K. Burke, L. Di Gaspero, B. McCollum, N. Musliu, E. Özcan (Ed.), PATAT 2018: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling: . Paper presented at 12th International Conference on the Practice and Theory of Automated Timetabling (pp. 235-256).
Open this publication in new window or tab >>An A* Algorithm for Solving a Prize-Collecting Sequencing Problem with One Common and Multiple Secondary Resources and Time Windows
2018 (English)In: PATAT 2018: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling / [ed] E. K. Burke, L. Di Gaspero, B. McCollum, N. Musliu, E. Özcan, 2018, p. 235-256Conference paper, Published paper (Refereed)
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-151910 (URN)978-0-9929984-2-4 (ISBN)
Conference
12th International Conference on the Practice and Theory of Automated Timetabling
Available from: 2018-10-09 Created: 2018-10-09 Last updated: 2018-10-30
Raidl, G. R., Rönnberg, E., Horn, M. & Maschler, J. (2018). An A*-Based Algorithm to Derive Relaxed Decision Diagrams for a Prize-Collecting Sequencing Problem. In: : . Paper presented at 15th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research.
Open this publication in new window or tab >>An A*-Based Algorithm to Derive Relaxed Decision Diagrams for a Prize-Collecting Sequencing Problem
2018 (English)Conference paper, Poster (with or without abstract) (Refereed)
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-151911 (URN)
Conference
15th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Available from: 2018-10-09 Created: 2018-10-09 Last updated: 2018-10-30
Blikstad, M., Karlsson, E., Lööw, T. & Rönnberg, E. (2018). An optimisation approach for pre-runtime scheduling of tasks and communication in an integrated modular avionic system. Optimization and Engineering, 19(4), 977-1004
Open this publication in new window or tab >>An optimisation approach for pre-runtime scheduling of tasks and communication in an integrated modular avionic system
2018 (English)In: Optimization and Engineering, ISSN 1389-4420, E-ISSN 1573-2924, Vol. 19, no 4, p. 977-1004Article in journal (Refereed) Published
Abstract [en]

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.

Keywords
Avionic system Scheduling Discrete optimisation Integer programming Multiprocessor scheduling Constraint generation
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-148854 (URN)10.1007/s11081-018-9385-6 (DOI)000447870700007 ()
Note

Funding agencies: Swedish Armed Forces; Swedish Defence Materiel Administration; Swedish Governmental Agency for Innovation Systems [NFFP6-2014-00917]; Center for Industrial Information Technology (CENIIT); Research School in Interdisciplinary Mathematics at Linkoping Univ

Available from: 2018-06-20 Created: 2018-06-20 Last updated: 2019-05-24
Karlsson, E., Rönnberg, E., Stenberg, A. & Uppman, H. (2018). Heuristic enhancements of a constraint generation procedure for scheduling of avionic systems. In: E. K. Burke, L. Di Gaspero, B. McCollum, N. Musliu, E. Özcan (Ed.), PATAT 2018: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling: . Paper presented at 12th International Conference on the Practice and Theory of Automated Timetabling (pp. 417-419).
Open this publication in new window or tab >>Heuristic enhancements of a constraint generation procedure for scheduling of avionic systems
2018 (English)In: PATAT 2018: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling / [ed] E. K. Burke, L. Di Gaspero, B. McCollum, N. Musliu, E. Özcan, 2018, p. 417-419Conference paper, Oral presentation with published abstract (Refereed)
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-151909 (URN)978-0-9929984-2-4 (ISBN)
Conference
12th International Conference on the Practice and Theory of Automated Timetabling
Available from: 2018-10-09 Created: 2018-10-09 Last updated: 2018-10-30
Rönnberg, E. & Larsson, T. (2018). Integral Simplex Methods for the Set Partitioning Problem: Globalisation and Anti-Cycling. In: Panos M. Pardalos, Athanasios Migdalas (Ed.), Open Problems in Optimization and Data Analysis: (pp. 285-303). Cham: Springer
Open this publication in new window or tab >>Integral Simplex Methods for the Set Partitioning Problem: Globalisation and Anti-Cycling
2018 (English)In: Open Problems in Optimization and Data Analysis / [ed] Panos M. Pardalos, Athanasios Migdalas, Cham: Springer, 2018, p. 285-303Chapter in book (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Cham: Springer, 2018
Series
Springer Optimization and Its Applications, ISSN 1931-6828, E-ISSN 1931-6836 ; 141
Keywords
Quasi-integrality, Set partitioning, Integral simplex method, Anti-cycling rules
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-153425 (URN)10.1007/978-3-319-99142-9_15 (DOI)9783319991412 (ISBN)9783319991429 (ISBN)
Available from: 2018-12-14 Created: 2018-12-14 Last updated: 2018-12-18Bibliographically approved
Rönnberg, E. (2017). Co-allocation of communication messages in an integrated modular avionic system. In: N. Kliewer, J.F. Ehmke, and R. Borndörfer (Ed.), Operations Research Proceedings 2017.: . Paper presented at Operations Research 2017 (OR2017), Freie Universität Berlin, Berlin, Germany, September 6-8, 2017 (pp. 459-465).
Open this publication in new window or tab >>Co-allocation of communication messages in an integrated modular avionic system
2017 (English)In: Operations Research Proceedings 2017. / [ed] N. Kliewer, J.F. Ehmke, and R. Borndörfer, 2017, p. 459-465Conference paper, Published paper (Refereed)
Abstract [en]

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.

Series
Operations Research Proceedings
Keywords
multiprocessor scheduling, avionic system
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-143037 (URN)10.1007/978-3-319-89920-6_61 (DOI)978-3-319-89920-6 (ISBN)978-3-319-89919-0 (ISBN)
Conference
Operations Research 2017 (OR2017), Freie Universität Berlin, Berlin, Germany, September 6-8, 2017
Available from: 2017-11-16 Created: 2017-11-16 Last updated: 2018-06-21Bibliographically approved
Karlsson, E. & Rönnberg, E. (2017). Explicit modelling of multiple intervals in a constraint generation procedure for multiprocessor scheduling. In: N. Kliewer, J.F. Ehmke and R. Borndörfer (Ed.), Operations Research Proceedings 2017: . Paper presented at Operations Research 2017, Freie Universität Berlin, Berlin, Germany, September 6-8, 2017 (pp. 567-572). Springer
Open this publication in new window or tab >>Explicit modelling of multiple intervals in a constraint generation procedure for multiprocessor scheduling
2017 (English)In: Operations Research Proceedings 2017 / [ed] N. Kliewer, J.F. Ehmke and R. Borndörfer, Springer, 2017, p. 567-572Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Springer, 2017
Series
Operations Research Proceedings, ISSN 0721-5924
Keywords
multiprocessor scheduling, multiple intervals, avionics scheduling and constraint generation
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-143021 (URN)10.1007/978-3-319-89920-6_75 (DOI)978-3-319-89919-0 (ISBN)978-3-319-89920-6 (ISBN)
Conference
Operations Research 2017, Freie Universität Berlin, Berlin, Germany, September 6-8, 2017
Available from: 2017-11-16 Created: 2017-11-16 Last updated: 2019-05-24Bibliographically approved
Zhao, Y., Larsson, T., Yuan, D., Rönnberg, E. & Lei, L. (2016). Power efficient uplink scheduling in SC-FDMA: benchmarking by column generation. Optimization and Engineering, 17(4), 695-725
Open this publication in new window or tab >>Power efficient uplink scheduling in SC-FDMA: benchmarking by column generation
Show others...
2016 (English)In: Optimization and Engineering, ISSN 1389-4420, E-ISSN 1573-2924, Vol. 17, no 4, p. 695-725Article in journal (Refereed) Published
Abstract [en]

We study resource allocation in cellular systems and consider the problem of finding a power efficient scheduling in an uplink single carrier frequency division multiple access system. Due to the discrete nature of this problem and its computational difficulty, particularly in a real-time setting, the use of suboptimal algorithms is common practice. We aim at an effective way of gauging the performance of suboptimal algorithms by finding tight bounds on the global optimum. Toward this end, we first provide a basic integer linear programming formulation. Then we propose a significantly stronger column-oriented formulation and a corresponding column generation method, as well as an enhanced column generation scheme. The latter extends the first scheme through the inclusion of a stabilization technique, an approximate column generation principle, and a tailored heuristic that is embedded in the column generation scheme to find high-quality though not necessarily global optimal solutions. The computational evaluation demonstrates that compared with a poor performance by the integer linear programming formulation, the column generation method can produce near-optimal schedules that enable a sharp bounding interval. The enhanced column generation method significantly sharpens the bounding interval. Hence the column generation approach serves well for the purpose of benchmarking results for large-scale instances.

Place, publisher, year, edition, pages
Springer-Verlag New York, 2016
Keywords
Localized SC-FDMA, Stabilized column generation, Power minimization, Integer linear programming, Uplink scheduling, Matheuristic
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-127355 (URN)10.1007/s11081-015-9304-z (DOI)000387857500004 ()
Note

Funding agencies: Research School in Interdisciplinary Mathematics at Linkoping University; Excellence Center at Linkoping - Lund in Information Technology, Centrum for Industriell Informationsteknologi, Linkoping University, EC FP7 Marie Curie Project [318992]; Chinese Sc

Available from: 2016-04-22 Created: 2016-04-22 Last updated: 2019-08-06Bibliographically approved
Organisations

Search in DiVA

Show all publications