A Dimensional Reduction Approach Based on Essential Constraints in Linear Programming

This paper presents a new dimension reduction strategy for medium and large-scale linear programming problems. The proposed method uses a subset of the original constraints and combines two algorithms: the weighted average and the cosine simplex algorithm. The first approach identifies binding constraints by using the weighted average of each constraint, whereas the second algorithm is based on the cosine similarity between the vector of the objective function and the constraints. These two approaches are complementary, and when used together, they locate the essential subset of initial constraints required for solving medium and large-scale linear programming problems. After reducing the dimension of the linear programming problem using the subset of the essential constraints, the solution method can be chosen from any suitable method for linear programming. The proposed approach was applied to a set of well-known benchmarks as well as more than 2000 random medium and large-scale linear programming problems. The results are promising, indicating that the new approach contributes to the reduction of both the size of the problems and the total number of iterations required. A tree-based classification model also confirmed the need for combining the two approaches. A detailed numerical example, the general numerical results, and the statistical analysis for the decision tree procedure are presented.

Optimal Batching Plan of Deoxidation Alloying based on Principal Component Analysis and Linear Programming

As the market competition of steel mills is severe,deoxidization alloying is an important link in the metallurgical process.To solve this problem,principal component regression analysis is adopted to reduce the dimension of influencing factors,and a reasonable and reliable prediction model of element yield is established.Based on the constraint conditions such as target cost function constraint,yield constraint and non-negative constraint,linear programming is adopted to design the lowest cost batting scheme that meets the national standards and production requirements.The research results provide a reliable optimization model for the deoxidization and alloying process of steel mills,which is of positive significance for improving the market competitiveness of steel mills,reducing waste discharge and protecting the environment.

A Dynamic Active-Set Method for Linear Programming

An efficient active-set approach is presented for both nonnegative and general linear programming by adding varying numbers of constraints at each iteration. Computational experiments demonstrate that the proposed approach is significantly faster than previous active-set and standard linear programming algorithms.

A Review of Quantitative Analysis (QA) in Production Planning Decisions Using the Linear Programming Model

The purpose of this paper was to examine the role of quantitative analysis in production planning decisions. This draws from the observed imperatives of quantitative analysis in business decisions and its capacity for predictability and enhanced decision making given the increasingly complex nature of the business environment. The paper therefore addressed the historical evolution of quantitative technique as an efficient and effective decision-making tool. The content of the paper addressed commonly applied quantitative technique in manufacturing firms today which is, linear programming and its subsequent impact on production planning decisions. The results based on a congruence of views revealed that the “best-fit” application of quantitative analysis models and tools can untangle the complexities of production and planning decision making process in order to achieve the organizational goal. This is, as literature also showed that there is obviously no consensus or integrated model that is capable of solving all managerial problem, different models such as the linear programming model have however been developed to cater for different problems as they arise. The workability or suitability of quantitative analysis is actually premised on its appropriate application. The paper recommends the application of quantitative analysis using linear programming in solving various resource allocation related issues in the primary production planning function of manufacturing firms.

Dynamic programming methodology for multi-criteria group decision-making under ordinal preferences

A method of minimizing rankings inconsistency is proposed for a decision-making problem with rankings of alternatives given by multiple decision makers according to multiple criteria. For each criteria, at first, the total inconsistency between the rankings of all alternatives for the group and the ones for every decision maker is defined after the decision maker weights in respect to the criteria are considered. Similarly, the total inconsistency between their final rankings for the group and the ones under every criteria is determined after the criteria weights are taken into account. Then two nonlinear integer programming models minimizing respectively the two total inconsistencies above are developed and then transformed to two dynamic programming models to obtain separately the rankings of all alternatives for the group with respect to each criteria and their final rankings. A supplier selection case illustrated the proposed method, and some discussions on the results verified its effectiveness. This work develops a new measurement of ordinal preferences’ inconsistency in multi-criteria group decision-making （MCGDM） and extends the cook-seiford social selection function to MCGDM considering weights of criteria and decision makers and can obtain unique ranking result.

A new heuristic algorithm for general integer linear programming problems

A new heuristic algorithm is proposed for solving general integer linear programming problems. In the algorithm, the objective function hyperplane is used as a cutting plane, and then by introducing a special set of assistant sets, an efficient heuristic search for the solution to the integer linear program is carried out in the sets on the objective function hyperplane. A simple numerical example shows that the algorithm is efficient for some problems, and therefore, of practical interest.

A Hybrid Dynamic Programming Method for Concave Resource Allocation Problems

Concave resource allocation problem is an integer programming problem of minimizing a nonincreasing concave function subject to a convex nondecreasing constraint and bounded integer variables. This class of problems are encountered in optimization models involving economies of scale. In this paper, a new hybrid dynamic programming method was proposed for solving concave resource allocation problems. A convex underestimating function was used to approximate the objective function and the resulting convex subproblem was solved with dynamic programming technique after transforming it into a 0-1 linear knapsack problem. To ensure the convergence, monotonicity and domain cut technique was employed to remove certain integer boxes and partition the revised domain into a union of integer boxes. Computational results were given to show the efficiency of the algorithm.

Max-plus-linear model-based predictive control for constrained hybrid systems: linear programming solution

In this paper, a linear programming method is proposed to solve model predictive control for a class of hybrid systems. Firstly, using the （max, ＋） algebra, a typical subclass of hybrid systems called max-plus-linear （MPL） systems is obtained. And then, model predictive control （MPC） framework is extended to MPL systems. In general, the nonlinear optimization approach or extended linear complementarity problem （ELCP） were applied to solve the MPL-MPC optimization problem. A new optimization method based on canonical forms for max-min-plus-scaling （MMPS） functions （using the operations maximization, minimization, addition and scalar multiplication） with linear constraints on the inputs is presented. The proposed approach consists in solving several linear programming problems and is more efficient than nonlinear optimization. The validity of the algorithm is illustrated by an example.

A New Method to Evaluate Linear Programming Problem in Bipolar Single-Valued Neutrosophic Environment

A bipolar single-valued neutrosophic set can deal with the hesitation relevant to the information of any decision making problem in real life scenarios,where bipolar fuzzy sets may fail to handle those hesitation problems.In this study,we first develop a new method for solving linear programming problems based on bipolar singlevalued neutrosophic sets.Further,we apply the score function to transform bipolar single-valued neutrosophic problems into crisp linear programming problems.Moreover,we apply the proposed technique to solve fully bipolar single-valued neutrosophic linear programming problems with non-negative triangular bipolar single-valued neutrosophic numbers(TBSvNNs)and non-negative trapezoidal bipolar single-valued neutrosophic numbers(TrBSvNNs).

Randomized Objective Function Linear Programming in Risk Management

The traditional linear programming model is deterministic. The way that uncertainty is handled is to compute the range of optimality. After the optimal solution is obtained, typically by the simplex method, one considers the effect of varying each objective function coefficient, one at a time. This yields the range of optimality within which the decision variables remain constant. This sensitivity analysis is useful for helping the analyst get a sense for the problem. However, it is unrealistic because objective function coefficients tend not to stand still. They are typically profit contributions from products sold and are subject to randomly varying selling prices. In this paper, a realistic linear program is created for simultaneously randomizing the coefficients from any probability distribution. Furthermore, we present a novel approach for designing a copula of random objective function coefficients according to a specified rank correlation. The corresponding distribution of objective function values is created. This distribution is examined directly for central tendency, spread, skewness and extreme values for the purpose of risk analysis. This enables risk analysis and business analytics, emerging topics in education and preparation for the knowledge economy.

Solving the Binary Linear Programming Model in Polynomial Time

The paper presents a technique for solving the binary linear programming model in polynomial time. The general binary linear programming problem is transformed into a convex quadratic programming problem. The convex quadratic programming problem is then solved by interior point algorithms. This settles one of the open problems of whether P = NP or not. The worst case complexity of interior point algorithms for the convex quadratic problem is polynomial. It can also be shown that every liner integer problem can be converted into binary linear problem.

A Linear Programming Model for Seabed Oil-Gas Pipe Network

This paper analyzes the pipe network system of oil-gas collection and transportation for offshore oilfield development. A '0-1' integer linear programming model is constructed to optimize the investment of seabed pipe network. The mathematical model is solved by the spanning tree method of graph theory and network analysis. All spanning trees of a network graph compose all the feasible solutions of the mathematical model. The optimal solution of the model is the spanning tree with the minimum cost among all spanning trees. This method can be used to optimize the seabed pipe network system and give a minimum cost plan for the development of offshore marginal oilfield groups.

AN IMPROVEMENT ON UNCONSTRAINED CONVEX PROGRAMMING APPROACH TO LINEAR PROGRAMMING

For satate form linear gram as Fang and sao deined and approach which would find an optimal solution by solving an anconstrained convex dual programming.Thedual was construcied by applying an emropic peturbation and a simple Inequality Inz【z-1 for z】0n,In this paper,we suggest than a paperbation functiontake the place of Inx such that the new approdt has good numerical stability andhas all properties of the original

Diagnosis and Resolution of Infeasibility in the Constraint Method for Solving Multi Objective Linear Programming Problems

In this paper we discuss about infeasibility diagnosis and infeasibility resolution, when the constraint method is used for solving multi objective linear programming problems. We propose an algorithm for resolution of infeasibility, which is a combination of interactive, weighting and constraint methods.Numerical examples are provided to illustrate the techniques developed.

Reserve Constrained Dynamic Economic Dispatch with Valve-point Effect:A Two-stage Mixed Integer Linear Programming Approach

This paper proposes a deterministic two-stage mixed integer linear programming(TSMILP)approach to solve the reserve constrained dynamic economic dispatch(DED)problem considering valve-point effect(VPE).In stage one,the nonsmooth cost function and the transmission loss are piecewise linearized and consequently the DED problem is formulated as a mixed integer linear programming(MILP)problem,which can be solved by commercial solvers.In stage two,based on the solution obtained in stage one,a range compression technique is proposed to make a further exploitation in the subspace of the whole solution domain.Due to the linear approximation of the transmission loss,the solution obtained in stage two dose not strictly satisfies the power balance constraint.Hence,a forward procedure is employed to eliminate the error.The simulation results on four test systems show that TSMILP makes satisfactory performances,in comparison with the existing methods.

Existence and Uniqueness of Solutions for two Classes of Functional Equations Arising in Dynamic Programming

In this paper we establish the existence, uniqueness and iterative approximation of solutions for two classes of functional equations arising in dynamic programming of multistage decision processes. The results presented here extend, and unify the corresponding results due to Bellman, Bhakta and Choudhury, Bhakta and Mitra, Liu and others.

Time Optimal Feedrate Generation with Confined Tracking Error Based on Linear Programming

In this paper,the problem of time optimal feedrate generation under confined feedrate,axis accelerations,and axis tracking errors is considered.The main contribution is to reduce the tracking error constraint to constraints about the axis velocities and accelerations,when the tracking error satisfies a second order linear ordinary differential equation.Based on this simplification on the tracking error,the original feedrate generation problem is reduced to a new form which can be efficiently solved with linear programming algorithms.Simulation results are used to validate the methods.

Genetic programming for predictions of effectiveness of rolling dynamic compaction with dynamic cone penetrometer test results

Rolling dynamic compaction (RDC),which employs non-circular module towed behind a tractor,is an innovative soil compaction method that has proven to be successful in many ground improvement applications.RDC involves repeatedly delivering high-energy impact blows onto the ground surface,which improves soil density and thus soil strength and stiffness.However,there exists a lack of methods to predict the effectiveness of RDC in different ground conditions,which has become a major obstacle to its adoption.For this,in this context,a prediction model is developed based on linear genetic programming (LGP),which is one of the common approaches in application of artificial intelligence for nonlinear forecasting.The model is based on in situ density-related data in terms of dynamic cone penetrometer (DCP) results obtained from several projects that have employed the 4-sided,8-t impact roller (BH-1300).It is shown that the model is accurate and reliable over a range of soil types.Furthermore,a series of parametric studies confirms its robustness in generalizing data.In addition,the results of the comparative study indicate that the optimal LGP model has a better predictive performance than the existing artificial neural network (ANN) model developed earlier by the authors.

The Optimal Conditions of the Linear Fractional Programming Problem with Constraint

In this article,the authors discuss the optimal conditions of the linear fractionalprogramming problem and prove that a locally optional solution is a globally optional solution and the locally optimal solution can be attained at a basic feasible solution withconstraint condition.