The Dual of a Logical Linear Programme

A Linear Programme (LP) involves a conjunction of linear constraints and has a well defined dual. It is shown that if we allow the full set of Boolean connectives {, , } applied to a set of linear constraints we get a model which we define as a Logical Linear Programme (LLP). This also has a well defined dual preserving most of the properties of LP duality. Generalisations of the connectives are also considered together with the relationship with Integer Programming formulation.     

On stability in Fuzzy Linear Programming problems

This study focuses on the problem of stability (with respect to changes of centres of fuzzy parameters) of the solution in Fuzzy Linear Programming (FLP) problems with symmetrical triangular fuzzy numbers and extended operations and inequalities.     

Linear programming system identification

We define a version of the Inverse Linear Programming problem that we call Linear Programming System Identification. This version of the problem seeks to identify both the objective function coefficient vector and the constraint matrix of a linear programming problem that best fits a set of observed vector pairs. One vector is that of actual decisions that we call outputs. These are regarded as approximations of optimal decision vectors. The other vector consists of the inputs or resources actually used to produce the corresponding outputs. We propose an algorithm for approximating the maximum likelihood solution. The major limitation of the method is the computation of exact volumes of convex polytopes. A numerical illustration is given for simulated data.     

An interval-coefficient fuzzy binary linear programming,the solution,and its application under uncertainties

The common difficulty in solving a Binary Linear Programming (BLP) problem is uncertainties in the parameters and the model structure. The previous studies of BLP problems normally focus on parameter uncertainty or model structure uncertainty, but not on both types of uncertainties. This paper develops an interval-coefficient Fuzzy Binary Linear Programming (IFBLP) and its solution for BLP problems under uncertainties both on parameters and model structure. In the IFBLP, the parameter uncertainty is represented by the interval coefficients, and the model structure uncertainty is reflected by the fuzzy constraints and a fuzzy goal. A novel and efficient methodology is used to solve the IFLBP into two extreme crisp-coefficient BLPs, which are called the ‘best optimum model’ and the ‘worst optimum model’. The results of these two crisp-coefficient extreme models can bound all outcomes of the IFBLP. One of the contributions in this paper is that it provides a mathematical sound approach (based on some mathematical developments) to find the boundaries of optimal alpha values, so that the linearity of model can be maintained during the conversions. The proposed approach is applied to a traffic noise control plan to demonstrate its capability of dealing with uncertainties.     

Integrating the use of linear and dynamic programming methods for dairy cow diet formulation

Despite many refinements that have been made to the basic Linear Programming model used to find economically optimal diets for dairy cows, the sequential nature of the physical and physiological changes that a cow goes through during lactation have not been incorporated into the modelling process satisfactorily. This paper demonstrates how it can be achieved by integrating the use of both Linear and Dynamic Programming methods to optimise the economic performance of a dairy cow over its entire lactation. Linear Programming generates solutions for each potential liveweight change occurring during each of eleven four week periods over the lactation, then the use of DP allows both the selection of the optimal sequence of liveweight changes during the lactation and the specification of rations associated with this optimal path.     

A “reduce and solve” approach for the multiple-choice multidimensional knapsack problem

The multiple-choice multidimensional knapsack problem (MMKP) is a well-known NP-hard combinatorial optimization problem with a number of important applications. In this paper, we present a “reduce and solve” heuristic approach which combines problem reduction techniques with an Integer Linear Programming (ILP) solver (CPLEX). The key ingredient of the proposed approach is a set of group fixing and variable fixing rules. These fixing rules rely mainly on information from the linear relaxation of the given problem and aim to generate reduced critical subproblem to be solved by the ILP solver. Additional strategies are used to explore the space of the reduced problems. Extensive experimental studies over two sets of 37 MMKP benchmark instances in the literature show that our approach competes favorably with the most recent state-of-the-art algorithms. In particular, for the set of 27 conventional benchmarks, the proposed approach finds an improved best lower bound for 11 instances and as a by-product improves all the previous best upper bounds. For the 10 additional instances with irregular structures, the method improves 7 best known results.     

A new formulation for the Traveling Deliveryman Problem

The Traveling Deliveryman Problem is a generalization of the Minimum Cost Hamiltonian Path Problem where the starting vertex of the path, i.e. a depot vertex, is fixed in advance and the cost associated with a Hamiltonian path equals the sum of the costs for the layers of paths (along the Hamiltonian path) going from the depot vertex to each of the remaining vertices. In this paper, we propose a new Integer Programming formulation for the problem and computationally evaluate the strength of its Linear Programming relaxation. Computational results are also presented for a cutting plane algorithm that uses a number of valid inequalities associated with the proposed formulation. Some of these inequalities are shown to be facet defining for the convex hull of feasible solutions to that formulation. These inequalities proved very effective when used to reinforce Linear Programming relaxation bounds, at the nodes of a Branch and Bound enumeration tree.     

