Parametric global optimisation for bilevel programming

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.     

The computational complexity of bilevel assignment problems

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.     

Linear bilevel multi-follower programming with independent followers

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.     

On the use of intersection cuts for bilevel optimization

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.     

The bilevel knapsack problem with stochastic right-hand sides

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.     

Description of 2-integer continuous knapsack polyhedra

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.     

Integer convex minimization by mixed integer linear optimization

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.     

Computing Aviation Sparing Policies: Solving a Large Nonlinear Integer Program

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.     

Extended formulations in combinatorial optimization

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.     

Model and extended Kuhn–Tucker approach for bilevel multi-follower decision making in a referential-uncooperative situation

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.     

New Branch-and-Cut Algorithm for Bilevel Linear Programming

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.     

Integer Optimization on Convex Semialgebraic Sets

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.     

Global solution of nonlinear mixed-integer bilevel programs

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.     

Integer programming formulation of combinatorial optimization problems

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 2ⁿ - (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.     

Controlled predatory pricing in a multiperiod Stackelberg game: an MPEC approach

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.     

A Controlled Random Search Technique Incorporating the Simulated Annealing Concept for Solving Integer and Mixed Integer Global Optimization Problems

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.     

A trust region SQP algorithm for mixed-integer nonlinear programming

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.     

Two-machine flowshop scheduling problems involving a batching machine with transportation or deterioration consideration

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.     

Global optimization of mixed-integer bilevel programming problems

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 C²-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.