共查询到20条相似文献,搜索用时 15 毫秒
1.
Parametric global optimisation for bilevel programming 总被引:2,自引:2,他引:0
Nuno P. Faísca Vivek Dua Berç Rustem Pedro M. Saraiva Efstratios N. Pistikopoulos 《Journal of Global Optimization》2007,38(4):609-623
We propose a global optimisation approach for the solution of various classes of bilevel programming problems (BLPP) based
on recently developed parametric programming algorithms. We first describe how we can recast and solve the inner (follower’s)
problem of the bilevel formulation as a multi-parametric programming problem, with parameters being the (unknown) variables
of the outer (leader’s) problem. By inserting the obtained rational reaction sets in the upper level problem the overall problem
is transformed into a set of independent quadratic, linear or mixed integer linear programming problems, which can be solved
to global optimality. In particular, we solve bilevel quadratic and bilevel mixed integer linear problems, with or without
right-hand-side uncertainty. A number of examples are presented to illustrate the steps and details of the proposed global
optimisation strategy. 相似文献
2.
This paper is concerned with a portfolio optimization problem under concave and piecewise constant transaction cost. We formulate
the problem as nonconcave maximization problem under linear constraints using absolute deviation as a measure of risk and
solve it by a branch and bound algorithm developed in the field of global optimization. Also, we compare it with a more standard
0–1 integer programming approach. We will show that a branch and bound method elaborating the special structure of the problem
can solve the problem much faster than the state-of-the integer programming code. 相似文献
3.
This paper is concerned with porfolio optimization problems with integer constraints. Such problems include, among others
mean-risk problems with nonconvex transaction cost, minimal transaction unit constraints and cardinality constraints on the
number of assets in a portfolio. These problems, though practically very important have been considered intractable because
we have to solve nonlinear integer programming problems for which there exists no efficient algorithms. We will show that
these problems can now be solved by the state- of-the-art integer programming methodologies if we use absolute deviation as
the measure of risk. 相似文献
4.
Jonathan F. Bard Krishnamurthi Venkatraman Thomas A. Feo 《Journal of Global Optimization》1993,3(3):289-309
This paper considers the problem of schedulingn jobs on a single machine to minimize the total cost incurred by their respective flow time and earliness penalties. It is assumed that each job has a due date that must be met, and that preemptions are not allowed. The problem is formulated as a dynamic program (DP) and solved with a reaching algorithm that exploits a series of dominance properties and efficiently generated bounds. A major factor underlying the effectiveness of the approach is the use of a greedy randomized adaptive search procedure (GRASP) to construct high quality feasible solutions. These solutions serve as upper bounds on the optimum, and permit a predominant portion of the state space to be fathomed during the DP recursion.To evaluate the performance of the algorithm, an experimental design involving over 240 randomly generated problems was followed. The test results indicate that problems with up to 30 jobs can be readily solved on a microcomputer in less than 12 minutes. This represents a significant improvement over previously reported results for both dynamic programming and mixed integer linear programming approaches. 相似文献
5.
P. Hungerländer 《Optimization》2017,66(10):1699-1712
We suggest a new variant of a row layout problem: Find an ordering of n departments with given lengths such that the total weighted sum of their distances to a given checkpoint is minimized. The Checkpoint Ordering Problem (COP) is both of theoretical and practical interest. It has several applications and is conceptually related to some well-studied combinatorial optimization problems, namely the Single-Row Facility Layout Problem, the Linear Ordering Problem and a variant of parallel machine scheduling. In this paper we study the complexity of the (COP) and its special cases. The general version of the (COP) with an arbitrary but fixed number of checkpoints is NP-hard in the weak sense. We propose both a dynamic programming algorithm and an integer linear programming approach for the (COP) . Our computational experiments indicate that the (COP) is hard to solve in practice. While the run time of the dynamic programming algorithm strongly depends on the length of the departments, the integer linear programming approach is able to solve instances with up to 25 departments to optimality. 相似文献
6.
Ronaldo Carpio 《Journal of Difference Equations and Applications》2020,26(2):209-222
ABSTRACTWe propose an algorithm, which we call ‘Fast Value Iteration’ (FVI), to compute the value function of a deterministic infinite-horizon dynamic programming problem in discrete time. FVI is an efficient algorithm applicable to a class of multidimensional dynamic programming problems with concave return (or convex cost) functions and linear constraints. In this algorithm, a sequence of functions is generated starting from the zero function by repeatedly applying a simple algebraic rule involving the Legendre-Fenchel transform of the return function. The resulting sequence is guaranteed to converge, and the Legendre-Fenchel transform of the limiting function coincides with the value function. 相似文献
7.
Multibody elastic contact analysis by quadratic programming 总被引:1,自引:0,他引:1
A quadratic programming method for contact problems is extended to a general problem involving contact ofn elastic bodies. Sharp results of quadratic programming theory provide an equivalence between the originaln-body contact problem and the simplex algorithm used to solve the quadratic programming problem. Two multibody examples are solved to illustrate the technique. 相似文献
8.
Absolute value programming 总被引:4,自引:0,他引:4
O. L. Mangasarian 《Computational Optimization and Applications》2007,36(1):43-53
We investigate equations, inequalities and mathematical programs involving absolute values of variables such as the equation
Ax+B|x| = b, where A and B are arbitrary m× n real matrices. We show that this absolute value equation is NP-hard to solve, and that solving it with B = I solves the general linear complementarity problem. We give sufficient optimality conditions and duality results for absolute
value programs as well as theorems of the alternative for absolute value inequalities. We also propose concave minimization
formulations for absolute value equations that are solved by a finite succession of linear programs. These algorithms terminate
at a local minimum that solves the absolute value equation in almost all solvable random problems tried. 相似文献
9.
Amedeo Premoli 《Mathematical Programming》1986,36(2):210-227
A compact algorithm is presented for solving the convex piecewise-linear-programming problem, formulated by means of a separable
convex piecewise-linear objective function (to be minimized) and a set of linear constraints. This algorithm consists of a
finite sequence of cycles, derived from the simplex method, characteritic of linear programming, and the line search, characteristic
of nonlinear programming. Both the required storage and amount of calculation are reduced with respect to the usual approach,
based on a linear-programming formulation with an expanded tableau. The tableau dimensions arem×(n+1), wherem is the number of constraints andn the number of the (original) structural variables, and they do not increase with the number of breakpoints of the piecewise-linear
terms constituting the objective function. 相似文献
10.
R.K Ahuja 《Operations Research Letters》1985,4(3):131-134
In this paper, we consider the following minimax linear programming problem: min z = max1 ≤ j ≤ n{CjXj}, subject to Ax = g, x ≥ 0. It is well known that this problem can be transformed into a linear program by introducing n additional constraints. We note that these additional constraints can be considered implicitly by treating them as parametric upper bounds. Based on this approach we develop two algorithms: a parametric algorithm and a primal—dual algorithm. The parametric algorithm solves a linear programming problem with parametric upper bounds and the primal—dual algorithm solves a sequence of related dual feasible linear programming problems. Computation results are also presented, which indicate that both the algorithms are substantially faster than the simplex algorithm applied to the enlarged linear programming problem. 相似文献
11.
Michael J. Todd 《Mathematical Programming》1986,35(2):173-192
We show that a particular pivoting algorithm, which we call the lexicographic Lemke algorithm, takes an expected number of steps that is bounded by a quadratic inn, when applied to a random linear complementarity problem of dimensionn. We present two probabilistic models, both requiring some nondegeneracy and sign-invariance properties. The second distribution is concerned with linear complementarity problems that arise from linear programming. In this case we give bounds that are quadratic in the smaller of the two dimensions of the linear programming problem, and independent of the larger. Similar results have been obtained by Adler and Megiddo.Research partially funded by a fellowship from the Alfred Sloan Foundation and by NSF Grant ECS82-15361. 相似文献
12.
Satoru Hashizume Masao Fukushima Naoki Katoh Toshihide Ibaraki 《Mathematical Programming》1987,37(3):255-267
We are concerned with a combinatorial optimization problem which has the ratio of two linear functions as the objective function.
This type of problems can be solved by an algorithm that uses an auxiliary problem with a parametrized linear objective function.
Because of its combinatorial nature, however, it is often difficult to solve the auxiliary problem exactly. In this paper,
we propose an algorithm which assumes that the auxiliary problems are solved only approximately, and prove that it gives an
approximate solution to the original problem, of which the accuracy is at least as good as that of approximate solutions to
the auxiliary problems. It is also shown that the time complexity is bounded by the square of the computation time of the
approximate algorithm for the auxiliary problem. As an example of the proposed algorithm, we present a fully polynomial time
approximation scheme for the fractional 0–1 knapsack problem. 相似文献
13.
We consider two-stage stochastic programming problems with integer recourse. The L-shaped method of stochastic linear programming
is generalized to these problems by using generalized Benders decomposition. Nonlinear feasibility and optimality cuts are
determined via general duality theory and can be generated when the second stage problem is solved by standard techniques.
Finite convergence of the method is established when Gomory’s fractional cutting plane algorithm or a branch-and-bound algorithm
is applied. 相似文献
14.
We introduce a new upper bound for the maximum-entropy sampling problem. Our bound is described as the solution of a linear
integer program. The bound depends on a partition of the underlying set of random variables. For the case in which each block
of the partition has bounded cardinality, we describe an efficient dynamic-programming algorithm to calculate the bound. For
the very special case in which the blocks have no more than two elements, we describe an efficient algorithm for calculating
the bound based on maximum-weight matching. This latter formulation has particular value for local-search procedures that
seek to find a good partition. We relate our bound to recent bounds of Hoffman, Lee and Williams. Finally, we report on the
results of some computational experiments.
Received: September 27, 2000 / Accepted: July 26, 2001 Published online: September 5, 2002
Key words. experimental design – design of experiments – entropy – maximum-entropy sampling – matching – integer program – spectral
bound – Fischer's inequality – branch-and-bound – dynamic programming
Mathematics Subject Classification (2000): 52B12, 90C10
Send offprint requests to: Jon Lee
Correspondence to: Jon Lee 相似文献
15.
A branch-and-bound algorithm to solve 0–1 parametric mixed integer linear programming problems has been developed. The present algorithm is an extension of the branch-and-bound algorithm for parametric analysis on pure integer programming. The characteristic of the present method is that optimal solutions for all values of the parameter can be obtained. 相似文献
16.
Yrjö Seppälä 《BIT Numerical Mathematics》1972,12(3):376-399
This paper describes a new algorithm solving the deterministic equivalents of chance-constrained problems where the random variables are normally distributed and independent of each other. In this method nonlinear chance-constraints are first replaced by uniformly tighter linear constraints. The resulting linear programming problem is solved by a standard simplex method. The linear programming problem is then revised using the solution data and solved again until the stopping rule of the algorithm terminates the process. It is proved that the algorithm converges and that the solution found is the -optimal solution of the chance-constrained programming problem.The computational experience of the algorithm is reported. The algorithm is efficient if the random variables are distributed independently of each other and if they number less than two hundred. The computing system is called CHAPS, i.e. Chance-ConstrainedProgrammingSystem. 相似文献
17.
We study Graver test sets for linear two-stage stochastic integer programs and show that test sets can be decomposed into
finitely many building blocks whose number is independent on the number of scenarios of the stochastic program. We present
a finite algorithm to compute the building blocks directly, without prior knowledge of test set vectors. Once computed, building
blocks can be employed to solve the stochastic program by a simple augmentation scheme, again without explicit knowledge of
test set vectors. Finally, we report preliminary computational experience.
Received: March 14, 2002 / Accepted: March 27, 2002 Published online: September 27, 2002
Key words. test sets – stochastic integer programming – decomposition methods
Mathematics Subject Classification (2000): 90C15, 90C10, 13P10 相似文献
18.
In many situations, a worker’s ability improves as a result of repeating the same or similar tasks; this phenomenon is known as the learning effect. In this paper the learning effect is considered in a two-machine flowshop. The objective is to find a sequence that minimizes a weighted sum of total completion time and makespan. Total completion time and makespan are widely used performance measures in scheduling literature. To solve this scheduling problem, an integer programming model with n2 + 6n variables and 7n constraints where n is the number of jobs is formulated. Because of the lengthy computing time and high computing complexity of the integer programming model, the problem with up to 30 jobs can be solved. A heuristic algorithm and a tabu search based heuristic algorithm are presented to solve large size problems. Experimental results show that the proposed heuristic methods can solve this problem with up to 300 jobs rapidly. According to the best of our knowledge, no work exists on the bicriteria flowshop with a learning effect. 相似文献
19.
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. 相似文献
20.
We consider 0–1 programming problems with a minimax objective function and any set of constraints. Upon appropriate transformations of its cost coefficients, such a minimax problem can be reduced to a linear minisum problem with the same set of feasible solutions such that an optimal solution to the latter will also solve the original minimax problem.Although this reducibility applies for any 0–1 programming problem, it is of particular interest for certain locational decision models. Among the obvious implications are that an algorithm for solving a p-median (minisum) problem in a network will also solve a corresponding p-center (minimax) problem.It should be emphasized that the results presented will in general only hold for 0–1 problems due to intrinsic properties of the minimax criterion. 相似文献