In this thesis, we present a novel algorithm for the solution of multiparametric mixed integer linear programming ( MP-MILP ) problems that exhibit uncertain objective function coefficients and uncertain entries in the right-hand side constraint vector. The algorithmic procedure employs a branch and bound strategy that involves the solution of a multiparametric linear programming sub-problem at leaf nodes and appropriate comparison procedures to update the tree. McCormick relaxation procedures are employed to overcome the presence of bilinear terms in the model. The algorithm generates an envelope of parametric profiles, containing the optimal solution of the MP-MILP problem. The parameter space is partitioned into polyhedral convex critical regions. Two examples are presented to illustrate the steps of the proposed algorithm.

We present a form of  Farkers lemma for bilevel inequality systems and use it to obtain an important characterization of global solutions of a class of bilevel polynomial programs with lower- level linear programs. It should be noted the objective functions of the upper- level polynomial programs are coercive polynomial. Polynomial function f is called coercive polynomial whenever

iminf ∥x∥ f(x) = +∞ .

Consequently, we show that a sequence of optimal solutions of related semidefinite linear programs converges to the global optimal solution of a bilevel polynomial program under suitable conditions. Also we obtain the global optimal value of the bilevel polynomial program by using YALMIP toolbox.  

Bilevel programming involves two optimization problems where the constraint region of the upper level problem is determined by another optimization problem. In this paper ,at first, we briefly consider quasiconcave bilevel programming problem without  upper level constraint and the special case of them , namely fractional linear bilevel programming problem. Then we consider quasiconcave bilevel problems over polyhedra with coupling constraints. On the other hand,under the uniqueness of the optimal solution of the lower level problem , we prove that the fact that the objective functions of both levels are quasiconcave characterizes the property of the existence of extreme point of the polyhedron defined by the whole set of constraints which is an optimal solution of the bilevel problem and An example is used to show that this property is in general violated if the optimal solution of the lower level problem is not unique, On the other hand, if the lower level objective function is convex quadratic, assumig the optimistic approach we prove that the optimal solution is attained at an extreme point of an enlarged polyhedron. Also we consider the effect of shifting constraints from one level to the other on the optimal solution of BLP.

Primal-dual interior-point methods are the most efficient methods for a computational point of view. In this thesis we intoduce a new kind of kernel function, which yields efficient large-update primal-dual interior point methods. Then we conclude that in some situations its iteration bounds order are O(m^((3m+1)/2m) n^((m+1)/2m) log(n/ϵ) ), which are at least as good as the best known bounds order so far,

 O(√n log(n  log(n/ϵ)) for large-update primal-dual interior-point methods. The result decreases the gap between the practical behavior of the large-update algorithms and their theoretical performance results, which is an open problem. Numerical results show that the efficiency of proposed algorithm

Abstract : We can develope the simplex method for solving piecewise linear programming problem (PLP) and linear fractional programming problem(LFP) . In this thesis we consider a further generalization of the simplex method to solve piecewise - linear fractional programming prolems (PLFP). Linear programming problem( LP) , PLP and LFP are all special cases of PLFP . The simplex algorithm introduced in this thesis for solving PLFP provideds a unified framework for solving several important optimization problems .

Bilevel linear programming (BLP) problem is an optimization problem in which a subset of the decision variables are constrained to lie in the optimal set of a second level optimization problem and it has the continuous variables and linear objective functions.
Each the BLP problem consists of two problems. The upper level problem that it called as leader and the lower level problem is called follower.
A linear programming problem has at least a binary variable which is known as linear mixed integer programming problem (MIP 0-1). In this thesis , BLP problem is reformulated as MIP , then we introduce integerality cuts for it. By using these cuts , we present the new branch and cut (CCB) algorithm for solving BLP problem. The algorithm is composed of two phases. The first one is a cutting-plane phase whose goal is to improve the value of the upper bound on the objective function value. It is an iterative step where at each iteration a valid cut is generated and added to the linear relaxation problem. After a maximal number of iterations , the second phase -a branch and bound phase - is triggered in order to ensure finite and exact convergence of the algorithm. We illustrated this algorithm completely. Also by showing the numerical results which tested on a series of randomly generated problems , CCB algorithm compromised to pure branch and bound algorithm in terms of computing times , number of nodes explored in branch and bound tree.

 

One of the most common approaches for multiobjective optimization is to generate the whole or partial efficient frontierand then decide about the preferred solution in a higher-level decision-making process. In this paper, a new methodfor generating the efficient frontier for multiobjective problems is developed, called the diversity maximization approach(DMA). This approach is capable of solving mixed-integer and combinatorial problems. The DMA finds Pareto optimalsolutions by maximizing a proposed diversity measure and guarantees generating the complete set of efficient points. Givena subset of the efficient frontier, DMA finds the next Pareto optimal solution which, combined with the existing ones,yields the most diversified subset of efficient points.
An additional way of using DMA is by incorporating it in a problem oriented branch-and-bound algorithm.
Detailed examples of both approaches are given.