Search

In this paper, we study a mixed-integer programming model of the single-level multi-item capacitated lot-sizing problem (MCLSP), which incorporates shared capacity on the production of items for each period throughout a planning horizon. We derive valid bounds on the partial objective function of the MCLSP formulation by solving the first t periods of the problem over a subset of all items, using dynamic programming and integer programming techniques. We also develop algorithms for strengthening these valid inequalities by back-lifting techniques. These inequalities can be utilized within a cutting-plane algorithm, in which we perturb the partial objective function coefficients to identify violated inequalities to the MCLSP polytope. Our computational results show that the envelope inequalities are very effective for the MCLSP instances with different capacity and cost characteristics, when compared to the (l, S) inequalities.

Controlling invasive species is a highly complex problem. The intricacy of the problem stems from the nonlinearity that is inherent in biological systems, consequently impeding researchers to obtain timely and cost-efficient treatment strategies over a planning horizon. To cope with the complexity of the invasive species problem, we develop a mixed-integer programming (MIP) model that handles the problem as a full dynamic optimization model and solves it to optimality for the first time. We demonstrate the applicability of the model on a case study of sericea ( Lespedeza cuneata ) infestation by optimizing a spatially explicit model on a heterogeneous 10-by-10 grid landscape for a seven-year time period. We evaluate the solution quality of five different linearization methods that are used to obtain the MIP model. We also compare the model with its mixed-integer nonlinear programming (MINLP) equivalent and nonlinear programming (NLP) relaxation in terms of solution quality. The computational superiority and realism of the proposed MIP model demonstrate that our model has the potential to constitute the basis for future decision-support tools in invasive species management.

Invasive species cause large economic losses and are difficult to control due to the high cost of locating and treating the continual emergence of new individuals. The national strategy against invasive species encompasses prevention, early detection, and rapid response. In particular, determining an optimal route for search and treatment under limited budget is critical to reducing management costs. In this paper, we present a new integrated simulation-optimization framework to effectively search and treat invasive species under a limited management budget. The simulation mimics invader growth over a landscape and 12 years, while a bio-economic optimization model finds an optimal search and treatment path to minimize its economic damage to agricultural production. Our optimization model is new in the sense that it prescribes the optimal path for searching and treating sites for controlling the invader. This study is also the first in the literature to present and combine simulation and optimization models of the complex bio-economic search-path problem, and to prescribe a pathway for search and treatment that is applicable to the real-world management of invasive species. Our case study data and parameter calibration are based on the large-scale field data on Sericea, an aggressive invasive plant threatening the Great Plains of the U.S., collected over twelve pastures in Kansas during the past two years. Solving simulation and optimization models in a consecutive fashion provides a considerable computational advantage to find an optimal solution to practical size problems in a reasonable time. Our results imply that applying yearly treatment with a slow search-and-treatment speed results in the biggest bang for the buck under most invasion scenarios.

This paper provides a new idea for approximating the inventory cost function to be used in a truncated dynamic program for solving the capacitated lot-sizing problem. The proposed method combines dynamic programming with regression, data fitting, and approximation techniques to estimate the inventory cost function at each stage of the dynamic program. The effectiveness of the proposed method is analyzed on various types of the capacitated lot-sizing problem instances with different cost and capacity characteristics. Computational results show that approximation approaches could significantly decrease the computational time required by the dynamic program and the integer program for solving different types of the capacitated lot-sizing problem instances. Furthermore, in most cases, the proposed approximate dynamic programming approaches can accurately capture the optimal solution of the problem with consistent computational performance over different instances.

The parallel replacement problem under economies of scale (PRES) determines minimum cost replacement policies for each asset in a group of assets that operate in parallel and are subject to fixed and variable purchase costs. We study the mixed-integer programming formulation of PRES under technological change by incorporating capacity gains into the model such that newer, technologically advanced assets have higher capacity than assets purchased earlier. We provide optimal solution characteristics and insights about the economics of the problem and derive associated cutting planes for optimising the problem. Computational experiments illustrate that the inequalities are quite effective in solving PRES under technological change instances.

In this paper, we formulate and analyse a long-term multi-objective dynamic model for controlling invasive species. This optimization framework is then applied to the case of buffelgrass control in the Arizona desert. The proposed model simultaneously optimizes three objectives corresponding to three different valued and threatened resources including saguaros (a native cactus species), buildings and vegetation. The model is used to decide the optimal allocation of labour to these resources to control the population of the species in a multi-period planning horizon. The computational method to solve this problem is based on multi-objective integer programming.

The parallel replacement problem under economies of scale (PRES) determines minimum cost replacement schedules for each individual asset in a group of assets that operate in parallel. A fixed cost is incurred in any period in which an asset is purchased. These fixed costs induce economies of scale, making replacement schedules for these assets economically interdependent. We prove that PRES is NP-hard and present integer programming formulations for four variants of the problem in which multiple asset types, or challengers, are available for replacement (MPRES). We then derive valid inequalities for PRES and MPRES, which are similar in structure to flow cover inequalities developed in the context of fixed charge network problems. Experiments illustrate that the inequalities are effective in improving the integrality gap of MPRES instances.

A dynamic model of controlling invasive weeds is first developed which is a large scale, nonlinear 0-1 integer programming problem. This model is then applied for the case of control of the invasive grass, Pennisetum ciliare (buffelgrass), in the Arizona desert. The large size of the problem makes the application of direct optimization methods impossible, instead the most frequently suggested strategies were analyzed and their consequences compared. The model is more advanced and complex than those examined in earlier studies.

Iterative solutions of forward dynamic programming formulations for the capacitated lot sizing problem are used to generate inequalities for an equivalent integer programming formulation. The inequalities capture convex and concave envelopes of intermediate-stage value functions and can be lifted by examining potential state information at future stages. Several possible implementations that employ these inequalities are tested and it is demonstrated that the proposed approach is more efficient than alternative integer programming–based algorithms. For certain datasets, the proposed algorithm also outperforms a pure dynamic programming algorithm for the problem.