A novel clustering approach and prediction of optimal number of clusters: global optimum search with enhanced positioning

Cluster analysis of genome-wide expression data from DNA microarray hybridization studies is a useful tool for identifying biologically relevant gene groupings (DeRisi et al. 1997; Weiler et al. 1997). It is hence important to apply a rigorous yet intuitive clustering algorithm to uncover these genomic relationships. In this study, we describe a novel clustering algorithm framework based on a variant of the Generalized Benders Decomposition, denoted as the Global Optimum Search (Floudas et al. 1989; Floudas 1995), which includes a procedure to determine the optimal number of clusters to be used. The approach involves a pre-clustering of data points to define an initial number of clusters and the iterative solution of a Linear Programming problem (the primal problem) and a Mixed-Integer Linear Programming problem (the master problem), that are derived from a Mixed Integer Nonlinear Programming problem formulation. Badly placed data points are removed to form new clusters, thus ensuring tight groupings amongst the data points and incrementing the number of clusters until the optimum number is reached. We apply the proposed clustering algorithm to experimental DNA microarray data centered on the Ras signaling pathway in the yeast Saccharomyces cerevisiae and compare the results to that obtained with some commonly used clustering algorithms. Our algorithm compares favorably against these algorithms in the aspects of intra-cluster similarity and inter-cluster dissimilarity, often considered two key tenets of clustering. Furthermore, our algorithm can predict the optimal number of clusters, and the biological coherence of the predicted clusters is analyzed through gene ontology.     

A linear characterization of the switching dynamic behavior of timed continuous Petri nets with structural conflicts

The behavior of timed continuous Petri nets (TCPN) can be ruled by linear equations during certain time elapses (IB-states), but changes in the marking and conflict solving policies make nonlinear the complete computation of the behavior. In this paper a global characterization of the switching behavior of TCPN through Mixed Linear Integer Programming (MLIP) is presented. The contribution is an analytical technique to compute the evolution graph of a TCPN, which allows deriving MLIP problems from TCPN models including cycles and structural conflicts; conflict resolution policies by priorities and sharing are considered.     

The Linear Program approach in multi-chain Markov Decision Processes revisited

Linear Programming is known to be an important and useful tool for solving Markov Decision Processes (MDP). Its derivation relies on the Dynamic Programming approach, which also serves to solve MDP. However, for Markov Decision Processes with several constraints the only available methods are based on Linear Programs. The aim of this paper is to investigate some aspects of such Linear Programs, related to multi-chain MDPs. We first present a stochastic interpretation of the decision variables that appear in the Linear Programs available in the literature. We then show for the multi-constrained Markov Decision Process that the Linear Program suggested in [9] can be obtained from an equivalent unconstrained Lagrange formulation of the control problem. This shows the connection between the Linear Program approach and the Lagrange approach, that was previously used only for the case of a single constraint [3, 14, 15].     

Mathematical reasoning and familiar procedures

In this note, we demonstrate with illustrations two different ways that MS Excel can be used to solve Linear Systems of Equation, Linear Programming Problems, and Matrix Inversion Problems. The advantage of using MS Excel is its availability and transparency (the user is responsible for most of the details of how a problem is solved). Further, we develop a worksheet method that is capable of solving and graphing a linear 2?×?2 system. It is our hope that both teachers and students will find the approaches useful for teaching and learning.     

Approximation of linear fractional-multiplicative problems

In this paper we propose a Fully Polynomial Time Approximation Scheme for a class of optimization problems where the feasible region is a polyhedral one and the objective function is the sum or product of ratios of linear functions. The class includes the well known ones of Linear (Sum-of-Ratios) Fractional Programming and Multiplicative Programming.     

An Application of Stochastic Programming with Weibull Distribution–Cluster Based Optimum Allocation of Recruitment in Manpower Planning

Abstract

Recruitment of persons for various assignments with required talents in an organization is an important feature, since it plays a vital role in the growth of the organization. To achieve the required expertise in recruitment, in this paper Linear Stochastic Programming (LSP) is applied along with cluster analysis technique. The aim of this paper is to obtain an optimal allocation of persons to different jobs, so that the time taken to complete all the jobs is minimum. The time taken for a person to complete a job is assumed to follow Weibull distribution. The parameters of Weibull distribution is obtained through Maximum Likelihood Estimator (MLE) approach, along with Cohen's iterative process.     

