模糊环境下带有平衡条件的投资项目评估与选择决策方法

文章提出在模糊环境下求解带有平衡条件的投资项目评估与选择问题的决策方法。该方法由模糊综合评价系统和项目选择的模糊整数规划模型两部分组成。其中模糊综合评价系统采用三角模糊数来描述决策人对项目的主观评价以及多个评价因素的综合，而模糊整数规划模型则描述了各种不同门类利益之间的平衡。最后以实例说明该方法的应用。     

An ILP model with logical constraints for mail sorting facility selection

This paper studies a facility selection problem which is generalised from the design of a mail sorting system with multiple input and output. The problem is formulated as a 0–1 integer linear programming (ILP) problem with logical constraints. We show how the logical constraints can be embedded into a ILP model. We compare three strategies for handling logical relations: (1) explicitly as added linear constraints; (2) implicitly as symbolic constraints; and (3) a combination of the two. The effectiveness of computations under different strategies are shown.     

New convergent heuristics for 0–1 mixed integer programming

Several hybrid methods have recently been proposed for solving 0–1 mixed integer programming problems. Some of these methods are based on the complete exploration of small neighborhoods. In this paper, we present several convergent algorithms that solve a series of small sub-problems generated by exploiting information obtained from a series of relaxations. These algorithms generate a sequence of upper bounds and a sequence of lower bounds around the optimal value. First, the principle of a linear programming-based algorithm is summarized, and several enhancements of this algorithm are presented. Next, new hybrid heuristics that use linear programming and/or mixed integer programming relaxations are proposed. The mixed integer programming (MIP) relaxation diversifies the search process and introduces new constraints in the problem. This MIP relaxation also helps to reduce the gap between the final upper bound and lower bound. Our algorithms improved 14 best-known solutions from a set of 108 available and correlated instances of the 0–1 multidimensional Knapsack problem. Other encouraging results obtained for 0–1 MIP problems are also presented.     

Expanded model of the project portfolio selection problem with divisibility,time profile factors and cardinality constraints

This paper develops a new model for project portfolio selection over a planning horizon with multiple time periods. The model considers the divisibility of projects and combines reinvestment, set-up cost, cardinality constraints and precedence relationship in the scheduling, simultaneously. For efficient computation, an equivalent mixed integer linear programming representation is provided. One numerical example with three scenarios is given to highlight the capability and characteristics of the proposed model.     

Ranking in quadratic integer programming problems

The present paper develops an algorithm for ranking the integer feasible solutions of a quadratic integer programming (QIP) problem. A linear integer programming (LIP) problem is constructed which provides bounds on the values of the objective function of the quadratic problem. The integer feasible solutions of this related integer linear programming problem are systematically scanned to rank the integer feasible solutions of the quadratic problem in non-decreasing order of the objective function values. The ranking in the QIP problem is useful in solving a nonlinear integer programming problem in which some other complicated nonlinear restrictions are imposed which cannot be included in the simple linear constraints of QIP, the objective function being still quadratic.     

An approach to the valuation and decision of ERP investment projects based on real options

The risks and uncertainties inherent in most enterprise resources planning (ERP) investment projects are vast. Decision making in multistage ERP projects investment is also complex, due mainly to the uncertainties involved and the various managerial and/or physical constraints to be enforced. This paper tackles the problem using a real-option analysis framework, and applies multistage stochastic integer programming in formulating an analytical model whose solution will yield optimum or near-optimum investment decisions for ERP projects. Traditionally, such decision problems were tackled using lattice simulation or finite difference methods to compute the value of simple real options. However, these approaches are incapable of dealing with the more complex compound real options, and their use is thus limited to simple real-option analysis. Multistage stochastic integer programming is particularly suitable for sequential decision making under uncertainty, and is used in this paper and to find near-optimal strategies for complex decision problems. Compared with the traditional approaches, multistage stochastic integer programming is a much more powerful tool in evaluating such compound real options. This paper describes the proposed real-option analysis model and uses an example case study to demonstrate the effectiveness of the proposed approach.     

Solving continuous min max problem for single period portfolio selection with discrete constraints by DCA

In this article, we consider the application of a continuous min–max model with cardinality constraints to worst-case portfolio selection with multiple scenarios of risk, where the return forecast of each asset belongs to an interval. The problem can be formulated as minimizing a convex function under mixed integer variables with additional complementarity constraints. We first prove that the complementarity constraints can be eliminated and then use Difference of Convex functions (DC) programming and DC Algorithm (DCA), an innovative approach in non-convex programming frameworks, to solve the resulting problem. We reformulate it as a DC program and then show how to apply DCA to solve it. Numerical experiments on several test problems are reported that demonstrate the accuracy of the proposed algorithm.     

On Facets of Knapsack Equality Polytopes

The 0/1 knapsack equality polytope is, by definition, the convex hull of 0/1 solutions of a single linear equation. A special form of this polytope, where the defining linear equation has nonnegative integer coefficients and the number of variables having coefficient one exceeds the right-hand side, is considered. Equality constraints of this form arose in a real-world application of integer programming to a truck dispatching scheduling problem. Families of facet defining inequalities for this polytope are identified, and complete linear inequality representations are obtained for some classes of polytopes.     

Rules-based heuristic approach for the U-shaped assembly line balancing problem

The type-2 U-shaped assembly line balancing problem is important for many just-in-time manufactures, but an efficient algorithm is not available at present. Thus, in this study, a novel heuristic approach based on multiple rules and an integer programming model is proposed to address this problem. In the proposed approach, three rules are systematically grouped together, i.e., task selection, task assignment, and task exchange rules. The sufficient conditions for implementing the exchange rules are proposed and proved. Thirteen small or medium scale benchmark issues comprising 63 instances were solved, where the computational results demonstrate the efficiency and effectiveness of the proposed method compared with integer programming. The computational results obtained for 18 examples comprising 121 instances demonstrate that the task exchange rules significantly improve the computational accuracy compared with the traditional heuristic. Finally, 30 new standard instances produced by a systematic data generation process were also solved effectively by the proposed approach. The proposed heuristic approach with multiple rules can provide a theoretical basis for other local search algorithms, especially for addressing issues such as the U-Shaped assembly line balancing problem.     

Constrained integer linear fractional programming problem

An integer linear fractional programming problem, whose integer solution is required to satisfy any h out of given n sets of constraints has been discussed in this paper. Method for ranking and scanning all integer points has also been developed and a numerical illustration is included in support of theory.     

A separable integer programming problem equivalent to its continual version

The separable integer programming problem with so called nested constraints is shown to be equivalent to its continual version obtained by piecewise linear continuation of the cost functions. A new approach to solution of the latter based on its successive reduction in size is suggested. When applied to the problem with piecewise linear convex functions it leads to two algorithms for its solution applicable also to the similar integer problem. These algorithms turn out more efficient than those obtained by dynamic programming approach.     

An exact approach for solving integer problems under probabilistic constraints with random technology matrix

This paper addresses integer programming problems under probabilistic constraints involving discrete distributions. Such problems can be reformulated as large scale integer problems with knapsack constraints. For their solution we propose a specialized Branch and Bound approach where the feasible solutions of the knapsack constraint are used as partitioning rules of the feasible domain. The numerical experience carried out on a set covering problem with random covering matrix shows the validity of the solution approach and the efficiency of the implemented algorithm.     

Modeling target volume flows in forest harvest scheduling subject to maximum area restrictions

In forest harvest scheduling problems, one must decide which stands to harvest in each period during a planning horizon. A typical requirement in these problems is a steady flow of harvested timber, mainly to ensure that the industry is able to continue operating with similar levels of machine and labor utilizations. The integer programming approaches described use the so-called volume constraints to impose such a steady yield. These constraints do not directly impose a limit on the global deviation of the volume harvested over the planning horizon or use pre-defined target harvest levels. Addressing volume constraints generally increases the difficulty of solving the integer programming formulations, in particular those proposed for the area restriction model approach. In this paper, we present a new type of volume constraint as well as a multi-objective programming approach to achieve an even flow of timber. We compare the main basic approaches from a computational perspective. The new volume constraints seem to more explicitly control the global deviation of the harvested volume, while the multi-objective approach tends to provide the best profits for a given dispersion of the timber flow. Neither approach substantially changed the computational times involved.     

A multiple criteria ranking procedure based on distance between partial preorders

In this paper, a multiple criteria ranking procedure based on distance between partial preorders is proposed. This method consists of two phases. In the first phase, the decision maker is asked to rank alternatives with a preorder (complete or partial) for each criterion and provide complete or partial linear information about the relative importance (weights) of the criteria. In the second phase, we introduce a distance procedure to aggregate the above individual rankings into a global ranking (a partial preorder). An algorithm for the aggregation procedure is proposed, followed by a numerical illustration.     

