Selecting Portfolios with Fixed Costs and Minimum Transaction Lots

The original Markowitz model of portfolio selection has received a widespread theoretical acceptance and it has been the basis for various portfolio selection techniques. Nevertheless, this normative model has found relatively little application in practice when some additional features, such as fixed costs and minimum transaction lots, are relevant in the portfolio selection problem. In this paper different mixed-integer linear programming models dealing with fixed costs and possibly minimum lots are introduced. Due to the high computational complexity of the models, heuristic procedures, based on the construction and optimal solution of mixed integer subproblems, are proposed. Computational results obtained using data from the Milan Stock Exchange show how the proposed heuristics yield very good solutions in a short computational time and make possible some interesting financial conclusions on the impact of fixed costs and minimum lots on portfolio composition.     

An integrated model for lot sizing with supplier selection and quantity discounts

Good inventory management is essential for a firm to be cost competitive and to acquire decent profit in the market, and how to achieve an outstanding inventory management has been a popular topic in both the academic field and in real practice for decades. As the production environment getting increasingly complex, various kinds of mathematical models have been developed, such as linear programming, nonlinear programming, mixed integer programming, geometric programming, gradient-based nonlinear programming and dynamic programming, to name a few. However, when the problem becomes NP-hard, heuristics tools may be necessary to solve the problem. In this paper, a mixed integer programming (MIP) model is constructed first to solve the lot-sizing problem with multiple suppliers, multiple periods and quantity discounts. An efficient Genetic Algorithm (GA) is proposed next to tackle the problem when it becomes too complicated. The objectives are to minimize total costs, where the costs include ordering cost, holding cost, purchase cost and transportation cost, under the requirement that no inventory shortage is allowed in the system, and to determine an appropriate inventory level for each planning period. The results demonstrate that the proposed GA model is an effective and accurate tool for determining the replenishment for a manufacturer for multi-periods.     

Optimization Models for Forest Road Upgrade Planning

Road blocking due to thawing or heavy rains annually contribute to a considerable loss in Swedish forestry. Companies are forced to build up large stocks of raw material (saw and pulp logs) in order to secure a continuous supply when access to the road network is uncertain. Storage outdoors leads to quality deterioration and monetary losses. Other related costs due to road blocking are road damage and longer haulage distances. One approach to reduce the losses due to road blocks is to upgrade the road network to a standard that guarantees accessibility. We consider the road upgrade problem from the perspective of Swedish forest companies with a planning horizon of about one decade. The objective is to minimize the combined upgrade and transportation costs. We present two mixed integer programming models, which are uncapacitated fixed charge network flow problems including multiple assortments, several time periods and a set of road classes. One model is based on arc flows and one on route flows. For a typical planning instance, the models become large and we propose how to improve solution performance through model strengthening. The models are tested in a case study for a major Swedish forest company.      

Solving Planning and Design Problems in the Process Industry Using Mixed Integer and Global Optimization

This contribution gives an overview on the state-of-the-art and recent advances in mixed integer optimization to solve planning and design problems in the process industry. In some case studies specific aspects are stressed and the typical difficulties of real world problems are addressed. Mixed integer linear optimization is widely used to solve supply chain planning problems. Some of the complicating features such as origin tracing and shelf life constraints are discussed in more detail. If properly done the planning models can also be used to do product and customer portfolio analysis. We also stress the importance of multi-criteria optimization and correct modeling for optimization under uncertainty. Stochastic programming for continuous LP problems is now part of most optimization packages, and there is encouraging progress in the field of stochastic MILP and robust MILP. Process and network design problems often lead to nonconvex mixed integer nonlinear programming models. If the time to compute the solution is not bounded, there are already a commercial solvers available which can compute the global optima of such problems within hours. If time is more restricted, then tailored solution techniques are required.     

The new Fundamental Tree Algorithm for production scheduling of open pit mines