Home Care optimization: impact of pattern generation policies on scheduling and routing decisions

In Home Care optimization, operators have to be assigned to patients by taking into account compatibility skill constraints, and patient visits have to be scheduled in a given planning horizon. Moreover, operator tours have to be determined. Integer Linear Programming models have been proposed which use the concept of patterns, i.e. a priori scheduling profiles, to combine the diverse decision levels. Computational results on real instances show that pattern generation policies are crucial to address scheduling and routing in large Home Care instances.     

Reminiscences about the origins of linear programming

The author recalls the early days of linear programming, the contributions of von Neumann, Leontief, Koopmans and others.Linear Programming is viewed as a revolutionary development giving us the ability for the first time to state general objectives and to find, by means of the simplex method, optimal policy decisions for a broad class of practical decision problems of great complexity.     

PROMETHEE: an extension through fuzzy mathematical programming

PROMETHEE multi-criteria methods are based on fuzzy evaluations of the differences between pairs of alternatives for each criterion. PROMETHEE II associates a crisp number to each action. PROMETHEE III associates an interval to each action and two actions are considered indifferent when they are very close to each other. PROMETHEE V applies Integer Linear Programming in order to select the subset of alternatives that maximizes the sum of PROMETHEE II scorings, subject to a set of constraints. In order to make the model more realistic, this paper proposes that some constraints are soft and some coefficients are estimated by fuzzy numbers. Fuzzy Integer Linear Programming is applied, using the PROMETHEE III scorings as objective function coefficients, in order to find the subsets of non-outranked alternatives that best satisfy the soft constraints. The new model is more realistic and fits better the fuzzy philosophy of PROMETHEE. The method is illustrated with an example.     

技术系数敏感性的进一步分析

讨论了四类线性规划("max≤"型、"max≥"型、"min≤"型、"min≥"型)问题中,当最优解组成不变时,技术系数a_(ij)各参数可允许变化的范围.为企业经济效益、生产管理及投产等问题提供决策依据-实施原最优方案或对原方案进行调整.     

A new multicriteria approach for the analysis of efficiency in the Spanish olive oil sector by modelling decision maker preferences

The efficiency in production is often analysed as technical efficiency using the production frontier function. Efficiency scores are usually based on distance computations to the frontier in an m + s-dimensional space, where m inputs produce s outputs. In addition, efficiency improvements consider the total consumption of each input. However, in many cases, the “consumption” of each input can be divided into input-consumption sections (ICSs), and trade-off among the ICSs is possible. This share framework can be used for computing efficiency. This analysis provides information about both the total optimal consumption of each input, as does data envelopment analysis, and the most efficient allocation of the “consumption” among the ICSs. This paper studies technical efficiency using this approach and applies it to the olive oil sector in Andalusia (Spain). A non-parametrical methodology is presented, and an input-oriented Multi-Criteria Linear Programming model (MLP) is proposed. The analysis is developed at global, input and ICSs levels, defining the extent of satisfaction achieved at all these levels for each company, in accordance with their own preferences. The companies’ preferences are modelled with their utility function and their set of weights. MLP offers more detailed information to assist decision makers than other models previously proposed in the literature. In addition to this application, it is concluded that there is room for improvement in the olive oil sector, particularly in the management of the skilled labour. Additionally, the solutions with two opposite scenarios indicate that the model is suitable for the intended decision making process.     

A mathematical modeling for incorporating energy price hikes into total natural gas consumption forecasting

In some countries that energy prices are low, price elasticity of demand may not be significant. In this case, large increase or hike in energy prices may impact energy consumption in a way which cannot be drawn from historical data. This paper proposes an integrated adaptive fuzzy inference system (FIS) to forecast long-term natural gas (NG) consumption when prices experience large increase. To incorporate the impact of price hike into modeling, a novel procedure for construction and adaptation of Takagi–Sugeno fuzzy inference system (TS-FIS) is suggested. Linear regressions are used to construct a first order TS-FIS. Furthermore, adaptive network-based FIS (ANFIS) is used to forecast NG consumption in power plants. To cope with random uncertainty in small historical data sets, Monte Carlo simulation is utilized to generate training data for ANFIS. To show the applicability and usefulness of the proposed model, it is applied for forecasting of annual NG consumption in Iran where removing energy subsidies has resulted in a hike in NG prices.     

Fourier-Motzkin elimination extension to integer programming problems

This paper describes how the Fourier-Motzkin Elimination Method, which can be used for solving Linear Programming Problems, can be extended to deal with Integer Programming Problems. The extension derives from a known decision procedure for the formal theory of a fragment of arithmetic which excludes multiplication.