دانلود رایگان مقاله راه حل خطی مشکلات مجموعه پروژه Mid-SemiVariance

abstract

We study the Mean-SemiVariance Project (MSVP) portfolio selection problem, where the objective is to obtain the optimal risk-reward portfolio of non-divisible projects when the risk is measured by the semivariance of the portfolio’s Net-Present Value (NPV) and the reward is measured by the portfolio’s expected NPV. Similar to the well-known mean-variance portfolio selection problem, when integer variables are present (e.g., due to transaction costs, cardinality constraints, or asset illiquidity), the MSVP problem can be solved using Mixed-Integer Quadratic Programming (MIQP) techniques. However, conventional MIQP solvers may be unable to solve large-scale MSVP problem instances in a reasonable amount of time. In this paper, we propose two linear solution schemes to solve the MSVP problem; that is, the proposed schemes avoid the use of MIQP solvers and only require the use of Mixed-Integer Linear Programming (MILP) techniques. In particular, we show that the solution of a class of real-world MSVP problems, in which project returns are positively correlated, can be accurately approximated by solving a single MILP problem. In general, we show that the MSVP problem can be effectively solved by a sequence of MILP problems, which allow us to solve large-scale MSVP problem instances faster than using MIQP solvers. We illustrate our solution schemes by solving a real MSVP problem arising in a Latin American oil and gas company. Also, we solve instances of the MSVP problem that are constructed using data from the PSPLIB library of project scheduling problems.

6. Concluding Remarks

In this paper, we studied the MSVP problem. After presenting a convex quadratic formulation of the problem, we proposed two alternative linear solution schemes that effectively solve this problem. These schemes have both practical and computational advantages over a direct MIQP approach to solve the MSVP. The first scheme is based on a MILP approximation that overestimates the project’s portfolio NPV semivariance (prone for risk-averse decision makers) by solving a single MILP. Aside from providing a formal proof of this overestimation, the computational tests show that the MILP approximation is very accurate when dealing with projects with positively correlated NPVs. Moreover, for instances of the MSVP problem with a moderate number of projects in which it is desired to use a large number of samples to accurately estimate the project’s portfolio NPV semivariance, the MILP approximation solution approach is shown to consistently outperform the default CPLEX 12.5 MIQP solver that can be used to directly solve the MSVP problem.