The problem of annual production scheduling in surface mining consists of determining an optimal sequence of extracting the mineralized material from the ground. The main objective of the optimization process is usually to maximize the total Net Present Value of the operation. Production scheduling is typically a mixed integer programming (MIP) type problem. However, the large number of integer variables required in formulating the problem makes it impossible to solve. To overcome this obstacle, a new algorithm termed “Fundamental Tree Algorithm” is developed based on linear programming to aggregate blocks of material and decrease the number of integer variables and the number of constraints required within the MIP formulation. This paper proposes the new Fundamental Tree Algorithm in optimizing production scheduling in surface mining. A case study on a large copper deposit summarized in the paper shows substantial economic benefit of the proposed algorithm compared to existing methods.     

考虑占位决策的围堵嫌犯模型

研究了2011年中国大学生数学建模竞赛B题的突发事件中交巡警对在逃嫌犯的围堵问题。不同于对该问题的以往的研究,本文考虑了交巡警在包围圈中可以占据某些路口,使得嫌犯不能通过这些被交巡警占据的路口,从而为形成包围圈的交巡警赢得更多时间。利用两篇相关文献的关于点截集判断的结论和考虑占位决策的建模方法,以不同的目标函数建立了考虑占位决策的围堵嫌犯问题的三个混合0-1非线性整数规划模型。通过选取部分线性约束和目标函数一起组合成混合0-1线性整数规划模型,设计了基于混合0-1线性整数规划方法的算法,并给出了算例。     

不确定条件下的乡村中小学布局优化

学校的合理规划布局是实现教育资源优化配置、提高办学效益和推动教育均衡发展的重要途径。已有许多学者研究了学校的布局问题,但基本上都忽略了交通网络条件以及不确定因素对学校布局的影响。本研究将在前人研究基础上,重点考虑交通网络对乡村中小学选址的影响,并假设旅行时间具有不确定性,从而以最小化学生旅行成本、学校建设、道路修建和道路升级成本为目标,构建不确定条件下的设施区位设计模型。在算法求解方面提出混合模拟退火算法,用于确定新建学校的最佳位置,以及新道路的修建和原有道路的升级情况。最后,将提出的模型和算法应用到实际案例中。     

Revised multi-choice goal programming for multi-period,multi-stage inventory controlled supply chain model with popup stores in Guerrilla marketing

In this paper, we consider a supply chain network design problem with popup stores which can be opened for a few weeks or months before closing seasonally in a marketplace. The proposed model is multi-period and multi-stage with multi-choice goals under inventory management constraints and formulated by 0–1 mixed integer linear programming. The design tasks of the problem involve the choice of the popup stores to be opened and the distribution network design to satisfy the demand with three multi-choice goals. The first goal is minimization of the sum of transportation costs in all stages; the second is to minimization of set up costs of popup stores; and the third goal is minimization of inventory holding and backordering costs. Revised multi-choice goal programming approach is applied to solve this mixed integer linear programming model. Also, we provide a real-world industrial case to demonstrate how the proposed model works.     

Comments on “A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem”

Benati and Rizzi [S. Benati, R. Rizzi, A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem, European Journal of Operational Research 176 (2007) 423–434], in a recent proposal of two linear integer programming models for portfolio optimization using Value-at-Risk as the measure of risk, claimed that the two counterpart models are equivalent. This note shows that this claim is only partly true. The second model attempts to minimize the probability of the portfolio return falling below a certain threshold instead of minimizing the Value-at-Risk. However, the discontinuity of real-world probability values makes the second model impractical. An alternative model with Value-at-Risk as the objective is thus proposed.     

Cutting plane algorithms for the inverse mixed integer linear programming problem

We present cutting plane algorithms for the inverse mixed integer linear programming problem (InvMILP), which is to minimally perturb the objective function of a mixed integer linear program in order to make a given feasible solution optimal.     

A dynamic multi-objective location-allocation model for search and rescue assets

