liu.seSök publikationer i DiVA
Ändra sökning
Avgränsa sökresultatet
1 - 29 av 29
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Träffar per sida
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sortering
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
Markera
Maxantalet träffar du kan exportera från sökgränssnittet är 250. Vid större uttag använd dig av utsökningar.
  • 1.
    Amankwah, Henry
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Textorius, Björn
    Linköpings universitet, Matematiska institutionen, Tillämpad matematik. Linköpings universitet, Tekniska högskolan.
    Rönnberg, Elina
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Open-Pit Production Scheduling - Suggestions for Lagrangian Dual Heuristic and Time Aggregation ApproachesManuskript (preprint) (Övrigt vetenskapligt)
    Abstract [en]

    Open-pit production scheduling deals with the problem of deciding what and when to mine from an open-pit, given potential profits of the different fractions of the mining volume, pit-slope restrictions, and mining capacity restrictions for successive time periods. We give suggestions for Lagrangian dual heuristic approaches for the open-pit production scheduling problem. First, the case with a single mining capacity restriction per time period is considered. For this case, linear programming relaxations are solved to find values of the multipliers for the capacity restrictions, to be used in a Lagrangian relaxation of the constraints. The solution to the relaxed problem will not in general satisfy the capacity restrictions, but can be made feasible by adjusting the multiplier values for one time period at a time. Further, a time aggregation approach is suggested as a way of reducing the computational burden of solving linear programming relaxations, especially for largescale real-life mine problems. For the case with multiple capacity restrictions per time period we apply newly developed conditions for optimality and nearoptimality in general discrete optimization problems to construct a procedure for heuristically constructing near-optimal intermediate pits.

  • 2.
    Blikstad, Mathias
    et al.
    Saab AB, Sweden.
    Karlsson, Emil
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Lööw, Tomas
    Saab AB, Sweden.
    Rönnberg, Elina
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    A constraint generation procedure for pre-runtime scheduling of integrated modular avionic systems2017Ingår i: Proceedings of the 13th Workshop on Models and Algorithms for Planning and Scheduling Problems / [ed] Susanne Albers, Nicole Megow, Andreas S. Schulz, Leen Stougie, 2017Konferensbidrag (Övrigt vetenskapligt)
    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 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.

  • 3.
    Blikstad, Mathias
    et al.
    Saab AB, Sweden.
    Karlsson, Emil
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Lööw, Tomas
    Saab AB, Sweden.
    Rönnberg, Elina
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    An Optimisation Approach for Pre-Runtime Scheduling of Tasks and Communication in an Integrated Modular Avionic System2017Rapport (Övrigt vetenskapligt)
    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 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.

  • 4.
    Blikstad, Mathias
    et al.
    Saab AB, Linköping, Sweden.
    Karlsson, Emil
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten. Saab AB, Linköping, Sweden.
    Lööw, Tomas
    Saab AB, Linköping, Sweden.
    Rönnberg, Elina
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten. Saab AB, Linköping, Sweden.
    An optimisation approach for pre-runtime scheduling of tasks and communication in an integrated modular avionic system2018Ingår i: Optimization and Engineering, ISSN 1389-4420, E-ISSN 1573-2924, Vol. 19, nr 4, s. 977-1004Artikel i tidskrift (Refereegranskat)
    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.

  • 5.
    Horn, Matthias
    et al.
    Institute of Logic and Computation, TU Wien.
    Raidl, Günther R.
    Institute of Logic and Computation, TU Wien.
    Rönnberg, Elina
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    An A* Algorithm for Solving a Prize-Collecting Sequencing Problem with One Common and Multiple Secondary Resources and Time Windows2018Ingår i: 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, s. 235-256Konferensbidrag (Refereegranskat)
  • 6.
    Karlsson, Emil
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten. Saab AB, Linköping, Sweden.
    Rönnberg, Elina
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten. Saab AB, Linköping, Sweden.
    Explicit modelling of multiple intervals in a constraint generation procedure for multiprocessor scheduling2017Ingår i: Operations Research Proceedings 2017 / [ed] N. Kliewer, J.F. Ehmke and R. Borndörfer, Springer, 2017, s. 567-572Konferensbidrag (Refereegranskat)
    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.

  • 7.
    Karlsson, Emil
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten. Saab AB, SE-581 88 Linköping.
    Rönnberg, Elina
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten. Saab AB, SE-581 88 Linköping.
    Stenberg, Andreas
    Saab AB, SE-581 88 Linköping.
    Uppman, Hannes
    Saab AB, SE-581 88 Linköping.
    A matheuristic approach to large-scale avionic scheduling2019Rapport (Övrigt vetenskapligt)
    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.

  • 8.
    Karlsson, Emil
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Rönnberg, Elina
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Stenberg, Andreas
    Saab AB, Sweden.
    Uppman, Hannes
    Saab AB, Sweden.
    Heuristic enhancements of a constraint generation procedure for scheduling of avionic systems2018Ingår i: 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, s. 417-419Konferensbidrag (Refereegranskat)
  • 9.
    Mayambala, Fred
    et al.
    Department of Mathematics, Makerere University, Kampala, Uganda.
    Rönnberg, Elina
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Eigendecomposition of the mean-variance portfolio optimization model2015Ingår i: Optimization, control, and applications in the information age / [ed] Athanasios Migdalas and Athanasia Karakitsiou, Springer, 2015, s. 209-232Kapitel i bok, del av antologi (Refereegranskat)
    Abstract [en]

    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.

  • 10.
    Mayambala, Fred
    et al.
    Department of Mathematics, Makerere University, Kampala, Uganda.
    Rönnberg, Elina
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Tight Upper Bounds on the Cardinality Constrained Mean-Variance Portfolio Optimization Problem Using Truncated Eigendecomposition2016Ingår i: Operations Research Proceedings 2014: Selected Papers of the Annual International Conference of the German Operations Research Society (GOR), RWTH Aachen University, Germany, September 2-5, 2014 / [ed] Marco Lübbecke, Arie Koster, Peter Letmathe, Reinhard Madlener, Britta Peis and Grit Walther, Springer, 2016, s. 385-392Konferensbidrag (Refereegranskat)
    Abstract [en]

    The mean-variance problem introduced by Markowitz in 1952 is a fundamental model in portfolio optimization up to date. When cardinality and bound constraints are included, the problem becomes NP-hard and the existing optimizing solution methods for this problem take a large amount of time.

    We introduce a core problem based method for obtaining upper bounds to the meanvariance portfolio optimization problem with cardinality and bound constraints. The method involves performing eigendecomposition on the covariance matrix and then using only few of the eigenvalues and eigenvectors to obtain an approximation of the original problem. A solution of this approximate problem has a relatively low cardinality and is used to construct a core problem. When solved, the core problem provides an upper bound. We test the method on large scale problems of up to 1000 assets. The obtained upper bounds are of high quality and the time required to obtain them is much less than what state-of-the-art mixed integer softwares use, which makes it practically useful.

  • 11.
    Raidl, Günther R.
    et al.
    Institute of Logic and Computation, TU Wien.
    Rönnberg, Elina
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Horn, Matthias
    Institute of Logic and Computation, TU Wien.
    Maschler, Johannes
    Institute of Logic and Computation, TU Wien.
    An A*-Based Algorithm to Derive Relaxed Decision Diagrams for a Prize-Collecting Sequencing Problem2018Konferensbidrag (Refereegranskat)
  • 12.
    Rönnberg, Elina
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten. Saab AB, Linköping, Sweden.
    Co-allocation of communication messages in an integrated modular avionic system2017Ingår i: Operations Research Proceedings 2017. / [ed] N. Kliewer, J.F. Ehmke, and R. Borndörfer, 2017, s. 459-465Konferensbidrag (Refereegranskat)
    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.

  • 13.
    Rönnberg, Elina
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Contributions within two topics in integer programming: nurse scheduling and column generation2012Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
    Abstract [en]

    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.

    Delarbeten
    1. Automating the self-scheduling process of nurses in Swedish healthcare: a pilot study
    Öppna denna publikation i ny flik eller fönster >>Automating the self-scheduling process of nurses in Swedish healthcare: a pilot study
    2010 (Engelska)Ingår i: HEALTH CARE MANAGEMENT SCIENCE, ISSN 1386-9620, Vol. 13, nr 1, s. 35-53Artikel i tidskrift (Refereegranskat) Published
    Abstract [en]

    Hospital wards need to be staffed by nurses round the clock, resulting in irregular working hours for many nurses. Over the years, the nurses influence on the scheduling has been increased in order to improve their working conditions. In Sweden it is common to apply a kind of self-scheduling where each nurse individually proposes a schedule, and then the final schedule is determined through informal negotiations between the nurses. This kind of self-scheduling is very time-consuming and does often lead to conflicts. We present a pilot study which aims at determining if it is possible to create an optimisation tool that automatically delivers a usable schedule based on the schedules proposed by the nurses. The study is performed at a typical Swedish nursing ward, for which we have developed a mathematical model and delivered schedules. The results of this study are very promising and suggest continued work along these lines.

    Ort, förlag, år, upplaga, sidor
    Springer Science Business Media, 2010
    Nyckelord
    Nurse scheduling, Nurse rostering, Self-scheduling, Preference scheduling, Operations research, Integer linear programming
    Nationell ämneskategori
    Matematik
    Identifikatorer
    urn:nbn:se:liu:diva-59720 (URN)10.1007/s10729-009-9107-x (DOI)000281585200004 ()
    Anmärkning
    The original publication is available at www.springerlink.com: Elina Rönnberg and Torbjörn Larsson, Automating the self-scheduling process of nurses in Swedish healthcare: a pilot study, 2010, HEALTH CARE MANAGEMENT SCIENCE, (13), 1, 35-53. http://dx.doi.org/10.1007/s10729-009-9107-x Copyright: Springer Science Business Media http://www.springerlink.com/ Tillgänglig från: 2010-09-24 Skapad: 2010-09-24 Senast uppdaterad: 2018-06-25
    2. Automatic scheduling of nurses: What does it take in practice?
    Öppna denna publikation i ny flik eller fönster >>Automatic scheduling of nurses: What does it take in practice?
    2013 (Engelska)Ingår i: Systems Analysis Tools for Better Healthcare Delivery / [ed] Panos M. Pardalos, Pando G. Georgiev, Petraq Papajorgji, Britta Neugaard, New York, NY: Springer Science+Business Media B.V., 2013, s. 151-178Kapitel i bok, del av antologi (Refereegranskat)
    Abstract [en]

    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. 

    Ort, förlag, år, upplaga, sidor
    New York, NY: Springer Science+Business Media B.V., 2013
    Serie
    Springer Optimization and Its Applications, ISSN 1931-6828 ; 74
    Nyckelord
    Mathematics, Practice of medicine, Mathematical optimization, Optimization, Operations Research, Management Science, Health Administration, Mathematical Modeling and Industrial Mathematics, Mathematical Modeling and Industrial Mathematics, Medical care, Hospital care, Matematiska modeller, Hälso- och sjukvård
    Nationell ämneskategori
    Beräkningsmatematik
    Identifikatorer
    urn:nbn:se:liu:diva-76079 (URN)10.1007/978-1-4614-5094-8_8 (DOI)978-1-4614-5093-1 (ISBN)978-1-4614-5094-8 (ISBN)
    Tillgänglig från: 2012-03-26 Skapad: 2012-03-26 Senast uppdaterad: 2018-06-25Bibliografiskt granskad
    3. Column generation using non-optimal dual solutions: Optimality conditions and over-generation
    Öppna denna publikation i ny flik eller fönster >>Column generation using non-optimal dual solutions: Optimality conditions and over-generation
    (Engelska)Manuskript (preprint) (Övrigt vetenskapligt)
    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 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.

    Nyckelord
    Binary program, column generation, optimality conditions, overgeneration
    Nationell ämneskategori
    Beräkningsmatematik
    Identifikatorer
    urn:nbn:se:liu:diva-76090 (URN)
    Tillgänglig från: 2012-03-26 Skapad: 2012-03-26 Senast uppdaterad: 2018-06-25Bibliografiskt granskad
    4. Column Generation in the Integral Simplex Method
    Öppna denna publikation i ny flik eller fönster >>Column Generation in the Integral Simplex Method
    2009 (Engelska)Ingår i: European Journal of Operational Research, ISSN 0377-2217, E-ISSN 1872-6860, Vol. 192, nr 1, s. 333-342Artikel i tidskrift (Refereegranskat) Published
    Abstract [en]

    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.

    Ort, förlag, år, upplaga, sidor
    Elsevier, 2009
    Nyckelord
    integer programming, set partitioning, column generation, quasi-integrality
    Nationell ämneskategori
    Beräkningsmatematik
    Identifikatorer
    urn:nbn:se:liu:diva-15287 (URN)10.1016/j.ejor.2007.09.037 (DOI)
    Anmärkning
    Original publication: Elina Rönnberg and Torbjörn Larsson, Column Generation in the Integral Simplex Method, 2009, European Journal of Operational Research, (192), 1, 333-342. http://dx.doi.org/10.1016/j.ejor.2007.09.037. Copyright: Elsevier B.V., http://www.elsevier.com/Tillgänglig från: 2008-10-29 Skapad: 2008-10-29 Senast uppdaterad: 2018-06-25Bibliografiskt granskad
    5. All-integer column generation: Basic principles and extensions
    Öppna denna publikation i ny flik eller fönster >>All-integer column generation: Basic principles and extensions
    2014 (Engelska)Ingår i: European Journal of Operational Research, ISSN 0377-2217, E-ISSN 1872-6860, Vol. 233, nr 3, s. 529-538Artikel i tidskrift (Refereegranskat) Published
    Abstract [en]

    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.

    Ort, förlag, år, upplaga, sidor
    Elsevier, 2014
    Nyckelord
    Set partitioning, meta-heuristic, column generation, quasiintegrality, surrogate columns, over-generation, all-integer pivots
    Nationell ämneskategori
    Beräkningsmatematik
    Identifikatorer
    urn:nbn:se:liu:diva-76091 (URN)10.1016/j.ejor.2013.08.036 (DOI)000328180200006 ()urn:nbn:se:liu:diva-102966 (Lokalt ID)urn:nbn:se:liu:diva-102966 (Arkivnummer)urn:nbn:se:liu:diva-102966 (OAI)
    Anmärkning

    On the day of the defence date the status of this article was Manuscript with the title All-integer column generation: A meta-heuristic for set partitioning problems.

    Tillgänglig från: 2012-03-26 Skapad: 2012-03-26 Senast uppdaterad: 2018-06-25Bibliografiskt granskad
  • 14.
    Rönnberg, Elina
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Methods and Applications in Integer Programming: All-Integer Column Generation and Nurse Scheduling2008Licentiatavhandling, sammanläggning (Övrigt vetenskapligt)
    Abstract [en]

    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.

    Delarbeten
    1. Column Generation in the Integral Simplex Method
    Öppna denna publikation i ny flik eller fönster >>Column Generation in the Integral Simplex Method
    2009 (Engelska)Ingår i: European Journal of Operational Research, ISSN 0377-2217, E-ISSN 1872-6860, Vol. 192, nr 1, s. 333-342Artikel i tidskrift (Refereegranskat) Published
    Abstract [en]

    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.

    Ort, förlag, år, upplaga, sidor
    Elsevier, 2009
    Nyckelord
    integer programming, set partitioning, column generation, quasi-integrality
    Nationell ämneskategori
    Beräkningsmatematik
    Identifikatorer
    urn:nbn:se:liu:diva-15287 (URN)10.1016/j.ejor.2007.09.037 (DOI)
    Anmärkning
    Original publication: Elina Rönnberg and Torbjörn Larsson, Column Generation in the Integral Simplex Method, 2009, European Journal of Operational Research, (192), 1, 333-342. http://dx.doi.org/10.1016/j.ejor.2007.09.037. Copyright: Elsevier B.V., http://www.elsevier.com/Tillgänglig från: 2008-10-29 Skapad: 2008-10-29 Senast uppdaterad: 2018-06-25Bibliografiskt granskad
    2. An All-Integer Column Generation Methodology for Set Partitioning Problems
    Öppna denna publikation i ny flik eller fönster >>An All-Integer Column Generation Methodology for Set Partitioning Problems
    2008 (Engelska)Rapport (Övrigt vetenskapligt)
    Abstract [en]

    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.

    Förlag
    s. 23
    Serie
    Report / Department of Mathematics, Universitetet i Linköping, Tekniska högskolan, ISSN 0348-2960
    Nyckelord
    integer programming, column generation, quasi-integrality, surrogate columns, over-generation
    Nationell ämneskategori
    Beräkningsmatematik
    Identifikatorer
    urn:nbn:se:liu:diva-15256 (URN)
    Tillgänglig från: 2008-10-28 Skapad: 2008-10-27 Senast uppdaterad: 2018-06-25Bibliografiskt granskad
    3. Automating the Self-Scheduling Process of Nurses in Swedish Healthcare: A Pilot Study
    Öppna denna publikation i ny flik eller fönster >>Automating the Self-Scheduling Process of Nurses in Swedish Healthcare: A Pilot Study
    2008 (Engelska)Rapport (Övrigt vetenskapligt)
    Abstract [en]

    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.

    Förlag
    s. 29
    Serie
    LiTH-MAT-R, ISSN 0348-2960 ; 2008:8
    Nyckelord
    nurse scheduling, integer linear programming
    Nationell ämneskategori
    Beräkningsmatematik
    Identifikatorer
    urn:nbn:se:liu:diva-57562 (URN)
    Tillgänglig från: 2008-10-28 Skapad: 2008-10-27 Senast uppdaterad: 2018-06-25Bibliografiskt granskad
  • 15.
    Rönnberg, Elina
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    All-integer column generation: Basic principles and extensions2014Ingår i: European Journal of Operational Research, ISSN 0377-2217, E-ISSN 1872-6860, Vol. 233, nr 3, s. 529-538Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    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.

  • 16.
    Rönnberg, Elina
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    An All-Integer Column Generation Methodology for Set Partitioning Problems2008Rapport (Övrigt vetenskapligt)
    Abstract [en]

    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.

  • 17.
    Rönnberg, Elina
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    An integer optimality condition for column generation on zero-one linear programs2019Ingår i: Discrete Optimization, ISSN 1572-5286, E-ISSN 1873-636X, Vol. 31, s. 79-92Artikel i tidskrift (Refereegranskat)
    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.

    Publikationen är tillgänglig i fulltext från 2020-09-27 15:07
  • 18.
    Rönnberg, Elina
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Automating the Self-Scheduling Process of Nurses in Swedish Healthcare: A Pilot Study2008Rapport (Övrigt vetenskapligt)
    Abstract [en]

    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.

  • 19.
    Rönnberg, Elina
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Automating the self-scheduling process of nurses in Swedish healthcare: a pilot study2010Ingår i: HEALTH CARE MANAGEMENT SCIENCE, ISSN 1386-9620, Vol. 13, nr 1, s. 35-53Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Hospital wards need to be staffed by nurses round the clock, resulting in irregular working hours for many nurses. Over the years, the nurses influence on the scheduling has been increased in order to improve their working conditions. In Sweden it is common to apply a kind of self-scheduling where each nurse individually proposes a schedule, and then the final schedule is determined through informal negotiations between the nurses. This kind of self-scheduling is very time-consuming and does often lead to conflicts. We present a pilot study which aims at determining if it is possible to create an optimisation tool that automatically delivers a usable schedule based on the schedules proposed by the nurses. The study is performed at a typical Swedish nursing ward, for which we have developed a mathematical model and delivered schedules. The results of this study are very promising and suggest continued work along these lines.

  • 20.
    Rönnberg, Elina
    et al.
    Linköpings universitet, Matematiska institutionen. Linköpings universitet, Tekniska högskolan.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen. Linköpings universitet, Tekniska högskolan.
    Column Generation in the Integral Simplex Method2009Ingår i: European Journal of Operational Research, ISSN 0377-2217, E-ISSN 1872-6860, Vol. 192, nr 1, s. 333-342Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    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.

  • 21.
    Rönnberg, Elina
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Column generation using non-optimal dual solutions: Optimality conditions and over-generationManuskript (preprint) (Övrigt vetenskapligt)
    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 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.

  • 22.
    Rönnberg, Elina
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Integral Simplex Methods for the Set Partitioning Problem: Globalisation and Anti-Cycling2018Ingår i: Open Problems in Optimization and Data Analysis / [ed] Panos M. Pardalos, Athanasios Migdalas, Cham: Springer, 2018, s. 285-303Kapitel i bok, del av antologi (Refereegranskat)
    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.

  • 23.
    Rönnberg, Elina
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Bertilsson, Ann
    Linköpings universitet, Matematiska institutionen. Linköpings universitet, Tekniska högskolan.
    Automatic scheduling of nurses: What does it take in practice?2013Ingår i: Systems Analysis Tools for Better Healthcare Delivery / [ed] Panos M. Pardalos, Pando G. Georgiev, Petraq Papajorgji, Britta Neugaard, New York, NY: Springer Science+Business Media B.V., 2013, s. 151-178Kapitel i bok, del av antologi (Refereegranskat)
    Abstract [en]

    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.
    Zhao, Hongmei
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Lei, Lei
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska högskolan.
    Yuan, Di
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska högskolan.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Rönnberg, Elina
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Power efficient uplink scheduling in SC-FDMA: Bounding global optimality by column generation2013Ingår i: 2013 IEEE 18th International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD, IEEE , 2013, s. 119-123Konferensbidrag (Refereegranskat)
    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 (SC-FDMA) system with localized allocation of subcarriers, that is, the subcarriers allocated to a user equipment have to be consecutive in the frequency domain in each time slot. This problem is discrete and nonconvex, thus the use of suboptimal algorithms has been a common practice. We leverage the power of mathematical programming in order to approach global optimality or a tight bounding interval confining global optimum, to arrive at an effective scheme for gauging the performance of suboptimal algorithms. Toward this end, we first provide a straightforward integer linear programming formulation, and then an alternative and less trivial, so-called column-oriented, formulation. The latter is solved by column generation, which is a solution technique for large-scale optimization problems with certain characteristics. The computational evaluation demonstrates that the column generation method produces very highquality subcarrier allocations that either coincide with the global optimum or enable an extremely sharp bounding interval. Hence the approach serves well for the purpose of benchmarking results for large-scale instances of power efficient SC-FDMA scheduling.

  • 25.
    Zhao, Yixin
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Rönnberg, Elina
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    A Large Neighbourhood Search Principle for Column-Oriented Models: Theoretical Derivation and Example Applications2016Ingår i: Matheuristics 2016: Proceedings of the Sixth International Workshop on Model-based Metaheuristics / [ed] V. Maniezzo and T. Stutzle, Bruxelles, Belgium: IRIDIA , 2016Konferensbidrag (Refereegranskat)
  • 26.
    Zhao, Yixin
    et al.
    Nanjing University of Science and Technology, School of Automation.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Rönnberg, Elina
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    An integer programming column generation principlefor heuristic search methods2019Ingår i: International Transactions in Operational Research, ISSN 0969-6016, E-ISSN 1475-3995, Vol. 27, nr 1, s. 665-695Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    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.

  • 27.
    Zhao, Yixin
    et al.
    Nanjing University of Science and Technology, School of Automation.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Rönnberg, Elina
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Pardalos, Panos
    University of Florida, Department of Industrial and System Engineering.
    The fixed charge transportation problem: a strong formulation based on Lagrangian decomposition and column generation2018Ingår i: Journal of Global Optimization, ISSN 0925-5001, E-ISSN 1573-2916, Vol. 72, nr 3, s. 517-538Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    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.

  • 28.
    Zhao, Yixin
    et al.
    Nanjing Univ Sci and Technol, Peoples R China.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Yuan, Di
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Rönnberg, Elina
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Lei, Lei
    Linköpings universitet, Institutionen för teknik och naturvetenskap. Linköpings universitet, Tekniska fakulteten.
    Correction: Power efficient uplink scheduling in SC-FDMA: benchmarking by column generation (vol 17, pg 695, 2016)2019Ingår i: Optimization and Engineering, ISSN 1389-4420, E-ISSN 1573-2924, Vol. 20, nr 3, s. 959-959Artikel i tidskrift (Övrigt vetenskapligt)
    Abstract [en]

    At the time of the final publication of the paper, in December 2016, Yixin Zhaos affiliation had changed.

  • 29.
    Zhao, Yixin
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Larsson, Torbjörn
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Yuan, Di
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Rönnberg, Elina
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska fakulteten.
    Lei, Lei
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Power efficient uplink scheduling in SC-FDMA: benchmarking by column generation2016Ingår i: Optimization and Engineering, ISSN 1389-4420, E-ISSN 1573-2924, Vol. 17, nr 4, s. 695-725Artikel i tidskrift (Refereegranskat)
    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.

1 - 29 av 29
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf