A simple Tabu Search method to solve the mixed-integer linear bilevel programming problem

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.     

Deterministic solution approach for some classes of nonlinear multilevel programs with multiple followers

In this paper we investigate multilevel programming problems with multiple followers in each hierarchical decision level. It is known that such type of problems are highly non-convex and hard to solve. A solution algorithm have been proposed by reformulating the given multilevel program with multiple followers at each level that share common resources into its equivalent multilevel program having single follower at each decision level. Even though, the reformulated multilevel optimization problem may contain non-convex terms at the objective functions at each level of the decision hierarchy, we applied multi-parametric branch-and-bound algorithm to solve the resulting problem that has polyhedral constraints. The solution procedure is implemented and tested for a variety of illustrative examples.     

Geometric and algorithmic developments for a hierarchical planning problem

This paper presents a new model for multiobjective planning in hierarchical systems that explicitly takes into consideration the order in which decisions are made. Interactions and conflicts that normally exist among the levels are introduced by specifying jointly controlled feasible regions and interdependent objective functions. At each level in the system, planners attempt to maximize net benefits in light of all higher-level decisions, and thus may influence but not control the behavior of others. The resultant formulation leads to the multilevel programming problem. The geometry of an all linear case is first examined wherein it is shown that the optimal solution must lie at a vertex of the original polyhedral constraint region. Next, a set of first order optimality conditions is derived for the general case and used as the basis of an algorithm for the linear problem. A number of examples are given to highlight the results.     

On the structure and properties of a linear multilevel programming problem

Many decision-making situations involve multiple planners with different, and sometimes conflicting, objective functions. One type of model that has been suggested to represent such situations is the linear multilevel programming problem. However, it appears that theoretical and algorithmic results for linear multilevel programming have been limited, to date, to the bounded case or the case of when only two levels exist. In this paper, we investigate the structure and properties of a linear multilevel programming problem that may be unbounded. We study the geometry of the problem and its feasible region. We also give necessary and sufficient conditions for the problem to be unbounded, and we show how the problem is related to a certain parametric concave minimization problem. The algorithmic implications of the results are also discussed.This research was supported by National Science Foundation Grant No. ECS-85-15231.     

Multilevel preconditioning — Appending boundary conditions by Lagrange multipliers

For saddle point problems stemming from appending essential boundary conditions in connection with Galerkin methods for elliptic boundary value problems, a class of multilevel preconditioners is developed. The estimates are based on the characterization of Sobolev spaces on the underlying domain and its boundary in terms of weighted sequence norms relative to corresponding multilevel expansions. The results indicate how the various ingredients of a typical multilevel framework affect the growth rate of the condition numbers. In particular, it is shown how to realize even condition numbers that are uniformly bounded independently of the discretization.These investigations are motivated by the idea of employing nested refinable shift-invariant spaces as trial spaces covering various types of wavelets that are of advantage for the solution of boundary value problems from other points of view. Instead of incorporating the boundary conditions into the approximation spaces in the Galerkin formulation, they are appended by means of Lagrange multipliers leading to a saddle point problem.The work of the author is partially supported by the Deutsche Forschungsgemeinschaft under grant numbers Ku1028/1-1 and Pr336/4-1.     

Optimal compromise solution of multi-objective minimal cost flow problems in fuzzy environment

Ghatee and Hashemi [M. Ghatee, S.M. Hashemi, Ranking function-based solutions of fully fuzzified minimal cost flow problem, Inform. Sci. 177 (2007) 4271–4294] transformed the fuzzy linear programming formulation of fully fuzzy minimal cost flow (FFMCF) problems into crisp linear programming formulation and used it to find the fuzzy optimal solution of balanced FFMCF problems. In this paper, it is pointed out that the method for transforming the fuzzy linear programming formulation into crisp linear programming formulation, used by Ghatee and Hashemi, is not appropriate and a new method is proposed to find the fuzzy optimal solution of multi-objective FFMCF problems. The proposed method can also be used to find the fuzzy optimal solution of single-objective FFMCF problems. To show the application of proposed method in real life problems an existing real life FFMCF problem is solved.     

On Linear Fractional Programming Problem and its Computation Using a Neural Network Model

In this paper we consider linear fractional programming problem and look at its linear complementarity formulation. In the literature, uniqueness of solution of a linear fractional programming problem is characterized through strong quasiconvexity. We present another characterization of uniqueness through complementarity approach and show that the solution set of a fractional programming problem is convex. Finally we formulate the complementarity condition as a set of dynamical equations and prove certain results involving the neural network model. A computational experience is also reported.      

A multi-parametric programming approach for multilevel hierarchical and decentralised optimisation problems

In this paper, we outline the foundations of a general global optimisation strategy for the solution of multilevel hierarchical and general decentralised multilevel problems, based on our recent developments on multi-parametric programming and control theory. The core idea is to recast each optimisation subproblem, present in the hierarchy, as a multi-parametric programming problem, with parameters being the optimisation variables belonging to the remaining subproblems. This then transforms the multilevel problem into single-level linear/convex optimisation problems. For decentralised systems, where more than one optimisation problem is present at each level of the hierarchy, Nash equilibrium is considered. A three person dynamic optimisation problem is presented to illustrate the mathematical developments.     

Minimising total average cycle stock subject to practical constraints

Silver and Moon (J Opl Res Soc 50(8) (1999) 789–796) address the problem of minimising total average cycle stock subject to two practical constraints. They provide a dynamic programming formulation for obtaining an optimal solution and propose a simple and efficient heuristic algorithm. Hsieh (J Opl Res Soc 52(4) (2001) 463–470) proposes a 0–1 linear programming approach to the problem and a simple heuristic based on the relaxed 0–1 programming formulation. We show in this paper that the formulation of Hsieh can be improved for solving very large size instances of this inventory problem. So the mathematical approach is interesting for several reasons: the definition of the model is simple, its implementation is immediate by using a mathematical programming language together with a mixed integer programming software and the performance of the approach is excellent. Computational experiments carried out on the set of realistic examples considered in the above references are reported. We also show that the general framework for modelling given by mixed integer programming allows the initial model to be extended in several interesting directions.     

Finding an efficient solution to linear bilevel programming problem: An effective approach

Multilevel programming is developed to solve the decentralized problem in which decision makers (DMs) are often arranged within a hierarchical administrative structure. The linear bilevel programming (BLP) problem, i.e., a special case of multilevel programming problems with a two level structure, is a set of nested linear optimization problems over polyhedral set of constraints. Two DMs are located at the different hierarchical levels, both controlling one set of decision variables independently, with different and perhaps conflicting objective functions. One of the interesting features of the linear BLP problem is that its solution may not be Paretooptimal. There may exist a feasible solution where one or both levels may increase their objective values without decreasing the objective value of any level. The result from such a system may be economically inadmissible. If the decision makers of the two levels are willing to find an efficient compromise solution, we propose a solution procedure which can generate effcient solutions, without finding the optimal solution in advance. When the near-optimal solution of the BLP problem is used as the reference point for finding the efficient solution, the result can be easily found during the decision process.     

Natural gas cash-out problem: Bilevel stochastic optimization approach

A stochastic formulation of the natural gas cash-out problem is given in a form of a bilevel multi-stage stochastic programming model with recourse. After reducing the original formulation to a bilevel linear problem, a stochastic scenario tree is defined by its node events, and time series forecasting is used to produce stochastic values for data of natural gas price and demand. Numerical experiments were run to compare the stochastic solution with the perfect information solution and the expected value solutions.     

The minimum distance superset problem: formulations and algorithms

The partial digest problem consists in retrieving the positions of a set of points on the real line from their unlabeled pairwise distances. This problem is critical for DNA sequencing, as well as for phase retrieval in X-ray crystallography. When some of the distances are missing, this problem generalizes into a “minimum distance superset problem”, which aims to find a set of points of minimum cardinality such that the multiset of their pairwise distances is a superset of the input. We introduce a quadratic integer programming formulation for the minimum distance superset problem with a pseudo-polynomial number of variables, as well as a polynomial-size integer programming formulation. We investigate three types of solution approaches based on an available integer programming solver: (1) solving a linearization of the pseudo-polynomial-sized formulation, (2) solving the complete polynomial-sized formulation, or (3) performing a binary search over the number of points and solving a simpler feasibility or optimization problem at each step. As illustrated by our computational experiments, the polynomial formulation with binary search leads to the most promising results, allowing to optimally solve most instances with up to 25 distance values and 8 solution points.     

Gap Functions and Existence of Solutions to Set-Valued Vector Variational Inequalities

The variational inequality problem with set-valued mappings is very useful in economics and nonsmooth optimization. In this paper, we study the existence of solutions and the formulation of solution methods for vector variational inequalities (VVI) with set-valued mappings. We introduce gap functions and establish necessary and sufficient conditions for the existence of a solution of the VVI. It is shown that the optimization problem formulated by using gap functions can be transformed into a semi-infinite programming problem. We investigate also the existence of a solution for the generalized VVI with a set-valued mapping by virtue of the existence of a solution of the VVI with a single-valued function and a continuous selection theorem.     

An error analysis and the mesh independence principle for a nonlinear collocation problem

A nonlinear Dirichlet boundary value problem is approximated by an orthogonal spline collocation scheme using piecewise Hermite bicubic functions. Existence, local uniqueness, and error analysis of the collocation solution and convergence of Newton's method are studied. The mesh independence principle for the collocation problem is proved and used to develop an efficient multilevel solution method. Simple techniques are applied for estimating certain discretization and iteration constants that are used in the formulation of a mesh refinement strategy and an efficient multilevel method. Several mesh refinement strategies for solving a test problem are compared numerically. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2006     

Using a Conic Formulation for Finding Steiner Minimal Trees

We present a new mathematical programming formulation for the Steiner minimal tree problem. We relax the integrality constraints on this formulation and transform the resulting problem (which is convex, but not everywhere differentiable) into a standard convex programming problem in conic form. We consider an efficient computation of an ε-optimal solution for this latter problem using an interior-point algorithm.     

Lower bounds for nonlinear assignment problems using many body interactions

This paper concerns lower bounding techniques for the general α-adic assignment problem. The nonlinear objective function is linearized by the introduction of additional variables and constraints, thus yielding a mixed integer linear programming formulation of the problem. The concept of many body interactions is introduced to strengthen this formulation and incorporated in a modified formulation obtained by lifting the original representation to a higher dimensional space. This process involves two steps — (i) addition of new variables and constraints and (ii) incorporation of the new variables in the objective function. If this lifting process is repeated β times on an α-adic assignment problem along with the incorporation of higher order interactions, it results in the mixed-integer formulation of an equivalent (α + β)-adic assignment problem. The incorporation of many body interactions in the higher dimensional formulation improves its degeneracy properties and is also critical to the derivation of decomposition methods for the solution of these large scale mathematical programs in the higher dimensional space. It is shown that a lower bound to the optimal solution of the corresponding linear programming relaxation can be obtained by dualizing a subset of constraints in this formulation and solving O(N^2(α+β−1)) linear assignment problems, whose coefficients depend on the dual values. Moreover, it is proved that the optimal solution to the LP relaxation is obtained if we use the optimal duals for the solution of the linear assignment problems. This concept of many body interactions could be applied in designing algorithms for the solution of formulations obtained by lifting general MILP's. We illustrate all these concepts on the quadratic assignment problems With these decomposition bounds, we have found the provably optimal solutions of two unsolved QAP's of size 32 and have also improved upon existing lower bounds for other QAP's.     

A new approximation algorithm for the multilevel facility location problem

In this paper we propose a new integer programming formulation for the multilevel facility location problem and a novel 3-approximation algorithm based on LP-rounding. The linear program that we use has a polynomial number of variables and constraints, thus being more efficient than the one commonly used in the approximation algorithms for these types of problems.     

多层线性规划问题的整体优化算法

本文研究了求解多层线性规划问题的整体优化算法,利用流动等值面技术,证明了算法的有限终止性,并给出实际例子验证了算法的有效性.     

Unrelated machine scheduling with time-window and machine downtime constraints: An application to a naval battle-group problem

This paper deals with an unrelated machine scheduling problem of minimizing the total weighted flow time, subject to time-window job availability and machine downtime side constraints. We present a zero-one integer programming formulation of this problem. The linear programming relaxation of this formulation affords a tight lower bound and often generates an integer optimal solution for the problem. By exploiting the special structures inherent in the formulation, we develop some classes of strong valid inequalities that can be used to tighten the initial formulation, as well as to provide cutting planes in the context of a branch-and-cut procedure. A major computational bottleneck is the solution of the underlying linear programming relaxation because of the extremely high degree of degeneracy inherent in the formulation. In order to overcome this difficulty, we employ a Lagrangian dual formulation to generate lower and upper bounds and to drive the branch-and-bound algorithm. As a practical instance of the unrelated machine scheduling problem, we describe a combinatorial naval defense problem. This problem seeks to schedule a set of illuminators (passive homing devices) in order to strike a given set of targets using surface-to-air missiles in a naval battle-group engagement scenario. We present computational results for this problem using suitable realistic data.     

A weak linearization of the Kuhn-tucker conditions for a class of allocation problems

The return obtained from the allocation of resources to an activity is occasionally modelled by means of concave, strictly increasing functions. Exponential functions of a certain class conveniently lend themselves to such modelling. A nonlinear programming formulation of a multiresource allocation problem with return functions of the class appears to have Kuhn-Tucker conditions which in a sense are intrinsically linear. The paper shows how this fact can be utilised to save processing time in the execution of numerical algorithms for the solution of this mathematical programming problem.