This paper presents a dynamic multi-objective mixed integer linear programming model to optimize the location and allocation of search and rescue (SAR) boats and helicopters to enhance the performance of maritime SAR missions. Our model incorporates simulated incident scenarios to account for demand uncertainty and allows relocation of vessels seasonally. We define three objectives as responding to incidents within a critical time, generating a balanced workload distribution among vessels of various types, and minimizing costs associated with operations and vessel relocations. Implementing a goal programming approach, we solve the problem for various objective function term weights and compare the performance of each solution with respect to 10 different metrics. Using historical incident datasets for the Aegean Sea, we show that the proposed model and solution approach can significantly improve the SAR performance and provide decision support for planners in developing effective and efficient resource location-allocation schemes.     

Min-Max Regret Robust Optimization Approach on Interval Data Uncertainty

This paper presents a three-stage optimization algorithm for solving two-stage deviation robust decision making problems under uncertainty. The structure of the first-stage problem is a mixed integer linear program and the structure of the second-stage problem is a linear program. Each uncertain model parameter can independently take its value from a real compact interval with unknown probability distribution. The algorithm coordinates three mathematical programming formulations to iteratively solve the overall problem. This paper provides the application of the algorithm on the robust facility location problem and a counterexample illustrating the insufficiency of the solution obtained by considering only a finite number of scenarios generated by the endpoints of all intervals. This work was supported by the National Science Foundation through Grant DMI-0200162.     

A single machine scheduling problem with availability constraints and sequence-dependent setup costs

We study a single machine scheduling problem with availability constraints and sequence-dependent setup costs, with the aim of minimizing the makespan. To the authors’ knowledge, this problem has not been treated as such in the operations research literature. We derive in this paper a mixed integer programming model to deal with such scheduling problem. Computational tests showed that commercial solvers are capable of solving only small instances of the problem. Therefore, we propose two ways for reducing the execution time, namely a valid inequality that strengthen the linear relaxation and an efficient heuristic procedure that provides a starting feasible solution to the solver. A substantial gain is achieved both in terms of the linear programming relaxation bound and in terms of the time to obtain an integer optimum when we use the enhanced model in conjunction with providing to the solver the solution obtained by the proposed heuristic.     

A piecewise linearization framework for retail shelf space management models

Managing shelf space is critical for retailers to attract customers and optimize profits. This article develops a shelf-space allocation optimization model that explicitly incorporates essential in-store costs and considers space- and cross-elasticities. A piecewise linearization technique is used to approximate the complicated nonlinear space-allocation model. The approximation reformulates the non-convex optimization problem into a linear mixed integer programming (MIP) problem. The MIP solution not only generates near-optimal solutions for large scale optimization problems, but also provides an error bound to evaluate the solution quality. Consequently, the proposed approach can solve single category-shelf space management problems with as many products as are typically encountered in practice and with more complicated cost and profit structures than currently possible by existing methods. Numerical experiments show the competitive accuracy of the proposed method compared with the mixed integer nonlinear programming shelf-space model. Several extensions of the main model are discussed to illustrate the flexibility of the proposed methodology.     

A mathematical programming model and solution for scheduling production orders in Shanghai Baoshan Iron and Steel Complex

In this paper, we investigate the production order scheduling problem derived from the production of steel sheets in Shanghai Baoshan Iron and Steel Complex (Baosteel). A deterministic mixed integer programming (MIP) model for scheduling production orders on some critical and bottleneck operations in Baosteel is presented in which practical technological constraints have been considered. The objective is to determine the starting and ending times of production orders on corresponding operations under capacity constraints for minimizing the sum of weighted completion times of all orders. Due to large numbers of variables and constraints in the model, a decomposition solution methodology based on a synergistic combination of Lagrangian relaxation, linear programming and heuristics is developed. Unlike the commonly used method of relaxing capacity constraints, this methodology alternatively relaxes constraints coupling integer variables with continuous variables which are introduced to the objective function by Lagrangian multipliers. The Lagrangian relaxed problem can be decomposed into two sub-problems by separating continuous variables from integer ones. The sub-problem that relates to continuous variables is a linear programming problem which can be solved using standard software package OSL, while the other sub-problem is an integer programming problem which can be solved optimally by further decomposition. The subgradient optimization method is used to update Lagrangian multipliers. A production order scheduling simulation system for Baosteel is developed by embedding the above Lagrangian heuristics. Computational results for problems with up to 100 orders show that the proposed Lagrangian relaxation method is stable and can find good solutions within a reasonable time.     

