共查询到20条相似文献,搜索用时 31 毫秒
1.
Regulation of Overlaps in Technology Development Activities 总被引:6,自引:0,他引:6
John Liu 《Annals of Operations Research》2000,99(1-4):123-139
In this paper, we present an algorithm for the solution of multiparametric mixed integer linear programming (mp-MILP) problems involving (i) 0-1 integer variables, and, (ii) more than one parameter, bounded between lower and upper bounds, present on the right hand side (RHS) of constraints. The solution is approached by decomposing the mp-MILP into two subproblems and then iterating between them. The first subproblem is obtained by fixing integer variables, resulting in a multiparametric linear programming (mp-LP) problem, whereas the second subproblem is formulated as a mixed integer linear programming (MILP) problem by relaxing the parameters as variables. 相似文献
2.
This paper presents a solution method for the general (mixed integer) parametric linear complementarity problem pLCP(q(θ),M), where the matrix M has a general structure and integrality restriction can be enforced on the solution. Based on the equivalence between the
linear complementarity problem and mixed integer feasibility problem, we propose a mixed integer programming formulation with
an objective of finding the minimum 1-norm solution for the original linear complementarity problem. The parametric linear
complementarity problem is then formulated as multiparametric mixed integer programming problem, which is solved using a multiparametric
programming algorithm. The proposed method is illustrated through a number of examples. 相似文献
3.
For multiparametric convex nonlinear programming problems we propose a recursive algorithm for approximating, within a given
suboptimality tolerance, the value function and an optimizer as functions of the parameters. The approximate solution is expressed
as a piecewise affine function over a simplicial partition of a subset of the feasible parameters, and it is organized over
a tree structure for efficiency of evaluation. Adaptations of the algorithm to deal with multiparametric semidefinite programming
and multiparametric geometric programming are provided and exemplified. The approach is relevant for real-time implementation
of several optimization-based feedback control strategies. 相似文献
4.
Tomas Gal 《European Journal of Operational Research》1977,1(5):307-322
To solve a linear vectormaximum problem means, in general, to determine the set E of all efficient solutions. A multiparametric method based on earlier works of the author is presented. In the procedure efficient vertices and efficient edges are generated via one subprogram, which works as a simple linear programming problem, and just by inspection of these results higher dimensional efficient faces are determined. The procedure does not depend on special properties of the restriction set and/or of the system of given objective functions. Illustrative examples are presented. Two appendixes provide a survey on a multiparametric algorithm and on a solution procedure for the auxiliary problem, both of which are the background for the method. 相似文献
5.
《European Journal of Operational Research》2002,139(3):511-520
We designed an algorithm for the multiparametric 0–1-integer linear programming (ILP) problem with the perturbation of the constraint matrix, the objective function and the right-hand side vector simultaneously considered. Our algorithm works by choosing an appropriate finite sequence of non-parametric mixed integer linear programming (MILP) problems in order to obtain a complete multiparametrical analysis. The algorithm may be implemented by using any software capable of solving MILP problems. 相似文献
6.
Several algorithms to solve the generalized fractional program are summarized and compared numerically in the linear case. These algorithms are iterative procedures requiring the solution of a linear programming problem at each iteration in the linear case. The most efficient algorithm is obtained by marrying the Newton approach within the Dinkelbach approach for fractional programming. 相似文献
7.
《European Journal of Operational Research》1986,24(2):216-227
Traditional pivoting procedures for solving the linear complementarity problem can only guarantee convergence for problems having well defined structures. Recently, optimization procedures based on linear, quadratic, and bilinear programming have been developed to extend the class of problems that can be solved efficiently. These latter approaches are the focus of this paper.The strengths and weaknesses of each of the approaches are discussed. The linear programming approach, advanced by Mangasarian, is the most efficient once an appropriate objective function is found. This requires the solution of a system of linear and bilinear equations that is easily solvable only in some cases. Extensions to this approach, due to Shiau, show some promise but are still limited to special cases of the general problem. The quadratic programming approaches discussed here are restricted to specialized procedures for the complementarity problem. One, proposed by Cheng, is based on the levitin-Poljak gradient projection method, and the other, due to Cirina, is based on Karush-Kuhn-Tucker theory. Both are only successful on some problems. The two bilinear programming algorithms discussed are the most general. For any problem, they are guaranteed to find at least one solution or conclude that none exist. One is a specialization of the recent biconvex programming algorithm of Al-Khayyal and Falk and the other is an entirely new implicit enumeration procedure. 相似文献
8.
F. Borrelli A. Bemporad M. Morari 《Journal of Optimization Theory and Applications》2003,118(3):515-540
We propose a novel algorithm for solving multiparametric linear programming problems. Rather than visiting different bases of the associated LP tableau, we follow a geometric approach based on the direct exploration of the parameter space. The resulting algorithm has computational advantages, namely the simplicity of its implementation in a recursive form and an efficient handling of primal and dual degeneracy. Illustrative examples describe the approach throughout the paper. The algorithm is used to solve finite-time constrained optimal control problems for discrete-time linear dynamical systems. 相似文献
9.
Multilevel programming is characterized as mathematical programming to solve decentralized planning problems. The models partition control over decision variables among ordered levels within a hierarchical planning structure of which the linear bilevel form is a special case of a multilevel programming problem. In a system with such a hierarchical structure, the high-level decision making situations generally require inclusion of zero-one variables representing ‘yes-no’ decisions. We provide a mixed-integer linear bilevel programming formulation in which zero-one decision variables are controlled by a high-level decision maker and real-value decision variables are controlled by a low-level decision maker. An algorithm based on the short term memory component of Tabu Search, called Simple Tabu Search, is developed to solve the problem, and two supplementary procedures are proposed that provide variations of the algorithm. Computational results disclose that our approach is effective in terms of both solution quality and efficiency. 相似文献
10.
In this paper, we examine duality for fractional programming problems in the face of data uncertainty within the framework
of robust optimization. We establish strong duality between the robust counterpart of an uncertain convex–concave fractional
program and the optimistic counterpart of its conventional Wolfe dual program with uncertain parameters. For linear fractional
programming problems with constraint-wise interval uncertainty, we show that the dual of the robust counterpart is the optimistic
counterpart in the sense that they are equivalent. Our results show that a worst-case solution of an uncertain fractional
program (i.e., a solution of its robust counterpart) can be obtained by solving a single deterministic dual program. In the
case of a linear fractional programming problem with interval uncertainty, such solutions can be found by solving a simple
linear program. 相似文献
11.
《Mathematical and Computer Modelling》2000,31(8-9):61-78
In this article, we present an algorithm for the resolution of a nonlinear optimization problem, concretely the posynomial geometric programming model. The solution procedure that we develop extends the condensation techniques for geometric programming, allowing us to find the optimal solutions to the dual geometric problems that we get from the interior of the corresponding feasible regions, in the line that interior point methods for linear programming work, which leads us to obtain considerable computational advantages with respect of the classical solution procedures. 相似文献
12.
We consider probabilistically constrained linear programs with general distributions for the uncertain parameters. These problems
involve non-convex feasible sets. We develop a branch-and-bound algorithm that searches for a global optimal solution to this
problem by successively partitioning the non-convex feasible region and by using bounds on the objective function to fathom
inferior partition elements. This basic algorithm is enhanced by domain reduction and cutting plane strategies to reduce the
size of the partition elements and hence tighten bounds. The proposed branch-reduce-cut algorithm exploits the monotonicity properties inherent in the problem, and requires solving linear programming subproblems.
We provide convergence proofs for the algorithm. Some illustrative numerical results involving problems with discrete distributions
are presented. 相似文献
13.
《European Journal of Operational Research》2005,165(3):569-584
We consider an optimization problem in which some uncertain parameters are replaced by random variables. The minimax approach to stochastic programming concerns the problem of minimizing the worst expected value of the objective function with respect to the set of probability measures that are consistent with the available information on the random data. Only very few practicable solution procedures have been proposed for this problem and the existing ones rely on simplifying assumptions. In this paper, we establish a number of stability results for the minimax stochastic program, justifying in particular the approach of restricting attention to probability measures with support in some known finite set. Following this approach, we elaborate solution procedures for the minimax problem in the setting of two-stage stochastic recourse models, considering the linear recourse case as well as the integer recourse case. Since the solution procedures are modifications of well-known algorithms, their efficacy is immediate from the computational testing of these procedures and we do not report results of any computational experiments. 相似文献
14.
We consider a linear programming problem with unknown objective function. Random observations related to the unknown objective function are sequentially available. We define a stochastic algorithm, based on the simplex method, that estimates an optimal solution of the linear programming problem. It is shown that this algorithm converges with probability one to the set of optimal solutions and that its failure probability is of order inversely proportional to the sample size. We also introduce stopping criteria for the algorithm. The asymptotic normality of some suitably defined residuals is also analyzed. The proposed estimation algorithm is motivated by the stochastic approximation algorithms but it introduces a generalization of these techniques when the linear programming problem has several optimal solutions. The proposed algorithm is also close to the stochastic quasi-gradient procedures, though their usual assumptions are weakened.Mathematics Subject Classification (2000): 90C05, 62L20, 90C15Acknowledgments. I would like to thank two unknown referees for their fruitful suggestions that have helped to improve the paper. 相似文献
15.
We consider the problem of obtaining integer solutions to a minmax linear programming problem. Although this general problem is NP-complete, it is shown that a restricted version of this problem can be solved in polynomial time. For this restricted class of problems two polynomial time algorithms are suggested, one of which is strongly polynomial whenever its continuous analogue and an associated linear programming problem can be solved by a strongly polynomial algorithm. Our algorithms can also be used to obtain integer solutions for the minmax transportation problem with an inequality budget constraint. The equality constrained version of this problem is shown to be NP-complete. We also provide some new insights into the solution procedures for the continuous minmax linear programming problem. 相似文献
16.
基于多参数线性规划理论,将不确定型二层线性规划问题转化为多个关于不确定参数的线性规划问题。利用不确定型决策方法中的悲观准则.从最不利的结果中选择最有利的结果,从而得到不确定型二层线性规划的最优解。数值实例的仿真结果表明,所提出的悲观决策方法对解决诸如不确定供应链的规划与运作等问题不失为一种有效的决策支持工具。 相似文献
17.
Janet Somers 《Discrete Applied Mathematics》1979,1(4):287-300
In this paper we present a comprehensive analysis of the max-flow problem with n parametric capacities, and give the basis for an algorithm to solve it. In particular we give a method for finding the max-flow value as a function of the parameters, and max-flows for all parameter points, in terms of max-flow values to problems at certain key parameter points. In the problem with nonzero lower bounds on the arc flows, we derive a set of linear constraints whose solution set is identical to the set of all feasible parameter points.The intrinsic difficulty of the problem is compared with that of the general multiparametric linear programming problem, and thus light is shed on the difficulty of the latter problem, whose complexity is currently unknown. 相似文献
18.
19.
20.
The zero-one integer programming problem and its special case, the multiconstraint knapsack problem frequently appear as subproblems in many combinatorial optimization problems. We present several methods for computing lower bounds on the optimal solution of the zero-one integer programming problem. They include Lagrangean, surrogate and composite relaxations. New heuristic procedures are suggested for determining good surrogate multipliers. Based on theoretical results and extensive computational testing, it is shown that for zero-one integer problems with few constraints surrogate relaxation is a viable alternative to the commonly used Lagrangean and linear programming relaxations. These results are used in a follow up paper to develop an efficient branch and bound algorithm for solving zero-one integer programming problems. 相似文献