Environmental site evaluation of waste management facilities embedded into EUGÈNE model: A multicriteria approach

EUGÈNE is a sophisticated mixed integer linear programming model developed to help regional decision makers on long-term planning for solid waste management activities. The model removes almost every limitations encountered in other waste management models and contains a large quantity of variables and constraints. The method used to embed waste management environmental parameters in the EUGÈNE model consists in building global impact index (GII) for all site/facility combinations. First, an environmental and spatial evaluation of waste management facilities over sites is based on qualitative and quantitative criteria measuring biophysical and social impacts. Spatial analysis is carried out by geographical information system routines. Then, a multicriteria analysis ranks all site/facility combinations, according to their global performance based on all criteria. The net flow, computed by the PROMETHEE multicriteria outranking method, is considered as a GII to be embedded into EUGÈNE. The model objective function is thus modified to minimize total system cost and GII. Some practical results obtained for the City of Montreal are discussed.     

Modelling either-or relations in integer programming

Logical relations occur frequently in integer programming problems and are modelled by introducing binary variables in association with linear expressions. Applications requiring constraints involving precedence, exclusion, implication and other conditions give rise to the logical relations OR and IMPLIES in the models. These relations will be considered in this paper from a modelling point of view and formulations investigated for situations where the logical variables link sets of integer variables. Valid inequalities (cuts) that can be added to a model will be developed for a number of the formulations and the computational benefits of these cuts will be considered from an experimental point of view by considering the performance of sets of problem instances. New formulations and combinations of older established formulations will be considered. It will be contended that tight formulations may not always be the most successful.     

A zero-one model for project portfolio selection and scheduling

A zero-one integer linear programming model is proposed for selecting and scheduling an optimal project portfolio, based on the organisation's objectives and constraints such as resource limitations and interdependence among projects. The model handles some of the issues that frequently arise in real world applications but are not addressed by previously suggested models, such as situations in which the amount of available and consumed resources varies in different periods. It also allows for interactive adjustment following the optimisation process, to provide decision makers a method for controlling portfolio selection, based on criteria that may be difficult to elicit directly. It is critical for such a system to provide fast evaluation of alternatives the decision makers may want to examine, and this requirement is addressed. The proposed model not only suggests projects that should be incorporated in the optimal portfolio, but it also determines the starting period for each project. Scheduling considerations can have a major impact on the combination of projects that can be incorporated in the portfolio, and may allow the addition of certain projects to the portfolio that could not have been selected otherwise. An example problem is described and solved with the proposed model, and some areas for future research are discussed.     

An optimization model for the aggregate production planning of a Brazilian sugar and ethanol milling company

This work presents an optimization model to support decisions in the aggregate production planning of sugar and ethanol milling companies. The mixed integer programming formulation proposed is based on industrial process selection and production lot-sizing models. The aim is to help the decision makers in selecting the industrial processes used to produce sugar, ethanol and molasses, as well as in determining the quantities of sugarcane crushed, the selection of sugarcane suppliers and sugarcane transport suppliers, and the final product inventory strategy. The planning horizon is the whole sugarcane harvesting season and decisions are taken on a discrete fraction of time. A case study was developed in a Brazilian mill and the results highlight the applicability of the proposed approach.     

Multicriteria dynamic programming with an application to the integer case

Fundamental dynamic programming recursive equations are extended to the multicriteria framework. In particular, a more detailed procedure for a general recursive solution scheme for the multicriteria discrete mathematical programming problem is developed. Definitions of lower and upper bounds are offered for the multicriteria case and are incorporated into the recursive equations to aid problem solution by eliminating inefficient subpolicies. Computational results are reported for a set of 0–1 integer linear programming problems.This research was supported in part by CONACYT (Consejo Nacional de Ciencia y Technologia), Mexico City, Mexico.     

Column enumeration based decomposition techniques for a class of non-convex MINLP problems

We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration approach. The master problem is a partitioning problem whose objective function coefficients are computed via subproblems. These problems can be linear, mixed integer linear, (non-)convex nonlinear, or mixed integer nonlinear. However, the important property of the subproblems is that we can compute their exact global optimum quickly. The proposed technique will be illustrated solving a cutting problem with optimum nonlinear programming subproblems.