liu.seSearch for publications in DiVA
Change search
Refine search result
1234567 1 - 50 of 379
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • 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.
    Abdulla, Ariyan
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Andersson, Erik
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Heuristiska algoritmer för schemaläggning i real-tidssystem med hänsyn till data beroenden2018Independent thesis Basic level (degree of Bachelor), 10,5 credits / 16 HE creditsStudent thesis
    Abstract [en]

    The schedule for the jobs in a real-time system can have a huge impact on how the system behave. Since real-time systems are common in safety applications it is important that the scheduling is done in a valid way. Furthermore, one can enhance the performance of the applications by minimizing data latency and jitter. A challenge is that jobs in real-time systems usually have complex constraints making it too time consuming to minimize data latency and jitter to optimality. The purpose of this report is to investigate the possibility of creating high quality schedules using heuristics, with the goal to keep the computational time under one minute. This will be done by comparing three different algorithms that will be used on real scheduling instances provided by the company Arcticus. The first algorithm is a greedy heuristic, the second one a local search and the third one is a metaheuristic, simulated annealing. The results indicate that the data latency can be reduced whilst keeping the computational time below one minute.

    Download full text (pdf)
    fulltext
  • 2.
    Akram, Usman
    et al.
    Linköping University, Department of Physics, Chemistry and Biology, Theoretical Biology. Linköping University, Faculty of Science & Engineering.
    Metson, Genevieve
    Linköping University, Department of Physics, Chemistry and Biology, Theoretical Biology. Linköping University, Faculty of Science & Engineering. Linköping University, Centre for Climate Science and Policy Research, CSPR.
    Quttineh, Nils-Hassan
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Wennergren, Uno
    Linköping University, Department of Physics, Chemistry and Biology, Theoretical Biology. Linköping University, Faculty of Science & Engineering.
    Closing Pakistan’s yield gaps through nutrient recycling2018In: Frontiers in Sustainable Food Systems, E-ISSN 2571-581X, p. 1-14, article id 00024Article in journal (Refereed)
    Abstract [en]

    Achieving food security will require closing yield gaps in many regions, including Pakistan. Although fertilizer subsidies have facilitated increased nitrogen (N) application rates, many staple crop yields have yet to reach their maximum potential. Considering that current animal manure and human excreta (bio-supply) recycling rates are low, there is substantial potential to increase the reuse of nutrients in bio-supply. We quantified 2010 crop N, phosphorus (P), and potassium (K) needs along with bio-supply nutrient availability for Pakistani districts, and compared these values to synthetic fertilizer use and costs. We found that synthetic fertilizer use combined with low bio-supply recycling resulted in a substantial gap between nutrient supply and P and K crop needs, which would cost 3 billion USD to fill with synthetic fertilizers. If all bio-supply was recycled, it could eliminate K synthetic fertilizer needs and decrease N synthetic fertilizer needs to 43% of what was purchased in 2010. Under a full recycling scenario, farmers would still require an additional 0.28 million tons of synthetic P fertilizers, costing 2.77 billion USD. However, it may not be prohibitively expensive to correct P deficiencies. Pakistan already spends this amount of money on fertilizers. If funds used for synthetic N were reallocated to synthetic P purchases in a full bio-supply recycling scenario, crop needs could be met. Most recycling could happen within districts, with only 6% of bio-supply requiring between-district transport when optimized to meet national N crop needs. Increased recycling in Pakistan could be a viable way to decrease yield gaps.

    Download full text (pdf)
    Closing Pakistan’s Yield Gaps Through Nutrient Recycling
  • 3.
    Akram, Usman
    et al.
    Linköping University, Department of Physics, Chemistry and Biology, Theoretical Biology. Linköping University, Faculty of Science & Engineering.
    Quttineh, Nils-Hassan
    Linköping University, Department of Mathematics, Optimization. Linköping University, Faculty of Science & Engineering.
    Wennergren, Uno
    Linköping University, Department of Physics, Chemistry and Biology, Theoretical Biology. Linköping University, Faculty of Science & Engineering.
    Tonderski, Karin
    Linköping University, Department of Physics, Chemistry and Biology, Biology. Linköping University, Faculty of Science & Engineering.
    Metson, Genevieve
    Linköping University, Department of Physics, Chemistry and Biology, Theoretical Biology. Linköping University, Faculty of Science & Engineering.
    Enhancing nutrient recycling from excreta to meet crop nutrient needs in Sweden - a spatial analysis2019In: Scientific Reports, E-ISSN 2045-2322, Vol. 9, article id 10264Article in journal (Refereed)
    Abstract [en]

    Increased recycling of nutrient-rich organic waste to meet crop nutrient needs is an essential component of a more sustainable food system. However, agricultural specialization continues to pose a significant challenge to balancing crop nutrient needs and the nutrient supply from animal manure and human excreta locally. For Sweden, this study found that recycling all excreta (in 2007) could meet up to 75% of crop nitrogen and 81% of phosphorus needs, but that this would exceed crop potassium needs by 51%. Recycling excreta within municipalities could meet 63% of crop P nutrient needs, but large regional differences and imbalances need to be corrected to avoid over or under fertilizing. Over 50% of the total nitrogen and phosphorus in excreta is contained in just 40% of municipalities, and those have a surplus of excreta nutrients compared to crop needs. Reallocation of surpluses (nationally optimized for phosphorus) towards deficit municipalities, would cost 192 million USD (for 24 079 km of truck travel). This is 3.7 times more than the total NPK fertilizer value being transported. These results indicate that Sweden could reduce its dependence on synthetic fertilizers through investments in excreta recycling, but this would likely require valuing also other recycling benefits.

    Download full text (pdf)
    fulltext
    Download (pdf)
    author correction
  • 4.
    Akram, Usman
    et al.
    Linköping University, Department of Physics, Chemistry and Biology, Theoretical Biology. Linköping University, Faculty of Science & Engineering.
    Quttineh, Nils-Hassan
    Linköping University, Department of Mathematics, Optimization. Linköping University, Faculty of Science & Engineering.
    Wennergren, Uno
    Linköping University, Department of Physics, Chemistry and Biology, Theoretical Biology. Linköping University, Faculty of Science & Engineering.
    Tonderski, Karin
    Linköping University, Department of Physics, Chemistry and Biology, Biology. Linköping University, Faculty of Science & Engineering.
    Metson, Geneviéve S.
    Linköping University, Department of Physics, Chemistry and Biology, Theoretical Biology. Linköping University, Faculty of Science & Engineering.
    Optimizing Nutrient Recycling From Excreta in Sweden and Pakistan: Higher Spatial Resolution Makes Transportation More Attractive2019In: Frontiers in Sustainable Food Systems, E-ISSN 2571-581X, Vol. 3Article in journal (Refereed)
    Abstract [en]

    Recycling essential plant nutrients like nitrogen (N), phosphorus (P), and potassium (K) from organic waste such as human and animal excreta will be an essential part of sustainable food systems and a circular economy. However, transportation is often cited as a major barrier to increased recycling as organic waste is heavy and bulky, and distances between areas of abundant waste may be far from areas with a need for fertilizers. We investigated the effect of increased input data spatial resolution to an optimization model on the weight, distance, and spatial patterns of transport. The model was run in Sweden and in Pakistan to examine cost-effectiveness of transporting excess excreta to areas of crop need after local recycling. Increasing the resolution of input data from political boundaries (municipalities and districts) to 0.083 decimal grids increased the amount of N requiring transport by 12% in Pakistan and increased P requiring transport by 14% in Sweden. The average distance decreased by 67% (to 44 km) in Pakistan but increased by 1 km in Sweden. Further increasing the resolution to 5 km grids in Sweden decreased the average transportation distance by 9 km (down to 123 km). In both countries, increasing resolution also decreased the number of long-distance heavy transports, and as such costs did not increase as much as total distance and weight transported. Ultimately, transportation in Pakistan seemed financially beneficial: the cost of transport only represented 13% of the NPK fertilizer value transported, and total recycling could even cover 78% of additional fertilizer purchases required. In Sweden, the cost of transporting excreta did not seem cost effective without valuing other potential benefits of increased recycling: costs were three times higher than the fertilizer value transported in excreta at the 5 km resolution. In summary, increasing input data resolution created a more realistic picture of recycling needs. This also highlighted more favorable cost to fertilizer value ratios which could make it easier to move forward with industry and government partners to facilitate productive recycling. Our analysis shows that in both countries increased recycling can result in better spatial nutrient balances.

    Download full text (pdf)
    fulltext
  • 5. Order onlineBuy this publication >>
    Amankwah, Henry
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Mathematical Optimization Models and Methods for Open-Pit Mining2011Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    Open-pit mining is an operation in which blocks from the ground are dug to extract the ore contained in them, and in this process a deeper and deeper pit is formed until the mining operation ends. Mining is often a highly complex industrial operation, with respect to both technological and planning aspects. The latter may involve decisions about which ore to mine and in which order. Furthermore, mining operations are typically capital intensive and long-term, and subject to uncertainties regarding ore grades, future mining costs, and the market prices of the precious metals contained in the ore. Today, most of the high-grade or low-cost ore deposits have already been depleted, and to obtain sufficient profitability in mining operations it is therefore today often a necessity to achieve operational efficiency with respect to both technological and planning issues.

    In this thesis, we study the open-pit design problem, the open-pit mining scheduling problem, and the open-pit design problem with geological and price uncertainty. These problems give rise to (mixed) discrete optimization models that in real-life settings are large scale and computationally challenging.

    The open-pit design problem is to find an optimal ultimate contour of the pit, given estimates of ore grades, that are typically obtained from samples in drill holes, estimates of costs for mining and processing ore, and physical constraints on mining precedence and maximal pit slope. As is well known, this problem can be solved as a maximum flow problem in a special network. In a first paper, we show that two well known parametric procedures for finding a sequence of intermediate contours leading to an ultimate one, can be interpreted as Lagrangian dual approaches to certain side-constrained design models. In a second paper, we give an alternative derivation of the maximum flow problem of the design problem.

    We also study the combined open-pit design and mining scheduling problem, which is the problem of simultaneously finding an ultimate pit contour and the sequence in which the parts of the orebody shall be removed, subject to mining capacity restrictions. The goal is to maximize the discounted net profit during the life-time of the mine. We show in a third paper that the combined problem can also be formulated as a maximum flow problem, if the mining capacity restrictions are relaxed; in this case the network however needs to be time-expanded.

    In a fourth paper, we provide some suggestions for Lagrangian dual heuristic and time aggregation approaches for the open-pit scheduling problem. Finally, we study the open-pit design problem under uncertainty, which is taken into account by using the concept of conditional value-atrisk. This concept enables us to incorporate a variety of possible uncertainties, especially regarding grades, costs and prices, in the planning process. In real-life situations, the resulting models would however become very computationally challenging.

    List of papers
    1. On the use of Parametric Open-Pit Design Models for Mine Scheduling - Pitfalls and Counterexamples
    Open this publication in new window or tab >>On the use of Parametric Open-Pit Design Models for Mine Scheduling - Pitfalls and Counterexamples
    (English)Manuscript (preprint) (Other academic)
    Abstract [en]

    This paper discusses a Lagrangian relaxation interpretation of the Picard and Smith (2004) parametric approach to open-pit mining, which finds a sequence of intermediate contours leading to an ultimate one. This method is similar to the well known parametric approach of Lerchs and Grossmann (1965). We give examples of worst case performance, as well as best case performance of the Picard-Smith approach. The worst case behaviour can be very poor in that we might not obtain any intermediate contours at all. We also discuss alternative parametric methods for finding intermediate contours, but conclude that such methods seem to have inherent weaknesses.

    Keywords
    Open-pit mining, Picard-Smith model, Lagrangian relaxation, pit design, block value, scheduling
    National Category
    Mathematics
    Identifiers
    urn:nbn:se:liu:diva-70838 (URN)
    Available from: 2011-09-20 Created: 2011-09-20 Last updated: 2013-08-30Bibliographically approved
    2. A Duality-Based Derivation of the Maximum Flow Formulation of the Open-Pit Design Problem
    Open this publication in new window or tab >>A Duality-Based Derivation of the Maximum Flow Formulation of the Open-Pit Design Problem
    (English)Manuscript (preprint) (Other academic)
    Abstract [en]

    Open-pit mining is a surface mining operation whereby ore, or waste, is excavated from the surface of the land. The open-pit design problem is deciding on which blocks of an ore deposit to mine in order to maximize the total profit, while obeying digging constraints concerning pit slope and block precedence. The open-pit design problem can be formulated as a maximum flow problem in a certain capacitated network, as first shown by Picard in 1976. His derivation is based on a restatement of the problem as a quadratic binary program. We give an alternative derivation of the maximum flow formulation, which uses only linear programming duality.

    Keywords
    Open-pit mining, pit design, maximum flow, maximum profit, block model
    National Category
    Mathematics
    Identifiers
    urn:nbn:se:liu:diva-70840 (URN)
    Available from: 2011-09-20 Created: 2011-09-20 Last updated: 2013-08-30Bibliographically approved
    3. A Multi-Parametric Maximum Flow Characterization of the Open-Pit Scheduling Problem
    Open this publication in new window or tab >>A Multi-Parametric Maximum Flow Characterization of the Open-Pit Scheduling Problem
    (English)Manuscript (preprint) (Other academic)
    Abstract [en]

    We consider the problem of finding an optimal mining schedule for an openpit during a number of time periods, subject to a mining capacity restriction for each time period. By applying Lagrangian relaxation to the capacities, a multi-parametric formulation is obtained. We show that this formulation can be restated as a maximum flow problem in a time-expanded network. This result extends a well-known result of Picard from 1976 for the open-pit design problem, that is, the single-period case, to the case of multiple time periods.

    Keywords
    Open-pit mining, scheduling, maximum flow, minimum cut, Lagrangian relaxation
    National Category
    Mathematics
    Identifiers
    urn:nbn:se:liu:diva-70841 (URN)
    Available from: 2011-09-20 Created: 2011-09-20 Last updated: 2013-08-30Bibliographically approved
    4. Open-Pit Production Scheduling - Suggestions for Lagrangian Dual Heuristic and Time Aggregation Approaches
    Open this publication in new window or tab >>Open-Pit Production Scheduling - Suggestions for Lagrangian Dual Heuristic and Time Aggregation Approaches
    (English)Manuscript (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.

    Keywords
    Open-pit mining, mine scheduling, Lagrangian relaxation, maximum flow, time aggregation
    National Category
    Mathematics
    Identifiers
    urn:nbn:se:liu:diva-70842 (URN)
    Available from: 2011-09-20 Created: 2011-09-20 Last updated: 2018-06-25Bibliographically approved
    5. Open-Pit Mining with Uncertainty - A Conditional Value-at-Risk Approach
    Open this publication in new window or tab >>Open-Pit Mining with Uncertainty - A Conditional Value-at-Risk Approach
    (English)Manuscript (preprint) (Other academic)
    Abstract [en]

    The selection of a mine design is based on estimating net present values of all possible, technically feasible mine plans so as to select the one with the maximum value. It is a hard task to know with certainty the quantity and quality of ore in the ground. This geological uncertainty, and also the future market behaviour of metal prices and foreign exchange rates, which are impossible to be known with certainty, make mining a high risk business.

    Value-at-Risk (VaR) is a measure that is used in financial decisions to minimize the loss caused by inadequate monitoring of risk. This measure does however have certain drawbacks such as lack of consistency, nonconvexity, and nondifferentiability. Rockafellar and Uryasev (2000) introduce the Conditional Value-at-Risk (CVaR) measure as an alternative to the VaR measure. The CVaR measure gives rise to a convex problem.

    An optimization model that maximizes expected return while minimizing risk is important for the mining sector as this will help make better decisions on the blocks of ore to mine at a particular point in time. We present a CVaR approach to the uncertainty involved in open-pit mining. We formulate investment and design models for the open-pit mine and also give a nested pit scheduling model based on CVaR. Several numerical results based on our models are presented by using scenarios from simulated geological and price uncertainties.

    Keywords
    Conditional value-at-risk (CVaR), open-pit mining, geological uncertainty, price uncertainty
    National Category
    Mathematics
    Identifiers
    urn:nbn:se:liu:diva-70843 (URN)
    Available from: 2011-09-20 Created: 2011-09-20 Last updated: 2013-08-30Bibliographically approved
    Download full text (pdf)
    Mathematical Optimization Models and Methods for Open-Pit Mining
    Download (pdf)
    omslag
  • 6.
    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.
    A Duality-Based Derivation of the Maximum Flow Formulation of the Open-Pit Design ProblemManuscript (preprint) (Other academic)
    Abstract [en]

    Open-pit mining is a surface mining operation whereby ore, or waste, is excavated from the surface of the land. The open-pit design problem is deciding on which blocks of an ore deposit to mine in order to maximize the total profit, while obeying digging constraints concerning pit slope and block precedence. The open-pit design problem can be formulated as a maximum flow problem in a certain capacitated network, as first shown by Picard in 1976. His derivation is based on a restatement of the problem as a quadratic binary program. We give an alternative derivation of the maximum flow formulation, which uses only linear programming duality.

  • 7.
    Amankwah, Henry
    et al.
    University of Cape Coast, Ghana .
    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.
    A maximum flow formulation of a multi-period open-pit mining problem2014In: Operational Research, ISSN 1109-2858, E-ISSN 1866-1505, Vol. 14, no 1, p. 1-10Article in journal (Refereed)
    Abstract [en]

    We consider the problem of finding an optimal mining sequence for an open pit during a number of time periods subject to only spatial and temporal precedence constraints. This problem is of interest because such constraints are generic to any open-pit scheduling problem and, in particular, because it arises as a Lagrangean relaxation of an open-pit scheduling problem. We show that this multi-period open-pit mining problem can be solved as a maximum flow problem in a time-expanded mine graph. Further, the minimum cut in this graph will define an optimal sequence of pits. This result extends a well-known result of J.-C. Picard from 1976 for the open-pit mine design problem, that is, the single-period case, to the case of multiple time periods.

    Download full text (pdf)
    fulltext
  • 8.
    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.
    A Multi-Parametric Maximum Flow Characterization of the Open-Pit Scheduling ProblemManuscript (preprint) (Other academic)
    Abstract [en]

    We consider the problem of finding an optimal mining schedule for an openpit during a number of time periods, subject to a mining capacity restriction for each time period. By applying Lagrangian relaxation to the capacities, a multi-parametric formulation is obtained. We show that this formulation can be restated as a maximum flow problem in a time-expanded network. This result extends a well-known result of Picard from 1976 for the open-pit design problem, that is, the single-period case, to the case of multiple time periods.

  • 9.
    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.
    On the use of Parametric Open-Pit Design Models for Mine Scheduling - Pitfalls and CounterexamplesManuscript (preprint) (Other academic)
    Abstract [en]

    This paper discusses a Lagrangian relaxation interpretation of the Picard and Smith (2004) parametric approach to open-pit mining, which finds a sequence of intermediate contours leading to an ultimate one. This method is similar to the well known parametric approach of Lerchs and Grossmann (1965). We give examples of worst case performance, as well as best case performance of the Picard-Smith approach. The worst case behaviour can be very poor in that we might not obtain any intermediate contours at all. We also discuss alternative parametric methods for finding intermediate contours, but conclude that such methods seem to have inherent weaknesses.

  • 10.
    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.
    Open-Pit Mining with Uncertainty - A Conditional Value-at-Risk ApproachManuscript (preprint) (Other academic)
    Abstract [en]

    The selection of a mine design is based on estimating net present values of all possible, technically feasible mine plans so as to select the one with the maximum value. It is a hard task to know with certainty the quantity and quality of ore in the ground. This geological uncertainty, and also the future market behaviour of metal prices and foreign exchange rates, which are impossible to be known with certainty, make mining a high risk business.

    Value-at-Risk (VaR) is a measure that is used in financial decisions to minimize the loss caused by inadequate monitoring of risk. This measure does however have certain drawbacks such as lack of consistency, nonconvexity, and nondifferentiability. Rockafellar and Uryasev (2000) introduce the Conditional Value-at-Risk (CVaR) measure as an alternative to the VaR measure. The CVaR measure gives rise to a convex problem.

    An optimization model that maximizes expected return while minimizing risk is important for the mining sector as this will help make better decisions on the blocks of ore to mine at a particular point in time. We present a CVaR approach to the uncertainty involved in open-pit mining. We formulate investment and design models for the open-pit mine and also give a nested pit scheduling model based on CVaR. Several numerical results based on our models are presented by using scenarios from simulated geological and price uncertainties.

  • 11.
    Amankwah, Henry
    et al.
    University of Cape Coast, Ghana .
    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, Mathematics and Applied Mathematics. Linköping University, The Institute of Technology.
    Open-pit mining with uncertainty: A conditional value-at-risk approach2013In: Optimization Theory, Decision Making, and Operations Research Applications: Proceedings of the 1st International Symposium and 10th Balkan Conference on Operational Research / [ed] Athanasios Migdalas, Angelo Sifaleras, Christos K. Georgiadis, Jason Papathanasiou, Emmanuil Stiakakis, New York: Springer, 2013, p. 117-139Conference paper (Refereed)
    Abstract [en]

    The selection of a mine design is based on estimating net present values of all possible, technically feasible mine plans so as to select the one with the maximum value. It is a hard task to know with certainty the quantity and quality of ore in the ground. This geological uncertainty and also the future market behavior of metal prices and foreign exchange rates, which are always uncertain, make mining a high risk business. Value-at-Risk (VaR) is a measure that is used in financial decisions to minimize the loss caused by inadequate monitoring of risk. This measure does, however, have certain drawbacks such as lack of consistency, nonconvexity, and nondifferentiability. Rockafellar and Uryasev [J. Risk 2, 21-41 (2000)] introduce the Conditional Value-at-Risk (CVaR) measure as an alternative to the VaR measure. The CVaR measure gives rise to a convex optimization problem. An optimization model that maximizes expected return while minimizing risk is important for the mining sector as this will help make better decisions on the blocks of ore to mine at a particular point in time. We present a CVaR approach to the uncertainty involved in open-pit mining. We formulate investment and design models for the open-pit mine and also give a nested pit scheduling model based on CVaR. Several numerical results based on our models are presented by using scenarios from simulated geological and market uncertainties.

  • 12.
    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.

  • 13.
    Andersson, Mats
    et al.
    Linköping University, Department of Biomedical Engineering, Medical Informatics. Linköping University, The Institute of Technology.
    Burdakov, Oleg
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Knutsson, Hans
    Linköping University, Department of Biomedical Engineering, Medical Informatics. Linköping University, The Institute of Technology.
    Zikrin, Spartak
    Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, The Institute of Technology.
    Global search strategies for solving multilinear least-squares problems2012In: Sultan Qaboos University Journal for Science, ISSN 1027-524X, Vol. 17, no 1, p. 12-21Article in journal (Refereed)
    Abstract [en]

    The multilinear least-squares (MLLS) problem is an extension of the linear leastsquares problem. The difference is that a multilinear operator is used in place of a matrix-vector product. The MLLS is typically a large-scale problem characterized by a large number of local minimizers. It originates, for instance, from the design of filter networks. We present a global search strategy that allows for moving from one local minimizer to a better one. The efficiency of this strategy is illustrated by results of numerical experiments performed for some problems related to the design of filter networks.

    Download full text (pdf)
    TR2011-17
  • 14.
    Andersson, Mats
    et al.
    Linköping University, Department of Biomedical Engineering, Medical Informatics. Linköping University, The Institute of Technology.
    Burdakov, Oleg
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Knutsson, Hans
    Linköping University, Department of Biomedical Engineering, Medical Informatics. Linköping University, The Institute of Technology.
    Zikrin, Spartak
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Global Search Strategies for Solving Multilinear Least-squares Problems2011Report (Other academic)
    Abstract [en]

    The multilinear least-squares (MLLS) problem is an extension of the linear least-squares problem. The difference is that a multilinearoperator is used in place of a matrix-vector product. The MLLS istypically a large-scale problem characterized by a large number of local minimizers. It originates, for instance, from the design of filter networks. We present a global search strategy that allows formoving from one local minimizer to a better one. The efficiencyof this strategy isillustrated by results of numerical experiments performed forsome problems related to the design of filter networks.

    Download full text (pdf)
    Global Search Strategies for Solving Multilinear Least-squares Problems
  • 15.
    Andersson, Mats
    et al.
    Linköping University, Department of Biomedical Engineering. Linköping University, The Institute of Technology.
    Burdakov, Oleg
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Knutsson, Hans
    Linköping University, Department of Biomedical Engineering, Medical Informatics. Linköping University, The Institute of Technology.
    Zikrin, Spartak
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Sparsity Optimization in Design of Multidimensional Filter Networks2013Report (Other academic)
    Abstract [en]

    Filter networks is a powerful tool used for reducing the image processing time, while maintaining its reasonably high quality.They are composed of sparse sub-filters whose low sparsity ensures fast image processing.The filter network design is related to solvinga sparse optimization problem where a cardinality constraint bounds above the sparsity level.In the case of sequentially connected sub-filters, which is the simplest network structure of those considered in this paper, a cardinality-constrained multilinear least-squares (MLLS) problem is to be solved. If to disregard the cardinality constraint, the MLLS is typically a large-scale problem characterized by a large number of local minimizers. Each of the local minimizers is singular and non-isolated.The cardinality constraint makes the problem even more difficult to solve.An approach for approximately solving the cardinality-constrained MLLS problem is presented.It is then applied to solving a bi-criteria optimization problem in which both thetime and quality of image processing are optimized. The developed approach is extended to designing filter networks of a more general structure. Its efficiency is demonstrated by designing certain 2D and 3D filter networks. It is also compared with the existing approaches.

    Download full text (pdf)
    Sparsity Optimization in Design of Multidimensional Filter Networks (revised version)
  • 16.
    Andersson, Mats
    et al.
    Linköping University, Department of Biomedical Engineering, Medical Informatics. Linköping University, The Institute of Technology. Linköping University, Center for Medical Image Science and Visualization (CMIV).
    Burdakov, Oleg
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Knutsson, Hans
    Linköping University, Department of Biomedical Engineering, Medical Informatics. Linköping University, The Institute of Technology.
    Zikrin, Spartak
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Sparsity Optimization in Design of Multidimensional Filter Networks2015In: Optimization and Engineering, ISSN 1389-4420, E-ISSN 1573-2924, Vol. 16, no 2, p. 259-277Article in journal (Refereed)
    Abstract [en]

    Filter networks are used as a powerful tool used for reducing the image processing time and maintaining high image quality.They are composed of sparse sub-filters whose high sparsity ensures fast image processing.The filter network design is related to solvinga sparse optimization problem where a cardinality constraint bounds above the sparsity level.In the case of sequentially connected sub-filters, which is the simplest network structure of those considered in this paper, a cardinality-constrained multilinear least-squares (MLLS) problem is to be solved. Even when disregarding the cardinality constraint, the MLLS is typically a large-scale problem characterized by a large number of local minimizers, each of which is singular and non-isolated.The cardinality constraint makes the problem even more difficult to solve.

    An approach for approximately solving the cardinality-constrained MLLS problem is presented.It is then applied to solving a bi-criteria optimization problem in which both thetime and quality of image processing are optimized. The developed approach is extended to designing filter networks of a more general structure. Its efficiency is demonstrated by designing certain 2D and 3D filter networks. It is also compared with the existing approaches.

    Download full text (pdf)
    fulltext
  • 17.
    Andersson, Per-Åke
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    CDU: R2 Optimeringsmetoder för resursfördelning inom Dr&Uh-verksamhet väg2003In: CDU-dagen,2003, 2003Conference paper (Other academic)
  • 18.
    Andersson, Per-Åke
    Linköping University, Department of Mathematics, Optimization. Linköping University, The Institute of Technology.
    Computation of Thermal Development in Injection Mould Filling, based on the Distance Model2002Licentiate thesis, monograph (Other academic)
    Abstract [en]

    The heat transfer in the filling phase of injection moulding is studied, based on Gunnar Aronsson’s distance model for flow expansion ([Aronsson], 1996).

    The choice of a thermoplastic materials model is motivated by general physical properties, admitting temperature and pressure dependence. Two-phase, per-phase-incompressible, power-law fluids are considered. The shear rate expression takes into account pseudo-radial flow from a point inlet.

    Instead of using a finite element (FEM) solver for the momentum equations a general analytical viscosity expression is used, adjusted to current axial temperature profiles and yielding expressions for axial velocity profile, pressure distribution, frozen layer expansion and special front convection.

    The nonlinear energy partial differential equation is transformed into its conservative form, expressed by the internal energy, and is solved differently in the regions of streaming and stagnant flow, respectively. A finite difference (FD) scheme is chosen using control volume discretization to keep truncation errors small in the presence of non-uniform axial node spacing. Time and pseudo-radial marching is used. A local system of nonlinear FD equations is solved. In an outer iterative procedure the position of the boundary between the “solid” and “liquid” fluid cavity parts is determined. The uniqueness of the solution is claimed. In an inner iterative procedure the axial node temperatures are found. For all physically realistic material properties the convergence is proved. In particular the assumptions needed for the Newton-Mysovskii theorem are secured. The metal mould PDE is locally solved by a series expansion. For particular material properties the same technique can be applied to the “solid” fluid.

    In the circular plate application, comparisons with the commercial FEM-FD program Moldflow (Mfl) are made, on two Mfl-database materials, for which model parameters are estimated/adjusted. The resulting time evolutions of pressures and temperatures are analysed, as well as the radial and axial profiles of temperature and frozen layer. The greatest differences occur at the flow front, where Mfl neglects axial heat convection. The effects of using more and more complex material models are also investigated. Our method performance is reported.

    In the polygonal star-shaped plate application a geometric cavity model is developed. Comparison runs with the commercial FEM-FD program Cadmould (Cmd) are performed, on two Cmd-database materials, in an equilateral triangular mould cavity, and materials model parameters are estimated/adjusted. The resulting average temperatures at the end of filling are compared, on rays of different angular deviation from the closest corner ray and on different concentric circles, using angular and axial (cavity-halves) symmetry. The greatest differences occur in narrow flow sectors, fatal for our 2D model for a material with non-realistic viscosity model. We present some colour plots, e.g. for the residence time.

    The classical square-root increase by time of the frozen layer is used for extrapolation. It may also be part of the front model in the initial collision with the cold metal mould. An extension of the model is found which describes the radial profile of the frozen layer in the circular plate application accurately also close to the inlet.

    The well-posedness of the corresponding linearized problem is studied, as well as the stability of the linearized FD-scheme.

    Download full text (pdf)
    FULLTEXT01
  • 19. Order onlineBuy this publication >>
    Andersson, Per-Åke
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Multi-year maintenance optimisation for paved public roads - segment based modelling and price-directive decomposition2007Doctoral thesis, monograph (Other academic)
    Abstract [en]

    The thesis deals with the generation of cost efficient maintenance plans for paved roads, based on database information about the current surface conditions and functional models for costs and state changes, partly developed in cooperation with Vägverket (VV, Swedish Road Administration). The intended use is in a stage of budgeting and planning, before concrete project information is available. Unlike the up to now used models, individual maintenance plans can be formulated for each segment (a homogeneous road section as to the current pavement state and paving history), in continuous state and works spaces. By using Lagrangean relaxation optimisation techniques, the special benefit/cost-ratio constraints that VV puts on each maintenance project can be naturally mastered by dual prices for the budget constraints. The number of segments competing for budget resources is usually large. Data from VV Vägdatabank (SRA Road Database) in county Värmland were used, comprising around 9000 road segments. Due to the large data amount the implemented programs rely on parallel computation. During the thesis work, access to the PC-cluster Monolith at NSC was granted. In order to reduce optimisation run times, model & method development was needed. By aggregating the road segments into road classes, good initial values of the dual prices were achieved. By adding new state dimensions, the use of the Markov property could be motivated. By developing a special residual value routine, the explicitly considered time period could be reduced. At solving the dual subproblem special attention was paid to the discretization effects in the dynamic programming approach. One type of study is on a sub-network, e.g. a road. Validation studies were performed on road 63 in Värmland – with promising but not satisfactory results (see below). A special model for co-ordinated maintenance considers the fine-tuned cost effects of simultaneous maintenance of contiguous road segments. The other main type of study is for a whole network. Several method types have been applied, both for solving the relaxed optimisation problems and for generating maintenance plans that fit to the budgets. For a decent discretization, the run time for the whole Värmland network is less than 80 CPU-hrs.A posterior primal heuristics reduces the demands for parallel processing to a small PC-cluster.The thesis further studies the effects of redistributing budget means, as well as turning to a transparent stochastic model – both showing modest deviations from the basic model.

    Optimisation results for Värmland indicate budget levels around 40% of the actual Värmland budget as sufficient. However, important cost triggers are missing in this first model round, e.g., certain functional performance (safety), all environmental performance (noise etc.) and structural performance (e.g. bearing capacity, only modelled by an age measure). For increased credibility of PMS in general and optimisation in particular, the discrepancies should be further analysed and lead to improvements as to condition monitoring, state effect & cost modelling and mathematical modelling & implementation.

    Download full text (pdf)
    FULLTEXT01
  • 20.
    Andersson, Per-Åke
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Multiyear planning of public road maintenance2003In: GOR2003,2003, 2003Conference paper (Other academic)
  • 21.
    Anistratov, Pavel
    et al.
    Linköping University, Department of Electrical Engineering, Vehicular Systems. Linköping University, Faculty of Science & Engineering.
    Olofsson, Björn
    Linköping University, Department of Electrical Engineering, Vehicular Systems. Linköping University, Faculty of Science & Engineering.
    Burdakov, Oleg
    Linköping University, Department of Mathematics, Optimization. Linköping University, Faculty of Science & Engineering.
    Nielsen, Lars
    Linköping University, Department of Electrical Engineering, Vehicular Systems. Linköping University, Faculty of Science & Engineering.
    Autonomous-Vehicle Maneuver Planning Using Segmentation and the Alternating Augmented Lagrangian Method2020In: 21th IFAC World Congress Proceedings / [ed] Rolf Findeisen, Sandra Hirche, Klaus Janschek, Martin Mönnigmann, Elsevier, 2020, Vol. 53, p. 15558-15565Conference paper (Refereed)
    Abstract [en]

    Segmenting a motion-planning problem into smaller subproblems could be beneficial in terms of computational complexity. This observation is used as a basis for a new sub-maneuver decomposition approach investigated in this paper in the context of optimal evasive maneuvers for autonomous ground vehicles. The recently published alternating augmented Lagrangianmethod is adopted and leveraged on, which turns out to fit the problem formulation with several attractive properties of the solution procedure. The decomposition is based on moving the coupling constraints between the sub-maneuvers into a separate coordination problem, which is possible to solve analytically. The remaining constraints and the objective function are decomposed into subproblems, one for each segment, which means that parallel computation is possible and benecial. The method is implemented and evaluated in a safety-critical double lane-change scenario. By using the solution of a low-complexity initialization problem and applying warm-start techniques in the optimization, a solution is possible to obtain after just a few alternating iterations using the developed approach. The resulting computational time is lower than solving one optimization problem for the full maneuver.

    Download full text (pdf)
    fulltext
  • 22.
    Berglund, Per
    et al.
    KTH Royal Institute of Technology, Sweden.
    Dannetun, Per
    Linköping University, University Services.
    Lee Chan, Wai
    Nanyang Technological University, Singapore.
    Gold, Julie
    Chalmers University of Technology, Sweden.
    Han, Sam
    Nanyang Technological University, Singapore.
    Hansson, Heidi
    Umeå University, Sweden.
    Harvey, Simon
    Chalmers University of Technology, Sweden.
    Song Huang, Jun
    National Institute of Education, Singapore.
    Larsson, Ann-Charlotte
    Linnaeus University, Sweden.
    Linton, Steven
    Örebro University, Sweden.
    McInerney, Gerald
    Karolinska Institutet, Sweden.
    Magnell, Marie
    KTH Royal Institute of Technology, Sweden.
    Popov, Oleg
    Umeå University, Sweden.
    Quttineh, Nils-Hassan
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    Richards, Tobias
    University of Borås, Sweden.
    Song, Juha
    Nanyang Technological University, Singapore.
    Switzer, Adam D.
    Nanyang Technological University, Singapore.
    Tegler Jerselius, Kristina
    Swedish Higher Education Authority, Sweden.
    Vikström, Susanne
    Umeå University, Sweden.
    Wikström, Martin
    Royal Swedish Academy of Engineering Sciences, Sweden.
    Trevor Yu, Kang Yang
    Nanyang Technological University, Singapore.
    Yeo, Jesvin Puay-Hwa
    Nanyang Technological University, Singapore.
    Zary, Nabil
    Nanyang Technological University, Singapore.
    Pohl, Hans
    The Swedish Foundation for International Cooperation in Research and Higher Education (STINT), Sweden.
    Ellervik, Ulf
    Lund University, Sweden.
    Linking Education and Research: A Roadmap for Higher Education Institutions at the Dawn of the Knowledge Society2019Other (Other academic)
    Abstract [en]

    In an era characterized by a move towards a “knowledge society”, universities are central in fostering “knowledgeability”, that is the reflexive understanding of knowledge in knowledge societies. The objective of “knowledgeability” can be met through creating a stronger link between education and research. Furthermore, overall student performance, for example in critical thinking and problem solving, can be improved if research-related activities are incorporated into the curriculum. The aim of this paper is to use international examples to discuss the research- education nexus from four different perspectives, namely context, policy, implementation and quality, with case studies from higher education institutions in Singapore and Sweden. We suggest that different integrative technologies can be used to enhance the links, but it will be essential to consider the inputs of training, service and support in using new technology. Interestingly, the act of evaluating the link between education and research will increase awareness of this linkage by stakeholders involved in both education and research. In turn the link can be strengthened, contributing to increased quality in both education and research.

    Download full text (pdf)
    Linking Education and Research: A Roadmap for Higher Education Institutions at the Dawn of the Knowledge Society
  • 23.
    Bergman, Johan
    et al.
    Pepto Systems AB, Stockholm, Sweden.
    Flisberg, Patrik
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Rönnqvist, Mikael
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Roll cutting at paper mills2002In: Proceedings of the Control Systems 2002, 2002, p. 159-163Conference paper (Other academic)
    Abstract [en]

    Roll cutting has attracted a great deal of research attention. However, most of the development of models and methods in academic research has not considered some key industrial requirements. These are practical production aspects that often create non-tractable optimization problems. In this paper, we study two important problems and show how these can be solved efficiently in an industrial setting. These are operative roll cutting where the number of reels and different patterns should be minimized and real-time cutting, when defects and quality restrictions on ordered rolls are included.

  • 24.
    Björk, Kaj-Mikael
    et al.
    Process Design Laboratory, Åbo Akademi University, Åbo, Finland.
    Lindberg, Per Olov
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Westerlund, Tapio
    Process Design Laboratory, Åbo Akademi University, Åbo, Finland.
    Some convexifications in global optimization of problems containing signomial terms2003In: Computers and Chemical Engineering, ISSN 0098-1354, E-ISSN 1873-4375, Vol. 27, no 5, p. 669-679Article in journal (Refereed)
    Abstract [en]

    It is often possible to use different convexification techniques with different transformations in global optimization. In 'Optimization Eng. (submitted for publication)', a new global optimization technique based on convexifying signomial terms is presented. The technique is based on the solution of a sequence of convexified approximate subproblems. The choice of transformation functions is clearly essential. It is not enough to use convexifications that will result in convex and underestimating problems, if an effective optimization approach is wanted. The transformations should be such that they make the resulting problems convex but at the same time do not change the problem more than necessary. It will be shown in this article that for certain problems the choice of transformations has a clear influence on the efficiency of the proposed optimization approach. Using other transformations than what is proposed in 'Optimization Eng. (submitted for publication)' will, in some examples, give solution times that are shorter by an order of magnitude. The concept of power convex functions (Generalized Concavity Optimization Econ. (1981) 153) will be used as a measure of the quality of the transformations. In this paper, the new transformation functions are also shown to be very successful in a heat exchanger network synthesis application. © 2002 Elsevier Science Ltd. All rights reserved.

  • 25.
    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.

  • 26.
    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.

    Download full text (pdf)
    fulltext
  • 27.
    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.

    Download full text (pdf)
    fulltext
  • 28.
    Blomvall, Jörgen
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    A multistage stochastic programming algorithm suitable for parallel computing2003In: Parallel Computing, ISSN 0167-8191, E-ISSN 1872-7336, Vol. 29, no 4, p. 431-445Article in journal (Refereed)
    Abstract [en]

    In [Euro. J. Operat. Res. 143 (2002) 452, Opt. Meth. Software 17 (2002) 383] a Riccati-based primal interior point method for multistage stochastic programmes was developed. This algorithm has several interesting features. It can solve problems with a nonlinear node-separable convex objective, local linear constraints and global linear constraints. This paper demonstrates that the algorithm can be efficiently parallelized. The solution procedure in the algorithm allows for a simple but efficient method to distribute the computations. The parallel algorithm has been implemented on a low-budget parallel computer, where we experience almost perfect linear speedup and very good scalability of the algorithm. © 2003 Elsevier Science B.V. All rights reserved.

  • 29.
    Blomvall, Jörgen
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Optimization based derivative pricing in incomplete and imperfect markets2003In: International Symposium on Mathematical Programming,2003, 2003Conference paper (Other academic)
  • 30.
    Blomvall, Jörgen
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Optimization based derivative pricing in incomplete and imperfect markets2003In: Informs Annual Meeting 2003,2003, 2003Conference paper (Other academic)
  • 31.
    Blomvall, Jörgen
    Linköping University, Department of Mathematics, Optimization. Linköping University, The Institute of Technology.
    Optimization of Financial Decisions using a new Stochastic Programming Method2001Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    The topics of this dissertation are the development of a new Stochastic Programming method and the application of Stochastic Programming in finance. Stochastic Programming is an area within Operations Research that has grown considerably over the last ten years. With new Stochastic Programming methods and more computer resources, Stochastic Programming has become a tool that at least for the moment foremost is used in the financial area. The first contribution in the dissertation is an extensive test of how well one could manage an option portfolio with optimization. When the investment strategy is back tested over a ten year period, the achieved return is much higher than the index even when the increased risk is considered. The second contribution is a new method to solve Stochastic Programming problems. The approach builds on a primal interior point approach. It shows that the resulting subproblems can be efficiently solved with Dynamic Programming. With a parallel implementation of the algorithm we manage to solve very large scale optimization problems with up to 5.8 million scenarios, 102 million variables and 290 million constraints in 80 minutes.

    List of papers
    1. A multistage stochastic programming algorithm suitable for parallel computing
    Open this publication in new window or tab >>A multistage stochastic programming algorithm suitable for parallel computing
    2003 (English)In: Parallel Computing, ISSN 0167-8191, E-ISSN 1872-7336, Vol. 29, no 4, p. 431-445Article in journal (Refereed) Published
    Abstract [en]

    In [Euro. J. Operat. Res. 143 (2002) 452, Opt. Meth. Software 17 (2002) 383] a Riccati-based primal interior point method for multistage stochastic programmes was developed. This algorithm has several interesting features. It can solve problems with a nonlinear node-separable convex objective, local linear constraints and global linear constraints. This paper demonstrates that the algorithm can be efficiently parallelized. The solution procedure in the algorithm allows for a simple but efficient method to distribute the computations. The parallel algorithm has been implemented on a low-budget parallel computer, where we experience almost perfect linear speedup and very good scalability of the algorithm. © 2003 Elsevier Science B.V. All rights reserved.

    Place, publisher, year, edition, pages
    Amsterdam, Netherlands: Elsevier, 2003
    Keywords
    Dynamic programming, Finance, Interior point methods, Parallel computing, Stochastic programming
    National Category
    Engineering and Technology
    Identifiers
    urn:nbn:se:liu:diva-46688 (URN)10.1016/S0167-8191(03)00015-2 (DOI)000182061100005 ()
    Conference
    International Conference on Parallel Computing in Numerical Optimization (ParCo 2001), Naples, Italy, September 2001
    Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2023-12-28Bibliographically approved
    2. A Riccati-based primal interior point solver for multistage stochastic programming - Extensions
    Open this publication in new window or tab >>A Riccati-based primal interior point solver for multistage stochastic programming - Extensions
    2002 (English)In: Optimization Methods and Software, ISSN 1055-6788, E-ISSN 1029-4937, Vol. 17, no 3, p. 383-407Article in journal (Refereed) Published
    Abstract [en]

    We show that a Riccati-based Multistage Stochastic Programming solver for problems with separable convex linear/nonlinear objective developed in previous papers can be extended to solve more general Stochastic Programming problems. With a Lagrangean relaxation approach, also local and global equality constraints can be handled by the Riccati-based primal interior point solver. The efficiency of the approach is demonstrated on a 10 staged stochastic programming problem containing both local and global equality constraints. The problem has 1.9 million scenarios, 67 million variables and 119 million constraints, and was solved in 97 min on a 32 node PC cluster.

    Place, publisher, year, edition, pages
    Oxfordshire, United Kingdom: Taylor & Francis, 2002
    Keywords
    interior point methods, parallel computations, stochastic programming
    National Category
    Engineering and Technology
    Identifiers
    urn:nbn:se:liu:diva-47857 (URN)10.1080/1055678021000033946 (DOI)000178077900002 ()
    Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2023-12-28Bibliographically approved
    3. A Riccati-based primal interior point solver for multistage stochastic programming
    Open this publication in new window or tab >>A Riccati-based primal interior point solver for multistage stochastic programming
    2002 (English)In: European Journal of Operational Research, ISSN 0377-2217, E-ISSN 1872-6860, Vol. 143, no 2, p. 452-461Article in journal (Refereed) Published
    Abstract [en]

    We propose a new method for certain multistage stochastic programs with linear or nonlinear objective function, combining a primal interior point approach with a linear-quadratic control problem over the scenario tree. The latter problem, which is the direction finding problem for the barrier subproblem is solved through dynamic programming using Riccati equations. In this way we combine the low iteration count of interior point methods with an efficient solver for the subproblems. The computational results are promising. We have solved a financial problem with 1,000,000 scenarios, 15,777,740 variables and 16,888,850 constraints in 20 hours on a moderate computer. © 2002 Elsevier Science B.V. All rights reserved.

    Place, publisher, year, edition, pages
    Amsterdam, Netherlands: Elsevier, 2002
    Keywords
    Dynamic programming, Finance, Interior point methods, Stochastic programming
    National Category
    Engineering and Technology
    Identifiers
    urn:nbn:se:liu:diva-46814 (URN)10.1016/S0377-2217(02)00301-6 (DOI)000178249600016 ()
    Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2023-12-28Bibliographically approved
  • 32.
    Blomvall, Jörgen
    et al.
    Linköping University, Department of Management and Engineering, Production Economics. Linköping University, The Institute of Technology.
    Ekblom, Jonas
    Linköping University, Department of Management and Engineering, Production Economics. Linköping University, The Institute of Technology.
    Ndengo, Marcel
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Estimating U.S. Treasury Yield Curves By A Generalized Optimization FrameworkManuscript (preprint) (Other academic)
    Abstract [en]

    We show that traditional data sets for the U.S. Treasury yield curves contain large amounts of noise, in e.g. the Fama-Bliss discount file already the second factor loading for innovations in forward rates is a consequence of noise. We implement the quadratic and cubic McCulloch splines, Nelson-Siegel and Svensson models and compare these traditional models with a recently developed generalized optimization framework using daily CRSP data from 1961 to 2011. In out-of-sample tests, it is shown that the generalized optimization framework produces smaller pricing errors compared to the traditional methods. Factor loadings from the generalized optimization framework show that the short and long end of the forward rate curve move independently, where principal component 1-3 explain the long end, and subsequent principal components explain the short end. This is consistent with the behavior of the market where short rates are governed by central bank while long rates are dependent on e.g. the expectation of future inflation.

  • 33.
    Blomvall, Jörgen
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Henningsson, Mathias
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    AN INTRODUCTORY PROJECT IN FINANCIAL ENGINEERING2008In: 4th International CDIO Conference,2008, 2008Conference paper (Other academic)
    Abstract [en]

      

  • 34.
    Blomvall, Jörgen
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Lindberg, Per Olov
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    A Riccati-based primal interior point solver for multistage stochastic programming2002In: European Journal of Operational Research, ISSN 0377-2217, E-ISSN 1872-6860, Vol. 143, no 2, p. 452-461Article in journal (Refereed)
    Abstract [en]

    We propose a new method for certain multistage stochastic programs with linear or nonlinear objective function, combining a primal interior point approach with a linear-quadratic control problem over the scenario tree. The latter problem, which is the direction finding problem for the barrier subproblem is solved through dynamic programming using Riccati equations. In this way we combine the low iteration count of interior point methods with an efficient solver for the subproblems. The computational results are promising. We have solved a financial problem with 1,000,000 scenarios, 15,777,740 variables and 16,888,850 constraints in 20 hours on a moderate computer. © 2002 Elsevier Science B.V. All rights reserved.

  • 35.
    Blomvall, Jörgen
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Lindberg, Per Olov
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    A Riccati-based primal interior point solver for multistage stochastic programming - Extensions2002In: Optimization Methods and Software, ISSN 1055-6788, E-ISSN 1029-4937, Vol. 17, no 3, p. 383-407Article in journal (Refereed)
    Abstract [en]

    We show that a Riccati-based Multistage Stochastic Programming solver for problems with separable convex linear/nonlinear objective developed in previous papers can be extended to solve more general Stochastic Programming problems. With a Lagrangean relaxation approach, also local and global equality constraints can be handled by the Riccati-based primal interior point solver. The efficiency of the approach is demonstrated on a 10 staged stochastic programming problem containing both local and global equality constraints. The problem has 1.9 million scenarios, 67 million variables and 119 million constraints, and was solved in 97 min on a 32 node PC cluster.

  • 36.
    Blomvall, Jörgen
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Lindberg, Per Olov
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Back-testing the performance of an actively managed option portfolio at the Swedish Stock Market, 1990–19992003In: Journal of Economic Dynamics and Control, ISSN 0165-1889, E-ISSN 1879-1743, Vol. 27, no 6, p. 1099-1112Article in journal (Refereed)
    Abstract [en]

    We build an investment model based on Stochastic Programming. In the model we buy at the ask price and sell at the bid price. We apply the model to a case where we can invest in a Swedish stock index, call options on the index and the risk-free asset. By reoptimizing the portfolio on a daily basis over a ten-year period, it is shown that options can be used to create a portfolio that outperforms the index. With ex post analysis, it is furthermore shown that we can create a portfolio that dominates the index in terms of mean and variance, i.e. at given level of risk we could have achieved a higher return using options.

  • 37.
    Blomvall, Jörgen
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Manzano, Julian
    Positive forward rates in the maximum smoothness framework2004In: Quantitative finance (Print), ISSN 1469-7688, E-ISSN 1469-7696, Vol. 4, no 2, p. 221-232Article in journal (Refereed)
    Abstract [en]

    In this paper we present a nonlinear dynamic programming algorithm for the computation of forward rates within the maximum smoothness framework. The algorithm implements the forward rate positivity constraint for a one-parametric family of smoothness measures and it handles price spreads in the constraining data set. We investigate the outcome of the algorithm using the Swedish Bond market showing examples where the absence of the positive constraint leads to negative interest rates. Furthermore we investigate the predictive accuracy of the algorithm as we move along the family of smoothness measures. Among other things we observe that the inclusion of spreads not only improves the smoothness of forward curves but also significantly reduces the predictive error.

  • 38.
    Blomvall, Jörgen
    et al.
    Linköping University, Department of Management and Engineering, Production Economics. Linköping University, The Institute of Technology.
    Ndengo, Marcel
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    High Quality Yield Curves from a Generalized Optimization FrameworkManuscript (preprint) (Other academic)
    Abstract [en]

    Traditional methods for estimating yield curves are special cases of a generalized optimization framework. For pricing out-of-sample in both the Swedish and U.S. interest rate swap (IRS) markets, it is shown that the framework dominates or is close to dominating the traditional methods in the comparison by first order stochastic dominance. When measuring the perceived variance for each traditional method, it is shown that, for the same level of market consistency, the framework produces lower variance. For these new yield curves, PCA of innovations in forward rates shows that the first three loadings (shift, twist and butterfly) do not explain movements in the short end, and that the subsequent loadings explain uncorrelated movements in the short end.

  • 39.
    Blomvall, Jörgen
    et al.
    Linköping University, Department of Management and Engineering, Production Economics. Linköping University, The Institute of Technology.
    Ndengo, Marcel
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Multiple Yield Curves Estimation Using A Generalized Optimization FrameworkManuscript (preprint) (Other academic)
    Abstract [en]

    After the credit crunch which started in 2007, significant basis spreads for exchanging floating payments of different tenors appeared. To deal with the problem, multiple yield curves estimation methods have been suggested. In this paper, a generalized optimization framework is extended to a multiple yield curve framework. As has been observed by practitioners, extending traditional cubic splines to multiple yield curves, though consistent with the market prices, does not provide smooth and realistic yield curves. When the parameters in the generalized optimization framework are selected to exactly match market prices, the yield curves are much more realistic, but small waves still remain due to noise in the input data. To avoid having a rough yield curve, we also study the least squares parameter setting in the generalized optimization framework. This method gives much smoother and more realistic yield curves with adjustments to market prices that are less than 0.2 basis points. When exact traditional methods are extended to estimate multiple yield curves, then even tiny pricing errors can cause a situation where the shape constraints prevent the method from finding realistic yield curves.

  • 40.
    Blomvall, Jörgen
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Shapiro, A.
    School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205, United States.
    Solving multistage asset investment problems by the sample average approximation method2006In: Mathematical programming, ISSN 0025-5610, E-ISSN 1436-4646, Vol. 108, no 2-3, p. 571-595Article in journal (Refereed)
    Abstract [en]

    The vast size of real world stochastic programming instances requires sampling to make them practically solvable. In this paper we extend the understanding of how sampling affects the solution quality of multistage stochastic programming problems. We present a new heuristic for determining good feasible solutions for a multistage decision problem. For power and log-utility functions we address the question of how tree structures, number of stages, number of outcomes and number of assets affect the solution quality. We also present a new method for evaluating the quality of first stage decisions.

  • 41.
    Boberg, Jessika
    Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.
    A comparison of sequencing formulations in a constraint generation procedure for avionics scheduling2017Independent thesis Basic level (degree of Bachelor), 10,5 credits / 16 HE creditsStudent thesis
    Abstract [en]

    This thesis compares different mixed integer programming (MIP) formulations for sequencing of tasks in the context of avionics scheduling. Sequencing is a key concern in many discrete optimisation problems, and there are numerous ways of accomplishing sequencing with different MIP formulations. A scheduling tool for avionic systems has previously been developed in a collaboration between Saab and Linköping University. This tool includes a MIP formulation of the scheduling problem where one of the model components has the purpose to sequence tasks. In this thesis, this sequencing component is replaced with other MIP formulations in order to study whether the computational performance of the scheduling tool can be improved. Different scheduling instances and objective functions have been used when performing the tests aiming to evaluate the performances, with the computational times of the entire avionic scheduling model determining the success of the different MIP formulations for sequencing. The results show that the choice of MIP formulation makes a considerable impact on the computational performance and that a significant improvement can be achieved by choosing the most suitable one.

    Download full text (pdf)
    fulltext
  • 42.
    Bredström, David
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Models and solution methods for large-scale industrial mixed integer programming problems2007Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    This thesis deals with large-scale industrial problems that can be formulated using mixed integer linear programming (MIP) models. Because of the large problem size, it is not often possible to apply standard solution methods. Therefore special techniques must be used. In this thesis, both full optimization and optimization based heuristic approaches are developed.

    The body of this thesis consists of five research papers. In the papers we consider industrial cases based on three applications: production planning at Södra Cell AB, ship routing and distribution at Södra Cell AB, and staff routing and scheduling in the Swedish home care.

    We develop two large-scale MIP models for the production-planning problem. For solving, we use both a direct approach, and a combination of column generation and constraint branching. The latter is a technique to control the branching rules in a branch and bound framework and takes into account application specific properties.

    For the ship routing problem, we present a MIP model and develop two solution methods. The first is based on an iterative rolling time horizon. In each step a part of the model is solved and later fixed. This is repeated until the full problem is solved. The second approach is to combine a genetic algorithm and linear programming. From the MIP model, we obtain solution bounds rarely present in genetic algorithm frameworks.

    In the staff routing problem there are special synchronization constraints and we introduce a new MIP model. An exact solution approach based on column generation and branch and bound is developed. We also suggest a variable fixing heuristic, which we use for solving the more general problem with requirements on equal workload.

    In the computational experiments, we use data instances obtained from real-world cases, and generated instances based on real-world cases. The numerical results show that high quality solutions can be obtained within reasonable time limits in all applications.

    List of papers
    1. Combined vehicle routing and scheduling with temporal precedence and synchronization constraints
    Open this publication in new window or tab >>Combined vehicle routing and scheduling with temporal precedence and synchronization constraints
    2006 (English)In: EconPapers, Vol. 18Article in journal (Other academic) Published
    Abstract [en]

    We present a mathematical programming model for the combined vehicle routing and scheduling problem with time windows and additional temporal constraints. The temporal constraints allow for imposing pairwise synchronization and pairwise temporal precedence between customer visits, independently of the vehicles. We describe some real world problems where the temporal constraints, in the literature, usually are remarkably simplified in the solution process, even though these constraints may significantly improve the solution quality and/or usability. We also propose an optimization based heuristic to solve real size instances. The results of numerical experiments substantiate the importance of the temporal constraints in the solution approach. We also make a computational study by comparing a direct usage of a commercial solver against the proposed heuristic where the latter approach can find high quality solutions within distinct time limits.

    Keywords
    Routing; Scheduling; Temporal Constraints; Synchronization; Branch and Bound
    National Category
    Engineering and Technology
    Identifiers
    urn:nbn:se:liu:diva-13128 (URN)
    Available from: 2008-04-02 Created: 2008-04-02 Last updated: 2009-02-17
    2. A branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints
    Open this publication in new window or tab >>A branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints
    2007 (English)In: Social Science Research Network, Vol. 7Article in journal (Refereed) Published
    Abstract [en]

    In this paper we present a branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints. The synchronization constraints are used to model situations when two or more customers need simultaneous service. The synchronization constraints impose a temporal dependency between vehicles, and it follows that a classical decomposition of the vehicle routing and scheduling problem is not directly applicable. With our algorithm, we have solved 44 problems to optimality from the 60 problems used for numerical experiments. The algorithm performs time window branching, and the number of subproblem calls is kept low by adjustment of the columns service times.

    Keywords
    Routing, Scheduling, Synchronization, Branch and Price
    National Category
    Mathematics
    Identifiers
    urn:nbn:se:liu:diva-13129 (URN)
    Available from: 2008-04-02 Created: 2008-04-02 Last updated: 2009-04-15
    3. Supply chain optimization in the pulp mill industry: IP models, column generation and novel constraint branches
    Open this publication in new window or tab >>Supply chain optimization in the pulp mill industry: IP models, column generation and novel constraint branches
    Show others...
    2004 (English)In: European Journal of Operational Research, ISSN 0377-2217, Vol. 156, no 1, p. 2-22Article in journal (Refereed) Published
    Abstract [en]

    We study the supply chain problem of a large international pulp producer with five pulp mills located in Scandinavia. The company currently uses manual planning for most of its supply chain, which includes harvesting and transportation of pulp, production scheduling and distribution of products to customers. We have developed two new mixed integer models that determine daily supply chain decisions over a planning horizon of three months. One model is based on column generation, where the generation phase is to find new production plans using a shortest path network. The second, slightly less flexible, has the daily production decisions explicitly included in the model. In order to solve the models within practical time limits we use a flexible approach that aggregates together the less immediate decisions. We also introduce a novel constraint branching heuristic. The models and solution approaches are intended to become an integrated component in the company’s new management system. In tests and comparisons with today’s manual planning, we have found new strategic policies that significantly reduce the company’s supply chain costs.

    Keywords
    Branch and bound, Integer programming, Production, Scheduling, Supply chain management
    National Category
    Mathematics
    Identifiers
    urn:nbn:se:liu:diva-13130 (URN)10.1016/j.ejor.2003.08.001 (DOI)
    Available from: 2008-04-02 Created: 2008-04-02 Last updated: 2013-11-05
    4. Supply chain optimization in pulp distribution using a rolling horizon solution approach
    Open this publication in new window or tab >>Supply chain optimization in pulp distribution using a rolling horizon solution approach
    2006 (English)Report (Other academic)
    Abstract [en]

    In this paper we consider a combined supply chain and ship routing problem for a large pulp producer in Scandinavia. The problem concerns the distribution of pulp to customers, with route scheduling of ships as a central part of modeling. It is an operative planning problem with daily ship routing decisions over a 40 days period. The pulp supply is determined by fixed production plans, and the transport flows and storages are modeled with the requirement to satisfy the demand in a cost-optimal way. We develop a mixed integer programming model with binary variables for route usage of a vessel.

    The problem is solved with a heuristic solution method, based on a rolling time horizon and a standard branch and bound algorithm. We apply the heuristic on problem instances with real world data, and compare results from reduced problem instances with the results from an exact branch and bound search. The computational experiments indicate that real world problems are solvable with the solution method and that it in many cases can be very effcient.

     

    Series
    LiTH-MAT-R ; 2003-25
    Keywords
    Supply chain, Ships, Scheduling, Mixed integer programming
    National Category
    Mathematics
    Identifiers
    urn:nbn:se:liu:diva-13131 (URN)
    Available from: 2008-04-02 Created: 2008-04-02 Last updated: 2013-11-05
    5. A hybrid algorithm for a pulp distribution problem
    Open this publication in new window or tab >>A hybrid algorithm for a pulp distribution problem
    2005 (English)In: IEEE Intelligent Systems, ISSN 1541-1672, Vol. 20, no 4, p. 19-25Article in journal (Refereed) Published
    Abstract [en]

    Distribution is a major factor in the supply chain for Sodra Cell, a leading manufacturer of pulp intended for paper production. Each year, the company transports large quantities of pulp using ships, trains, and trucks; here we focus on scheduling the ships and optimizing deliveries to minimize distribution costs.

    National Category
    Engineering and Technology
    Identifiers
    urn:nbn:se:liu:diva-13132 (URN)10.1109/MIS.2005.59 (DOI)
    Available from: 2008-04-02 Created: 2008-04-02 Last updated: 2015-12-29
  • 43.
    Bredström, David
    Linköping University, Department of Mathematics, Optimization. Linköping University, The Institute of Technology.
    Optimization models and methods for production planning and ship scheduling in the pulp industry2003Licentiate thesis, comprehensive summary (Other academic)
    Abstract [en]

    To use optimization models and methods is an increasingly acknowledged element of supply chain management for large industries. Concurrently with the increasing global market competition and modern business policies, an already effective organization needs to find new possibilities to improve their planning procedures and resource utilization. To incorporate the planning in a more comprehensive context, in an overall supply chain, provides new possibilities to efficiently manage several planning steps than if considered individually.

    This thesis considers production planning and ship scheduling problems at Södra Cell, a large Scandinavian pulp manufacturer. The main purpose of the thesis is to suggest optimization models and methods that can support production and distribution planners to objectively consider the supply chain impact in the short-term decision making process. The production planning and the ship scheduling problems are approached separately. Optimization models are formulated for both problems, and specially adapted solution methods are developed that account the characteristics of the problems.

    The thesis consists of three research papers. In the first paper two mixed integer models (MIPs) are developed for the production planning problem. The first model has binary variables for every possible production plan and a column generation approach with a constraint branching heuristic is used to solve the otherwise very large model. The second model has the production choices formulated in constraints and is solved with a standard branch and bound search. The results are compared with manual planning and potential large savings are indicated.

    The second and the third paper both consider the pulp distribution problem where ship routing and scheduling decisions have a key role. In the second paper the problem is solved with a rolling time horizon method. An MIP model is solved repeatedly over short ranges of time until eventually the whole planning period is covered. The third paper presents a genetic algorithm with integrated linear programming models for the distribution problem. The solutions from the different solution strategies for the distribution problem are mutually compared in the third paper.

    List of papers
    1. Supply chain optimization in the pulp mill industry: IP models, column generation and novel constraint branches
    Open this publication in new window or tab >>Supply chain optimization in the pulp mill industry: IP models, column generation and novel constraint branches
    Show others...
    2004 (English)In: European Journal of Operational Research, ISSN 0377-2217, Vol. 156, no 1, p. 2-22Article in journal (Refereed) Published
    Abstract [en]

    We study the supply chain problem of a large international pulp producer with five pulp mills located in Scandinavia. The company currently uses manual planning for most of its supply chain, which includes harvesting and transportation of pulp, production scheduling and distribution of products to customers. We have developed two new mixed integer models that determine daily supply chain decisions over a planning horizon of three months. One model is based on column generation, where the generation phase is to find new production plans using a shortest path network. The second, slightly less flexible, has the daily production decisions explicitly included in the model. In order to solve the models within practical time limits we use a flexible approach that aggregates together the less immediate decisions. We also introduce a novel constraint branching heuristic. The models and solution approaches are intended to become an integrated component in the company’s new management system. In tests and comparisons with today’s manual planning, we have found new strategic policies that significantly reduce the company’s supply chain costs.

    Keywords
    Branch and bound, Integer programming, Production, Scheduling, Supply chain management
    National Category
    Mathematics
    Identifiers
    urn:nbn:se:liu:diva-13130 (URN)10.1016/j.ejor.2003.08.001 (DOI)
    Available from: 2008-04-02 Created: 2008-04-02 Last updated: 2013-11-05
    2. Supply chain optimization in pulp distribution using a rolling horizon solution approach
    Open this publication in new window or tab >>Supply chain optimization in pulp distribution using a rolling horizon solution approach
    2006 (English)Report (Other academic)
    Abstract [en]

    In this paper we consider a combined supply chain and ship routing problem for a large pulp producer in Scandinavia. The problem concerns the distribution of pulp to customers, with route scheduling of ships as a central part of modeling. It is an operative planning problem with daily ship routing decisions over a 40 days period. The pulp supply is determined by fixed production plans, and the transport flows and storages are modeled with the requirement to satisfy the demand in a cost-optimal way. We develop a mixed integer programming model with binary variables for route usage of a vessel.

    The problem is solved with a heuristic solution method, based on a rolling time horizon and a standard branch and bound algorithm. We apply the heuristic on problem instances with real world data, and compare results from reduced problem instances with the results from an exact branch and bound search. The computational experiments indicate that real world problems are solvable with the solution method and that it in many cases can be very effcient.

     

    Series
    LiTH-MAT-R ; 2003-25
    Keywords
    Supply chain, Ships, Scheduling, Mixed integer programming
    National Category
    Mathematics
    Identifiers
    urn:nbn:se:liu:diva-13131 (URN)
    Available from: 2008-04-02 Created: 2008-04-02 Last updated: 2013-11-05
    3. A genetic algorithm for a pulp distribution problem
    Open this publication in new window or tab >>A genetic algorithm for a pulp distribution problem
    2003 (English)Report (Other academic)
    Abstract [en]

    In this paper we present a genetic algorithm for the pulp distribution problem at a large pulp producer in Scandinavia. The distribution is a major part of the company's supply chain and includes transports with cargo vessels, by train and trucks and storages at terminals in port, at pulp mills and in customer locations. The problem we focus on is to find ship schedules and pulp deliveries in order to minimize the total cost of distribution.

    The genetic algorithm utilizes two linear programming models. The first model optimizes all transport flows given a schedule and the second model approximates the performance of a schedule, measured in the total distribution cost. In the computational experiments we use instances from the real world and compare the results with an exact mixed integer programming approach.

    Place, publisher, year, edition, pages
    Linköping: Linköpings universitet, 2003. p. 21
    Series
    LiTH-MAT-R, ISSN 0348-2960 ; 26
    National Category
    Mathematics
    Identifiers
    urn:nbn:se:liu:diva-22364 (URN)1572 (Local ID)1572 (Archive number)1572 (OAI)
    Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2013-11-05
  • 44.
    Bredström, David
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Carlsson, Dick
    Södra Cell AB, Växjö, Sweden.
    Lundgren, Jan T.
    Linköping University, Department of Science and Technology. Linköping University, The Institute of Technology.
    Mason, Andrew
    Department of Engineering Science, The University of Auckland, Auckland, New Zealand.
    Rönnqvist, Mikael
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Supply chain optimization in the pulp mill industry: IP models, column generation and novel constraint branches2004In: European Journal of Operational Research, ISSN 0377-2217, Vol. 156, no 1, p. 2-22Article in journal (Refereed)
    Abstract [en]

    We study the supply chain problem of a large international pulp producer with five pulp mills located in Scandinavia. The company currently uses manual planning for most of its supply chain, which includes harvesting and transportation of pulp, production scheduling and distribution of products to customers. We have developed two new mixed integer models that determine daily supply chain decisions over a planning horizon of three months. One model is based on column generation, where the generation phase is to find new production plans using a shortest path network. The second, slightly less flexible, has the daily production decisions explicitly included in the model. In order to solve the models within practical time limits we use a flexible approach that aggregates together the less immediate decisions. We also introduce a novel constraint branching heuristic. The models and solution approaches are intended to become an integrated component in the company’s new management system. In tests and comparisons with today’s manual planning, we have found new strategic policies that significantly reduce the company’s supply chain costs.

  • 45.
    Bredström, David
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Rönnqvist, Mikael
    Norwegian School of Economics and Business Administration (NHH), Bergen, Norway.
    A branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints2007In: Social Science Research Network, Vol. 7Article in journal (Refereed)
    Abstract [en]

    In this paper we present a branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints. The synchronization constraints are used to model situations when two or more customers need simultaneous service. The synchronization constraints impose a temporal dependency between vehicles, and it follows that a classical decomposition of the vehicle routing and scheduling problem is not directly applicable. With our algorithm, we have solved 44 problems to optimality from the 60 problems used for numerical experiments. The algorithm performs time window branching, and the number of subproblem calls is kept low by adjustment of the columns service times.

  • 46.
    Bredström, David
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Rönnqvist, Mikael
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    A genetic algorithm for a pulp distribution problem2003Report (Other academic)
    Abstract [en]

    In this paper we present a genetic algorithm for the pulp distribution problem at a large pulp producer in Scandinavia. The distribution is a major part of the company's supply chain and includes transports with cargo vessels, by train and trucks and storages at terminals in port, at pulp mills and in customer locations. The problem we focus on is to find ship schedules and pulp deliveries in order to minimize the total cost of distribution.

    The genetic algorithm utilizes two linear programming models. The first model optimizes all transport flows given a schedule and the second model approximates the performance of a schedule, measured in the total distribution cost. In the computational experiments we use instances from the real world and compare the results with an exact mixed integer programming approach.

  • 47.
    Bredström, David
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Rönnqvist, Mikael
    Norwegian School of Economics and Business Administration, Bergen.
    Combined vehicle routing and scheduling with temporal precedence and synchronization constraints2006In: EconPapers, Vol. 18Article in journal (Other academic)
    Abstract [en]

    We present a mathematical programming model for the combined vehicle routing and scheduling problem with time windows and additional temporal constraints. The temporal constraints allow for imposing pairwise synchronization and pairwise temporal precedence between customer visits, independently of the vehicles. We describe some real world problems where the temporal constraints, in the literature, usually are remarkably simplified in the solution process, even though these constraints may significantly improve the solution quality and/or usability. We also propose an optimization based heuristic to solve real size instances. The results of numerical experiments substantiate the importance of the temporal constraints in the solution approach. We also make a computational study by comparing a direct usage of a commercial solver against the proposed heuristic where the latter approach can find high quality solutions within distinct time limits.

  • 48.
    Bredström, David
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Rönnqvist, Mikael
    Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .
    Ship routing and scheduling in the pulp mill industry2003In: 18th International Symposium on Mathematical Programming,2003, 2003Conference paper (Other academic)
  • 49.
    Bredström, David
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Rönnqvist, Mikael
    Norwegian School of Economics and Business Administration, Bergen.
    Supply chain optimization in pulp distribution using a rolling horizon solution approach2006Report (Other academic)
    Abstract [en]

    In this paper we consider a combined supply chain and ship routing problem for a large pulp producer in Scandinavia. The problem concerns the distribution of pulp to customers, with route scheduling of ships as a central part of modeling. It is an operative planning problem with daily ship routing decisions over a 40 days period. The pulp supply is determined by fixed production plans, and the transport flows and storages are modeled with the requirement to satisfy the demand in a cost-optimal way. We develop a mixed integer programming model with binary variables for route usage of a vessel.

    The problem is solved with a heuristic solution method, based on a rolling time horizon and a standard branch and bound algorithm. We apply the heuristic on problem instances with real world data, and compare results from reduced problem instances with the results from an exact branch and bound search. The computational experiments indicate that real world problems are solvable with the solution method and that it in many cases can be very effcient.

     

  • 50.
    Bredström, David
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Rönnqvist, Mikael
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Carlsson, Dick
    A hybrid algorithm for a pulp distribution problem2005In: IEEE Intelligent Systems, ISSN 1541-1672, Vol. 20, no 4, p. 19-25Article in journal (Refereed)
    Abstract [en]

    Distribution is a major factor in the supply chain for Sodra Cell, a leading manufacturer of pulp intended for paper production. Each year, the company transports large quantities of pulp using ships, trains, and trucks; here we focus on scheduling the ships and optimizing deliveries to minimize distribution costs.

1234567 1 - 50 of 379
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • 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