liu.seSearch for publications in DiVA
Change search
Refine search result
1 - 28 of 28
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Amankwah, Henry
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Larsson, Torbjörn
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Textorius, Björn
    Linköping University, Department of Mathematics, Applied Mathematics. Linköping University, The Institute of Technology.
    Rönnberg, Elina
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Open-Pit Production Scheduling - Suggestions for Lagrangian Dual Heuristic and Time Aggregation ApproachesManuscript (preprint) (Other academic)
    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öping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Lööw, Tomas
    Saab AB, Sweden.
    Rönnberg, Elina
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    A constraint generation procedure for pre-runtime scheduling of integrated modular avionic systems2017In: Proceedings of the 13th Workshop on Models and Algorithms for Planning and Scheduling Problems / [ed] Susanne Albers, Nicole Megow, Andreas S. Schulz, Leen Stougie, 2017Conference paper (Other academic)
    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öping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Lööw, Tomas
    Saab AB, Sweden.
    Rönnberg, Elina
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    An Optimisation Approach for Pre-Runtime Scheduling of Tasks and Communication in an Integrated Modular Avionic System2017Report (Other academic)
    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öping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering. Saab AB, Linköping, Sweden.
    Lööw, Tomas
    Saab AB, Linköping, Sweden.
    Rönnberg, Elina
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering. Saab AB, Linköping, Sweden.
    An optimisation approach for pre-runtime scheduling of tasks and communication in an integrated modular avionic system2018In: Optimization and Engineering, ISSN 1389-4420, E-ISSN 1573-2924, Vol. 19, no 4, p. 977-1004Article in journal (Refereed)
    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öping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    An A* Algorithm for Solving a Prize-Collecting Sequencing Problem with One Common and Multiple Secondary Resources and Time Windows2018In: 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 (Refereed)
  • 6.
    Karlsson, Emil
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering. Saab AB, Linköping, Sweden.
    Rönnberg, Elina
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering. Saab AB, Linköping, Sweden.
    Explicit modelling of multiple intervals in a constraint generation procedure for multiprocessor scheduling2017In: Operations Research Proceedings 2017 / [ed] N. Kliewer, J.F. Ehmke and R. Borndörfer, Springer, 2017, p. 567-572Conference 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.

  • 7.
    Karlsson, Emil
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering. Saab AB, SE-581 88 Linköping.
    Rönnberg, Elina
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering. 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 scheduling2019Report (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.

  • 8.
    Karlsson, Emil
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Rönnberg, Elina
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Stenberg, Andreas
    Saab AB, Sweden.
    Uppman, Hannes
    Saab AB, Sweden.
    Heuristic enhancements of a constraint generation procedure for scheduling of avionic systems2018In: 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 (Refereed)
  • 9.
    Mayambala, Fred
    et al.
    Department of Mathematics, Makerere University, Kampala, Uganda.
    Rönnberg, Elina
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Larsson, Torbjörn
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Eigendecomposition of the mean-variance portfolio optimization model2015In: Optimization, control, and applications in the information age / [ed] Athanasios Migdalas and Athanasia Karakitsiou, Springer, 2015, p. 209-232Chapter in book (Refereed)
    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öping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Larsson, Torbjörn
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Tight Upper Bounds on the Cardinality Constrained Mean-Variance Portfolio Optimization Problem Using Truncated Eigendecomposition2016In: 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, p. 385-392Conference paper (Refereed)
    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öping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    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 Problem2018Conference paper (Refereed)
  • 12.
    Rönnberg, Elina
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering. Saab AB, Linköping, Sweden.
    Co-allocation of communication messages in an integrated modular avionic system2017In: Operations Research Proceedings 2017. / [ed] N. Kliewer, J.F. Ehmke, and R. Borndörfer, 2017, p. 459-465Conference 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.

  • 13.
    Rönnberg, Elina
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Contributions within two topics in integer programming: nurse scheduling and column generation2012Doctoral thesis, comprehensive summary (Other academic)
    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.

    List of papers
    1. Automating the self-scheduling process of nurses in Swedish healthcare: a pilot study
    Open this publication in new window or tab >>Automating the self-scheduling process of nurses in Swedish healthcare: a pilot study
    2010 (English)In: HEALTH CARE MANAGEMENT SCIENCE, ISSN 1386-9620, Vol. 13, no 1, p. 35-53Article in journal (Refereed) 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.

    Place, publisher, year, edition, pages
    Springer Science Business Media, 2010
    Keywords
    Nurse scheduling, Nurse rostering, Self-scheduling, Preference scheduling, Operations research, Integer linear programming
    National Category
    Mathematics
    Identifiers
    urn:nbn:se:liu:diva-59720 (URN)10.1007/s10729-009-9107-x (DOI)000281585200004 ()
    Note
    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/ Available from: 2010-09-24 Created: 2010-09-24 Last updated: 2018-06-25
    2. Automatic scheduling of nurses: What does it take in practice?
    Open this publication in new window or tab >>Automatic scheduling of nurses: What does it take in practice?
    2013 (English)In: 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, p. 151-178Chapter in book (Refereed)
    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. 

    Place, publisher, year, edition, pages
    New York, NY: Springer Science+Business Media B.V., 2013
    Series
    Springer Optimization and Its Applications, ISSN 1931-6828 ; 74
    Keywords
    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
    National Category
    Computational Mathematics
    Identifiers
    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)
    Available from: 2012-03-26 Created: 2012-03-26 Last updated: 2018-06-25Bibliographically approved
    3. Column generation using non-optimal dual solutions: Optimality conditions and over-generation
    Open this publication in new window or tab >>Column generation using non-optimal dual solutions: Optimality conditions and over-generation
    (English)Manuscript (preprint) (Other academic)
    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.

    Keywords
    Binary program, column generation, optimality conditions, overgeneration
    National Category
    Computational Mathematics
    Identifiers
    urn:nbn:se:liu:diva-76090 (URN)
    Available from: 2012-03-26 Created: 2012-03-26 Last updated: 2018-06-25Bibliographically approved
    4. Column Generation in the Integral Simplex Method
    Open this publication in new window or tab >>Column Generation in the Integral Simplex Method
    2009 (English)In: European Journal of Operational Research, ISSN 0377-2217, E-ISSN 1872-6860, Vol. 192, no 1, p. 333-342Article in journal (Refereed) 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.

    Place, publisher, year, edition, pages
    Elsevier, 2009
    Keywords
    integer programming, set partitioning, column generation, quasi-integrality
    National Category
    Computational Mathematics
    Identifiers
    urn:nbn:se:liu:diva-15287 (URN)10.1016/j.ejor.2007.09.037 (DOI)
    Note
    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/Available from: 2008-10-29 Created: 2008-10-29 Last updated: 2018-06-25Bibliographically approved
    5. All-integer column generation: Basic principles and extensions
    Open this publication in new window or tab >>All-integer column generation: Basic principles and extensions
    2014 (English)In: European Journal of Operational Research, ISSN 0377-2217, E-ISSN 1872-6860, Vol. 233, no 3, p. 529-538Article in journal (Refereed) 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.

    Place, publisher, year, edition, pages
    Elsevier, 2014
    Keywords
    Set partitioning, meta-heuristic, column generation, quasiintegrality, surrogate columns, over-generation, all-integer pivots
    National Category
    Computational Mathematics
    Identifiers
    urn:nbn:se:liu:diva-76091 (URN)10.1016/j.ejor.2013.08.036 (DOI)000328180200006 ()urn:nbn:se:liu:diva-102966 (Local ID)urn:nbn:se:liu:diva-102966 (Archive number)urn:nbn:se:liu:diva-102966 (OAI)
    Note

    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.

    Available from: 2012-03-26 Created: 2012-03-26 Last updated: 2018-06-25Bibliographically approved
  • 14.
    Rönnberg, Elina
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Methods and Applications in Integer Programming: All-Integer Column Generation and Nurse Scheduling2008Licentiate thesis, comprehensive summary (Other academic)
    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.

    List of papers
    1. Column Generation in the Integral Simplex Method
    Open this publication in new window or tab >>Column Generation in the Integral Simplex Method
    2009 (English)In: European Journal of Operational Research, ISSN 0377-2217, E-ISSN 1872-6860, Vol. 192, no 1, p. 333-342Article in journal (Refereed) 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.

    Place, publisher, year, edition, pages
    Elsevier, 2009
    Keywords
    integer programming, set partitioning, column generation, quasi-integrality
    National Category
    Computational Mathematics
    Identifiers
    urn:nbn:se:liu:diva-15287 (URN)10.1016/j.ejor.2007.09.037 (DOI)
    Note
    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/Available from: 2008-10-29 Created: 2008-10-29 Last updated: 2018-06-25Bibliographically approved
    2. An All-Integer Column Generation Methodology for Set Partitioning Problems
    Open this publication in new window or tab >>An All-Integer Column Generation Methodology for Set Partitioning Problems
    2008 (English)Report (Other academic)
    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.

    Publisher
    p. 23
    Series
    Report / Department of Mathematics, Universitetet i Linköping, Tekniska högskolan, ISSN 0348-2960
    Keywords
    integer programming, column generation, quasi-integrality, surrogate columns, over-generation
    National Category
    Computational Mathematics
    Identifiers
    urn:nbn:se:liu:diva-15256 (URN)
    Available from: 2008-10-28 Created: 2008-10-27 Last updated: 2018-06-25Bibliographically approved
    3. Automating the Self-Scheduling Process of Nurses in Swedish Healthcare: A Pilot Study
    Open this publication in new window or tab >>Automating the Self-Scheduling Process of Nurses in Swedish Healthcare: A Pilot Study
    2008 (English)Report (Other academic)
    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.

    Publisher
    p. 29
    Series
    LiTH-MAT-R, ISSN 0348-2960 ; 2008:8
    Keywords
    nurse scheduling, integer linear programming
    National Category
    Computational Mathematics
    Identifiers
    urn:nbn:se:liu:diva-57562 (URN)
    Available from: 2008-10-28 Created: 2008-10-27 Last updated: 2018-06-25Bibliographically approved
  • 15.
    Rönnberg, Elina
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Larsson, Torbjörn
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    All-integer column generation: Basic principles and extensions2014In: European Journal of Operational Research, ISSN 0377-2217, E-ISSN 1872-6860, Vol. 233, no 3, p. 529-538Article in journal (Refereed)
    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öping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Larsson, Torbjörn
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    An All-Integer Column Generation Methodology for Set Partitioning Problems2008Report (Other academic)
    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öping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Larsson, Torbjörn
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    An integer optimality condition for column generation on zero-one linear programs2019In: Discrete Optimization, ISSN 1572-5286, E-ISSN 1873-636X, Vol. 31, p. 79-92Article in journal (Refereed)
    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.

    The full text will be freely available from 2020-09-27 15:07
  • 18.
    Rönnberg, Elina
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Larsson, Torbjörn
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Automating the Self-Scheduling Process of Nurses in Swedish Healthcare: A Pilot Study2008Report (Other academic)
    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öping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Larsson, Torbjörn
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Automating the self-scheduling process of nurses in Swedish healthcare: a pilot study2010In: HEALTH CARE MANAGEMENT SCIENCE, ISSN 1386-9620, Vol. 13, no 1, p. 35-53Article in journal (Refereed)
    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öping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Larsson, Torbjörn
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Column Generation in the Integral Simplex Method2009In: European Journal of Operational Research, ISSN 0377-2217, E-ISSN 1872-6860, Vol. 192, no 1, p. 333-342Article in journal (Refereed)
    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öping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Larsson, Torbjörn
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Column generation using non-optimal dual solutions: Optimality conditions and over-generationManuscript (preprint) (Other academic)
    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öping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Larsson, Torbjörn
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Integral Simplex Methods for the Set Partitioning Problem: Globalisation and Anti-Cycling2018In: 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.

  • 23.
    Rönnberg, Elina
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Larsson, Torbjörn
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Bertilsson, Ann
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Automatic scheduling of nurses: What does it take in practice?2013In: 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, p. 151-178Chapter in book (Refereed)
    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öping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Lei, Lei
    Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, The Institute of Technology.
    Yuan, Di
    Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, The Institute of Technology.
    Larsson, Torbjörn
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Rönnberg, Elina
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Power efficient uplink scheduling in SC-FDMA: Bounding global optimality by column generation2013In: 2013 IEEE 18th International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD, IEEE , 2013, p. 119-123Conference paper (Refereed)
    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öping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Larsson, Torbjörn
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Rönnberg, Elina
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    A Large Neighbourhood Search Principle for Column-Oriented Models: Theoretical Derivation and Example Applications2016In: Matheuristics 2016: Proceedings of the Sixth International Workshop on Model-based Metaheuristics / [ed] V. Maniezzo and T. Stutzle, Bruxelles, Belgium: IRIDIA , 2016Conference paper (Refereed)
  • 26.
    Zhao, Yixin
    et al.
    Nanjing University of Science and Technology, School of Automation.
    Larsson, Torbjörn
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Rönnberg, Elina
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    An integer programming column generation principlefor heuristic search methods2019In: International Transactions in Operational Research, ISSN 0969-6016, E-ISSN 1475-3995, Vol. 27, no 1, p. 665-695Article in journal (Refereed)
    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öping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Rönnberg, Elina
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    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 generation2018In: Journal of Global Optimization, ISSN 0925-5001, E-ISSN 1573-2916, Vol. 72, no 3, p. 517-538Article in journal (Refereed)
    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.
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Larsson, Torbjörn
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Yuan, Di
    Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, Faculty of Science & Engineering.
    Rönnberg, Elina
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Lei, Lei
    Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, Faculty of Science & Engineering.
    Power efficient uplink scheduling in SC-FDMA: benchmarking by column generation2016In: Optimization and Engineering, ISSN 1389-4420, E-ISSN 1573-2924, Vol. 17, no 4, p. 695-725Article in journal (Refereed)
    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 - 28 of 28
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf