In this paper we consider how to increase the capacities of the elements in a set E efficiently so that the capacity of a given family F of subsets of E can be increased to the maximum extent while the total cost for ...
详细信息
In this paper we consider how to increase the capacities of the elements in a set E efficiently so that the capacity of a given family F of subsets of E can be increased to the maximum extent while the total cost for the increment of capacity is within a given budget bound. We transform this problem into finding the minimum weight element of F when the weight of each element of E is a linear function of a single parameter and propose an algorithm for solving this problem. We further discuss the problem for some special cases. Especially, when E is the edge set of a network and the family F consists of all spanning trees, we give a strongly polynomial algorithm.
Preprocessing of raw data has been shown to improve performance of knowledge discovery processes. Discretization of quantitative attributes is a key component of preprocessing and has the potential to greatly impact t...
详细信息
Preprocessing of raw data has been shown to improve performance of knowledge discovery processes. Discretization of quantitative attributes is a key component of preprocessing and has the potential to greatly impact the efficiency of the process and the quality of its outcomes. In attribute discretization, the value domain of an attribute is partitioned into a finite set of intervals so that the attribute can be described using a small number of discrete representations. Discretization therefore involves two decisions, on the number of intervals and the placement of interval boundaries. Previous approaches for quantitative attribute discretization have used heuristic algorithms to identify partitions of the attribute value domain. Therefore, these approaches cannot be guaranteed to provide the optimal solution for the given discretization criterion and number of intervals. In this paper, we use linearprogramming (LP) methods to formulate the attribute discretization problem. The LP formulation allows the discretization criterion and the number of intervals to be integral considerations of the problem. We conduct experiments and identify optimal solutions for various discretization criteria and numbers of intervals.
In this paper we investigate the sensitivity analysis of the parameterized central path, First, a complete marginal analysis of the central optimal solution is developed. This analysis explains the differential proper...
详细信息
In this paper we investigate the sensitivity analysis of the parameterized central path, First, a complete marginal analysis of the central optimal solution is developed. This analysis explains the differential properties of the central optimal solution with respect to both the cost coefficients and the right-hand side components. We also show that the marginal derivatives are uniformly bounded. Second, we present three conditions for which the parameterized central path converges. Two of these results allow the difficult situation of simultaneous perturbations in the cost coefficients and right-hand side levels.
In the cluster analysis problem one seeks to partition a finite set of objects into disjoint groups (or clusters) such that each group contains relatively similar objects and, relatively dissimilar objects are placed ...
详细信息
In the cluster analysis problem one seeks to partition a finite set of objects into disjoint groups (or clusters) such that each group contains relatively similar objects and, relatively dissimilar objects are placed in different groups. For certain classes of the problem or, under certain assumptions, the partitioning exercise can be formulated as a sequence of linear programs (LPs), each with a parametric objective function. Such LPs can be solved using the parametric linear programming procedure developed by Gass and Saaty [(Gass, S., Saaty, T. (1955), Naval Research Logistics Quarterly 2, 39-45)]. In this paper, a parametric linear programming model for solving cluster analysis problems is presented. We show how this model can be used to find optimal solutions for certain variations of the clustering problem or, in other cases, for an approximation of the general clustering problem. (C) 1998 Elsevier Science B.V. All rights reserved.
We present a decomposition method for indefinite quadratic programming problems having n variables and m linear constraints. The given problem is decomposed into at most m QP subproblems each having m linear constrain...
详细信息
We present a decomposition method for indefinite quadratic programming problems having n variables and m linear constraints. The given problem is decomposed into at most m QP subproblems each having m linear constraints and n-1 variables. All global minima, all isolated local minima and some of the non-isolated local minima for the given problem are obtained from those of the lower dimensional subproblems. One way to continue solving the given problem is to apply the decomposition method again to the subproblems and repeatedly doing so until subproblems of dimension 1 are produced and these can be solved directly. A technique to reduce the potentially large number of subproblems is formulated.
Operations Research (OR) methodology and its mathematical models have been widely accepted as management means in China, not only in industry and agriculture, but also in non-profit organizations, including the govern...
详细信息
The production-transportation problem (PTP) is a generalization of the transportation problem. In PTP, we decide not only the level of shipment from each source to each sink but also the level of supply at each source...
详细信息
The production-transportation problem (PTP) is a generalization of the transportation problem. In PTP, we decide not only the level of shipment from each source to each sink but also the level of supply at each source. A concave production cost function is associated with the assignment of supplies to sources. Thus the objective function of PTP is the sum of the linear transportation costs and the production costs. We show that this problem is generally NP-hard and present some polynomial classes. In particular, we propose a polynomial algorithm for the case in which the transportation cost matrix has the Monge property and the number of sources is fixed. The algorithm generalizes a polynomial algorithm of Tuy, Dan, and Ghannadan [Oper. Res. Lett., 14 (1993), pp. 99-109] for the problem with two sources.
In the present paper we derive an O(n(2) log n) algorithm for the linearprogramming (LP) relaxation of the two dimensional knapsack problem with box and generalized upper bound (GUB) constraints. The two dimensional ...
详细信息
In the present paper we derive an O(n(2) log n) algorithm for the linearprogramming (LP) relaxation of the two dimensional knapsack problem with box and generalized upper bound (GUB) constraints. The two dimensional linear knapsack problem with box constraints and GUB's generalizes the multiple choice linear knapsack problem considered by Dyer and others. The problem arose in an application in a steel tube rolling mill in India.
This paper presents a result of transforming a class of non-convex programs into parametric programs. parametric linear programming algorithms are then developed to solve several special cases of the quadratic assignm...
详细信息
This paper presents a result of transforming a class of non-convex programs into parametric programs. parametric linear programming algorithms are then developed to solve several special cases of the quadratic assignment problem (QAP). Lower and upper bounds of the parameters are derived to further accelerate the parameter search. Numerical experiments are conducted to show the efficiency of the algorithm.
We present a new definition of optimality intervals for the parametric right-hand side linearprogramming (parametric RHS LP) Problem phi(lambda) = min{c(T)x\Ax = b + lambda-bBAR, x greater-than-or-equal-to 0}. We the...
详细信息
We present a new definition of optimality intervals for the parametric right-hand side linearprogramming (parametric RHS LP) Problem phi(lambda) = min{c(T)x\Ax = b + lambda-bBAR, x greater-than-or-equal-to 0}. We then show that an optimality interval consists either of a breakpoint or the open interval between two consecutive breakpoints of the continuous piecewise linear convex function phi(lambda). As a consequence, the optimality intervals form a partition of the closed interval {lambda;\phi(lambda)\ < infinity}. Based on these optimality intervals, we also introduce an algorithm for solving the parametric RHS LP problem which requires an LP solver as a subroutine. If a polynomial-time LP solver is used to implement this subroutine, we obtain a substantial improvement on the complexity of those parametric RHS LP instances which exhibit degeneracy. When the number of breakpoints of phi(lambda) is polynomial in terms of the size of the parametric problem, we show that the latter can be solved in polynomial time.
暂无评论