物流服务供应链订单分配优化及其遗传算法

针对物流服务供应链订单分配问题中,物流服务集成商通常会按照所分配的订单价值向分包商收取一定比例交易费用的特点,设定交易费用为交易额的线性函数,构建了新的物流服务供应链订单分配优化混合整数规划模型,其优化目标为最小化交易费用、采购费用、短缺服务与延迟供给的物流能力数量。鉴于问题的NP-hard特性,设计了相应的遗传算法,并结合基于优先权的启发式规则避免了大量非法初始解的出现。实验算例表明所建立的模型能够反映物流服务供应链订单分配过程中的线性交易费用因素,其所设计的算法能够在可接受的时间内获得质量较高的满意解,并且对于大规模订单分配优化问题,遗传算法的求解时间与求解结果要优于LINGO软件。     

模糊环境下动态供应商选择的混合整数非线性规划模型

基于供应商选择问题的动态性和模糊性,考虑在每个周期内生产商的需求能力及供应商的供应能力为模糊变量,本文将一个多阶段多商品多渠道的供应商选择问题视为一个0-1混合整数模糊动态非线性规划问题,目标函数为总成本最小化。然后建立了0-1混合整数模糊动态非线性规划模型。为了求解该模型,通过可信性理论把模型中模糊机会约束清晰化,将该模型转化为一个确定型的0-1混合整数动态非线性规划模型。最后给出了一个数值算例验证了模型的可行性。     

A polynomial algorithm for the earthwork allocation problem with borrow and waste site selection

In road construction projects, earthwork is planned together with horizontal and vertical alignments. This study focuses on earthwork operations that basically include cutting the hills and filling the holes on the road path. The candidate borrow and waste sites can also be used to obtain or heap earth when the available cut and fill amounts are not balanced or operating these sites reduces the total earthwork cost. Total earthwork cost contains the transportation cost and the overall cost related to opening the candidate sites. The problem is to determine which borrow and waste sites to operate, and the earth flows between cut, fill, waste, and borrow sites such that the total cost is minimized. It is shown that the problem is a generalization of the well-known lot-sizing problem. A fixed charge network flow problem formulation is presented, and a polynomial time dynamic programming algorithm is developed for solving the problem.     

A patient assignment algorithm for home care services

We consider the problem of assigning patients to nurses for home care services. The aim is to balance the workload of the nurses while avoiding long travels to visit the patients. We analyse the case of the CSSS Côte-des-Neiges, Métro and Parc Extension for which a previous analysis has shown that demand fluctuations may create work overload for the nursing staff. We propose a mixed integer programming model with some non-linear constraints and a non-linear objective which we solve using a Tabu Search algorithm. A simplification of the workload measure leads to a linear mixed integer program which we optimize using CPLEX.     

Robust scheduling of parallel machines with sequence-dependent set-up costs

In this paper we propose a robust approach for solving the scheduling problem of parallel machines with sequence-dependent set-up costs. In the literature, several mathematical models and solution methods have been proposed to solve such scheduling problems, but most of which are based on the strong assumption that input data are known in a deterministic way. In this paper, a fuzzy mathematical programming model is formulated by taking into account the uncertainty in processing times to provide the optimal solution as a trade-off between total set-up cost and robustness in demand satisfaction. The proposed approach requires the solution of a non-linear mixed integer programming (NLMIP), that can be formulated as an equivalent mixed integer linear programming (MILP) model. The resulting MILP model in real applications could be intractable due to its NP-hardness. Therefore, we propose a solution method technique, based on the solution of an approximated model, whose dimension is remarkably reduced with respect to the original counterpart. Numerical experiments conducted on the basis of data taken from a real application show that the average deviation of the reduced model solution over the optimum is less than 1.5%.