共查询到20条相似文献,搜索用时 218 毫秒
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.
In bilevel optimization problems there are two decision makers, the leader and the follower, who act in a hierarchy. Each
decision maker has his own objective function, but there are common constraints. This paper deals with bilevel assignment
problems where each decision maker controls a subset of edges and each edge has a leader’s and a follower’s weight. The edges
selected by the leader and by the follower need to form a perfect matching. The task is to determine which edges the leader
should choose such that his objective value which depends on the follower’s optimal reaction is maximized. We consider sum-
and bottleneck objective functions for the leader and follower. Moreover, if not all optimal reactions of the follower lead
to the same leader’s objective value, then the follower either chooses an optimal reaction which is best (optimistic rule)
or worst (pessimistic rule) for the leader. We show that all the variants arising if the leader’s and follower’s objective
functions are sum or bottleneck functions are NP-hard if the pessimistic rule is applied. In case of the optimistic rule the problem is shown to be NP-hard if at least one of the decision makers has a sum objective function. 相似文献
3.
This paper considers a particular case of linear bilevel programming problems with one leader and multiple followers. In this
model, the followers are independent, meaning that the objective function and the set of constraints of each follower only
include the leader’s variables and his own variables. We prove that this problem can be reformulated into a linear bilevel
problem with one leader and one follower by defining an adequate second level objective function and constraint region. In
the second part of the paper we show that the results on the optimality of the linear bilevel problem with multiple independent
followers presented in Shi et al. [The kth-best approach for linear bilevel multi-follower programming, J. Global Optim. 33, 563–578 (2005)] are based on a misconstruction
of the inducible region. 相似文献
4.
Matteo Fischetti Ivana Ljubić Michele Monaci Markus Sinnl 《Mathematical Programming》2018,172(1-2):77-103
We address a generic mixed-integer bilevel linear program (MIBLP), i.e., a bilevel optimization problem where all objective functions and constraints are linear, and some/all variables are required to take integer values. We first propose necessary modifications needed to turn a standard branch-and-bound MILP solver into an exact and finitely-convergent MIBLP solver, also addressing MIBLP unboundedness and infeasibility. As in other approaches from the literature, our scheme is finitely-convergent in case both the leader and the follower problems are pure integer. In addition, it is capable of dealing with continuous variables both in the leader and in follower problems—provided that the leader variables influencing follower’s decisions are integer and bounded. We then introduce new classes of linear inequalities to be embedded in this branch-and-bound framework, some of which are intersection cuts based on feasible-free convex sets. We present a computational study on various classes of benchmark instances available from the literature, in which we demonstrate that our approach outperforms alternative state-of-the-art MIBLP methods. 相似文献
5.
We introduce the bilevel knapsack problem with stochastic right-hand sides, and provide necessary and sufficient conditions for the existence of an optimal solution. When the leader’s decisions can take only integer values, we present an equivalent two-stage stochastic programming reformulation with binary recourse. We develop a branch-and-cut algorithm for solving this reformulation, and a branch-and-backtrack algorithm for solving the scenario subproblems. Computational experiments indicate that our approach can solve large instances in a reasonable amount of time. 相似文献
6.
Description of 2-integer continuous knapsack polyhedra 总被引:1,自引:0,他引:1
In this paper we discuss the polyhedral structure of several mixed integer sets involving two integer variables. We show that the number of the corresponding facet-defining inequalities is polynomial on the size of the input data and their coefficients can also be computed in polynomial time using a known algorithm [D. Hirschberg, C. Wong, A polynomial-time algorithm for the knapsack problem with two variables, Journal of the Association for Computing Machinery 23 (1) (1976) 147–154] for the two integer knapsack problem. These mixed integer sets may arise as substructures of more complex mixed integer sets that model the feasible solutions of real application problems. 相似文献
7.
《Operations Research Letters》2014,42(6-7):424-428
Minimizing a convex function over the integral points of a bounded convex set is polynomial in fixed dimension (Grötschel et al., 1988). We provide an alternative, short, and geometrically motivated proof of this result. In particular, we present an oracle-polynomial algorithm based on a mixed integer linear optimization oracle. 相似文献
8.
Ronald H. Nickel Igor Mikolic-Torreira Jon W. Tolle 《Computational Optimization and Applications》2006,35(1):109-126
Deployed US Navy aircraft carriers must stock a large number of spare parts to support the various types of aircraft embarked
on the ship. The sparing policy determines the spares that will be stocked on the ship to keep the embarked aircraft ready
to fly. Given a fleet of ten or more aircraft carriers and a cost of approximately 50 million dollars per carrier plus the
cost of spares maintained in warehouses in the United States, the sparing problem constitutes a significant portion of the
Navy’s resources. The objective of this work is to find a minimum-cost sparing policy that meets the readiness requirements
of the embarked aircraft. This is a very large, nonlinear, integer optimization problem. The cost function is piecewise linear
and convex while the constraint mapping is highly nonlinear. The distinguishing characteristics of this problem from an optimization
viewpoint are that a large number of decision variables are required to be integer and that the nonlinear constraint functions
are essentially “black box” functions; that is, they are very difficult (and expensive) to evaluate and their derivatives
are not available. Moreover, they are not convex. Integer programming problems with a large number of variables are difficult
to solve in general and most successful approaches to solving nonlinear integer problems have involved linear approximation
and relaxation techniques that, because of the complexity of the constraint functions, are inappropriate for attacking this
problem. We instead employ a pattern search method to each iteration of an interior point-type algorithm to solve the relaxed
version of the problem. From the solution found by the pattern search on each interior point iteration, we begin another pattern
search on the integer lattice to find a good integer solution. The best integer solution found across all interations is returned
as the optimal solution. The pattern searches are distributed across a local area network of non-dedicated, heterogeneous
computers in an office environment, thus, drastically reducing the time required to find the solution. 相似文献
9.
Extended formulations in combinatorial optimization 总被引:1,自引:0,他引:1
Michele Conforti Gérard Cornuéjols Giacomo Zambelli 《4OR: A Quarterly Journal of Operations Research》2010,8(1):1-48
This survey is concerned with the size of perfect formulations for combinatorial optimization problems. By “perfect formulation”,
we mean a system of linear inequalities that describes the convex hull of feasible solutions, viewed as vectors. Natural perfect
formulations often have a number of inequalities that is exponential in the size of the data needed to describe the problem.
Here we are particularly interested in situations where the addition of a polynomial number of extra variables allows a formulation
with a polynomial number of inequalities. Such formulations are called “compact extended formulations”. We survey various
tools for deriving and studying extended formulations, such as Fourier’s procedure for projection, Minkowski–Weyl’s theorem,
Balas’ theorem for the union of polyhedra, Yannakakis’ theorem on the size of an extended formulation, dynamic programming,
and variable discretization. For each tool that we introduce, we present one or several examples of how this tool is applied.
In particular, we present compact extended formulations for several graph problems involving cuts, trees, cycles and matchings,
and for the mixing set. We also present Bienstock’s approximate compact extended formulation for the knapsack problem, Goemans’
result on the size of an extended formulation for the permutahedron, and the Faenza-Kaibel extended formulation for orbitopes. 相似文献
10.
Jie Lu Chenggen Shi Guangquan Zhang Tharam Dillon 《Journal of Global Optimization》2007,38(4):597-608
When multiple followers are involved in a bilevel decision problem, the leader’s decision will be affected, not only by the
reactions of these followers, but also by the relationships among these followers. One of the popular situations within this
bilevel multi-follower issue is where these followers are uncooperatively making their decisions while having cross reference
to decision information of the other followers. This situation is called a referential-uncooperative situation in this paper.
The well-known Kuhn–Tucker approach has been previously successfully applied to a one-leader-and-one-follower linear bilevel
decision problem. This paper extends this approach to deal with the above-mentioned linear referential-uncooperative bilevel
multi-follower decision problem. The paper first presents a decision model for this problem. It then proposes an extended
Kuhn–Tucker approach to solve this problem. Finally, a numerical example illustrates the application of the extended Kuhn–Tucker
approach. 相似文献
11.
Linear mixed 0–1 integer programming problems may be reformulated as equivalent continuous bilevel linear programming (BLP)
problems. We exploit these equivalences to transpose the concept of mixed 0–1 Gomory cuts to BLP. The first phase of our new
algorithm generates Gomory-like cuts. The second phase consists of a branch-and-bound procedure to ensure finite termination
with a global optimal solution. Different features of the algorithm, in particular, the cut selection and branching criteria
are studied in details. We propose also a set of algorithmic tests and procedures to improve the method. Finally, we illustrate
the performance through numerical experiments. Our algorithm outperforms pure branch-and-bound when tested on a series of
randomly generated problems.
Work of the authors was partially supported by FCAR, MITACS and NSERC grants. 相似文献
12.
Let Y be a convex set in \Re
k
defined by polynomial inequalities and equations of degree at most d ≥ 2 with integer coefficients of binary length at most l . We show that if the set of optimal solutions of the integer programming problem min is not empty, then the problem has an optimal solution of binary length ld
O(k4)
. For fixed k , our bound implies a polynomial-time algorithm for computing an optimal integral solution y
*
. In particular, we extend Lenstra's theorem on the polynomial-time solvability of linear integer programming in fixed dimension
to semidefinite integer programming.
Received August 3, 1998, and in revised form March 22, 1999. 相似文献
13.
Global solution of nonlinear mixed-integer bilevel programs 总被引:1,自引:0,他引:1
Alexander Mitsos 《Journal of Global Optimization》2010,47(4):557-582
An algorithm for the global optimization of nonlinear bilevel mixed-integer programs is presented, based on a recent proposal
for continuous bilevel programs by Mitsos et al. (J Glob Optim 42(4):475–513, 2008). The algorithm relies on a convergent
lower bound and an optional upper bound. No branching is required or performed. The lower bound is obtained by solving a mixed-integer
nonlinear program, containing the constraints of the lower-level and upper-level programs; its convergence is achieved by
also including a parametric upper bound to the optimal solution function of the lower-level program. This lower-level parametric
upper bound is based on Slater-points of the lower-level program and subsets of the upper-level host sets for which this point
remains lower-level feasible. Under suitable assumptions the KKT necessary conditions of the lower-level program can be used
to tighten the lower bounding problem. The optional upper bound to the optimal solution of the bilevel program is obtained
by solving an augmented upper-level problem for fixed upper-level variables. A convergence proof is given along with illustrative
examples. An implementation is described and applied to a test set comprising original and literature problems. The main complication
relative to the continuous case is the construction of the parametric upper bound to the lower-level optimal objective value,
in particular due to the presence of upper-level integer variables. This challenge is resolved by performing interval analysis
over the convex hull of the upper-level integer variables. 相似文献
14.
Toshimde Ibaraki 《Discrete Mathematics》1976,16(1):39-52
This paper considers in a somewhat general setting when a combinatorial optimization problem can be formulated as an (all-integer) integer programming (IP) problem. The main result is that any combinatorial optimization problem can be formulated as an IP problem if its feasible region S is finite but there are many rather sample problems that have no IP formulation if their S is infinite. The approach used for finite S usually gives a formulation with a relatively small number of additional variables for example, an integer polynomial of n 0?1 variables requires at most n + 1 additional variables by our approach, whereas 2n - (n + 1) additional variables at maximum are required by other existing methods. Finally, the decision problem of deciding whether an arbitrarily given combinatorial optimization problem has an IP formulation is considered and it is shown by an argument closely related to Hilbert's tenth problem (drophantine equations) that no such algorithm exists. 相似文献
15.
We analyze a multiperiod oligopolistic market where each period is a Stackelberg game between a leader firm and multiple follower
firms. The leader chooses his production level first, taking into account the reaction of the followers. Then, the follower
firms decide their production levels after observing the leader’s decision. The difference between the proposed model and
other models discussed in literature is that the leader firm has the power to force the follower firms out of business by
preventing them from achieving a target sales level in a given time period. The leader firm has an incentive to lower the
market prices possibly lower than the Stackelberg equilibrium in order to push the followers to sell less and eventually go
out of business. Intentionally lowering the market prices to force competitors to fail is known as predatory pricing, and
is illegal under antitrust laws since it negatively affects consumer welfare. In this work, we show that there exists a predatory
pricing strategy where the market price is above the average cost and consumer welfare is preserved. We develop a mixed integer
nonlinear problem (MINLP) that models the multiperiod Stackelberg game. The MINLP problem is transformed to a mixed integer
linear problem (MILP) by using binary variables and piecewise linearization. A cutting plane algorithm is used to solve the
resulting MILP. The results show that firms can engage in predatory pricing even if the average market price is forced to
remain higher than the average cost. Furthermore, we show that in order to protect the consumers, antitrust laws can control
predatory pricing by setting rules on consumer welfare. 相似文献
16.
In this paper, a computational algorithm, named RST2ANU algorithm, has been developed for solving integer and mixed integer global optimization problems. This algorithm, which primarily is based on the original controlled random search approach of Price [22i], incorporates a simulated annealing type acceptance criterion in its working so that not only downhill moves but also occasional uphill moves can be accepted. In its working it employs a special truncation procedure which not only ensures that the integer restrictions imposed on the decision variables are satisfied, but also creates greater possibilities for the search leading to a global optimal solution. The reliability and efficiency of the proposed RST2ANU algorithm has been demonstrated on thirty integer and mixed integer optimization problems taken from the literature. The performance of the algorithm has been compared with the performance of the corresponding purely controlled random search based algorithm as well as the standard simulated annealing algorithm. The performance of the method on mathematical models of three realistic problems has also been demonstrated. 相似文献
17.
We propose a modified sequential quadratic programming method for solving mixed-integer nonlinear programming problems. Under
the assumption that integer variables have a smooth influence on the model functions, i.e., that function values do not change drastically when in- or decrementing an integer
value, successive quadratic approximations are applied. The algorithm is stabilized by a trust region method with Yuan’s second
order corrections. It is not assumed that the mixed-integer program is relaxable or, in other words, function values are evaluated
only at integer points. The Hessian of the Lagrangian function is approximated by a quasi-Newton update formula subject to
the continuous and integer variables. Numerical results are presented for a set of 80 mixed-integer test problems taken from
the literature. The surprising result is that the number of function evaluations, the most important performance criterion
in practice, is less than the number of function calls needed for solving the corresponding relaxed problem without integer
variables. 相似文献
18.
This paper considers two scheduling problems for a two-machine flowshop where a single machine is followed by a batching machine. The first problem is that there is a transporter to carry the jobs between machines. The second problem is that there are deteriorating jobs to be processed on the single machine. For the first problem with minimizing the makespan, we formulate it as a mixed integer programming model and then prove that it is strongly NP-hard. A heuristic algorithm is proposed for solving this problem and its worst case performance is analyzed. The computational experiments are carried out and the numerical results show that the heuristic algorithm is effective. For the second problem, we derive the optimal algorithms with polynomial time for minimizing the makespan, the total completion time and the maximum lateness, respectively. 相似文献
19.
Two approaches that solve the mixed-integer nonlinear bilevel programming problem to global optimality are introduced. The first addresses problems mixed-integer nonlinear in outer variables and C2-nonlinear in inner variables. The second adresses problems with general mixed-integer nonlinear functions in outer level. Inner level functions may be mixed-integer nonlinear in outer variables, linear, polynomial, or multilinear in inner integer variables, and linear in inner continuous variables. This second approach is based on reformulating the mixed-integer inner problem as continuous via its vertex polyheral convex hull representation and solving the resulting nonlinear bilevel optimization problem by a novel deterministic global optimization framework. Computational studies illustrate proposed approaches. 相似文献
20.