In this thesis we are concerned with optimisation over the non-dominated set of a multiobjective optimisation problem. A multi-objective optimisation problem (MOP) involves multiple conflicting objective functions. The non-dominated set of this problem is of interest because it is composed of the “best” trade-off for a decision maker to choose according to his preference. We assume that this selection process can be modelled by maximising a function over the non-dominated set. We present two new algorithms for the optimisation of a linear function over the non-dominated set of a multi-objective linear programme (MOLP). A primal method is developed based on a revised version of Benson’s outer approximation algorithm. A dual method derived from the dual variant of the outer approximation algorithm is proposed. Taking advantage of some special properties of the problem, the new methods are designed to achieve better computational efficiency. We compare the two new algorithms with several algorithms from the literature on a set of randomly generated instances. The results show that the new algorithms are considerably faster than the competitors. We adapt the two new methods for the determination of the nadir point of (MOLP). The nadir point is characterized by the componentwise worst values of the non-dominated points of (MOP). This point is a prerequisite for many multi-criteria decision making (MCDM) procedures. Computational experiments against another exact method for this purpose from the literature reveal that the new methods are faster than the competitor. The last section of the thesis is devoted to optimising a linear function over the non-dominated set of a convex multi-objective problem. A convex multi-objective problem (CMOP) often involves nonlinear objective functions or constraints. We extend the primal and the dual methods to solve this problem. We compare the two algorithms with several existing algorithms from the literature on a set of randomly generated instances. The results reveal that the new methods are much faster than the others.

In this thesis we consider, from a computability perspective, the question of what order-theoretic properties of a partial order can be preserved under linear extension. It is well-known that such properties as well-foundedness or scatteredness can be preserved, that is, given any well-founded partial order you can find a well-founded linear extension and mutatis mutandis for scattered partial orders. An order type σ is extendible if a partial order that does not embed σ can always be extended to a linear order that does not extend σ. So for example “given any well-founded partial order, you can find a well-founded linear extension” is equivalent to saying that ω^∗ is extendible. The extendible order types were classified by Bonnet [3] in 1969. We define notions of computable extendibility and then apply them to investigate the computable extendibility of three commonly used order types, ω^∗ , ω^∗ + ω and η. In Chapter 2 we prove that given a computably well-founded computable partial order, you can find a computably well-founded ω-c.e. linear extension, and further that this result doesn’t hold for n-c.e. for any finite n. In Chapter 3 we show how to extend these results for linearisations of computable partial orders which do not embed ζ = ω^∗ + ω. In Chapter 4 we prove the analogous results for scattered partial orders.

No description available.

The main objectives of this thesis are (i) to develop primal-dual interior point algorithms for solving Nonlinear Programming (NLP) problems (ii) to develop a branch and cut algorithm for solving 0-1 Mixed Integer Nonlinear Programming (MINLP) problems and (iii) the application of the interior point algorithms to solve the NLP problems arising during the solution process of a 0-1 MINLP problem. Two primal-dual interior point algorithms are developed for solving NLP problems with both equality and inequality constraints. In the first algorithm the perturbed optimality conditions of the initial problem are solved by using a quasi- Newton method. The descent property of the search direction is established for a penalty-barrier merit function, based on an approximation of Fletcher's exact and differentiable penalty function. In the second algorithm, an equivalent problem is formulated with the equality constraints incorporated into the objective by means of the quadratic penalty function. The inequality constraints are also included into the objective by means of the logarithmic barrier function. The optimality conditions of the transformed problem are solved by using a quasi-Newton method. The descent property of the search direction is ensured for a merit function, using an adaptive strategy to determine the penalty parameter. Global convergence of both interior point algorithms is achieved through line search procedures that ensure the monotonic decrease of the corresponding merit function. Numerical results demonstrate the efficient performance of both algorithms for a variety of test problems. A branch and cut algorithm is also developed for solving 0-1 MINLP problems. The algorithm integrates Branch and Bound, Outer Approximation and Gomory Cutting Planes. Only the initial Mixed Integer Linear Programming (MILP) master problem is considered. At integer solutions NLP problems are solved, using the primal-dual interior point algorithms mentioned above. The objective and constraints are linearized at the optimum solution of those NLP problems and the linearizations are added to all the unsolved nodes of the enumerations tree. Also, Gomory cutting planes, which are valid throughout the tree, are generated at selected nodes. These cuts help the algorithm to locate integer solutions quickly and consequently improve the linear approximation of the objective and constraints, held at the unsolved nodes of the tree. Numerical results show that the addition of Gomory cuts can reduce the number of nodes in the enumeration tree.

The subject of this thesis is the well-known problem in the theory of mathematical programming, the cutting stock problem. Its applications are numerous, occurring whenever material must be cut from "master" items, but this thesis is primarily concerned with the paper industry, where the cutting and slitting of big sheets of paper into smaller ones is an important and cost-sensitive part of the manufacturing process. Algorithms described in Chapters 2 and 3 solve certain classes of such problems to optimality (in the sense of having the least possible waste) in reasonable time. These classes include the one-dimensional problem, the one-and-a-half dimensional problem and certain two-stage problems. For each of these classes we report on industrial case studies in the paper and board industry. This is, apparently, the first time in the published literature that such optimal solutions for these problems have been routinely generated. This work has resulted in the development of two commercial packages - used on a daily basis in six paper and board mills, the first of which was installed in February 1985. In these sites, savings in the range of 1%-5% in utilisation have been achieved as compared against other programs or human practice. in Chapter 4 a heuristic algorithm is developed for rearranging a previously generated solution to reduce the number of knife settings required. Another heuristic takes existing solutions and reduces the number of patterns present in the solution. We describe a general framework for solving assortment problems and examine its application in the paper industry. Finally, statistical techniques are used to answer such "green-field site" questions as what are good geometric characteristics for a paper machine, and what is the relationship between waste and run length.

In this work we address the problem of identifying a discrete-time nonlinear system composed of a linear dynamical system connected to a static nonlinear component. We use linear fractional representation to provide a united framework for the identification of two classes of such systems. The first class consists of discrete-time systems consists of a linear time invariant system connected to a continuous nonlinear static component. The identification problem of estimating the unknown parameters of the linear system and simultaneously fitting a math order spline to the nonlinear data is addressed. A simple and tractable algorithm based on the separable least squares method is proposed for estimating the parameters of the linear and the nonlinear components. We also provide a sufficient condition on data for consistency of the identification algorithm. Numerical examples illustrate the performance of the algorithm. Further, we examine a second class of systems that may involve a nonlinear static element of a more complex structure. The nonlinearity may not be continuous and is approximated by piecewise a±ne maps defined on different convex polyhedra, which are defined by linear combinations of lagged inputs and outputs. An iterative identification procedure is proposed, which alternates the estimation of the linear and the nonlinear subsystems. Standard identification techniques are applied to the linear subsystem, whereas recently developed piecewise affine system identification techniques are employed for the estimation of the nonlinear component. Numerical examples show that the proposed procedure is able to successfully profit from the knowledge of the interconnection structure, in comparison with a direct black box identification of the piecewise a±ne system.

For theoretical and practical reasons, quadratic programming problems have attracted the interest of the mathematical programming community. They naturally arise from applications and as subproblems in other numerical techniques. However most existing techniques, designed for solving small and dense problems, tend to be prohibitively expensive when applied directly to solve large-scale problems. In this work we explore methods suitable for solving large-scale sparse convex quadratic programming problems. An interior-point primal-dual algorithmic framework and its computational implementation are presented in the first part of this work. Primal and dual updates are computed at each step by iteratively solving the linear systems posed by the classical method of barriers using a preconditioned Krylov-subspace method. Several variants are suggested by a Taylor approximation of the central path. A truncated Newton strategy has been implemented in order to achieve a significant reduction in the CPU time. In the second part, sparse implementations for Lemke's algorithm and a row-action algorithm based on diagonal approximations of the Hessian, are suggested. Lemke's algorithm implementation is based on updating the sparse LU factorization of a matrix representing the basis at the current step. The implementation of the row-action algorithm relies on the efficient solution of single-constrained diagonal subproblems. In order to compare the relative merits of our implementations, numerical experimentation is conducted on two sets of problems that use randomly generated Hessian matrices and constraints taken from a subset of the netlib problems. Several aspects are studied: the use of iterative linear algebra for solving the linear systems of equations posed by the interior-point variants, the impact on the computational resources (memory and CPU) when different approaches are used to solve large scale problems, and finally, the effectiveness of a second order correction and the truncated Newton strategy implemented in the interior-point methods.

No description available.

In this thesis, we study the portfolio selection problem with multiple risky assets, linear transaction costs and a risk measure in a multi-period setting. In particular, we formulate the multi-period portfolio selection problem as a dynamic program and to solve it we construct approximate dynamic programming (ADP) algorithms, where we include Conditional-Value-at-Risk (CVaR) as a measure of risk, for different separable functional approximations of the value functions. We begin with the simple linear approximation which does not capture the nature of the portfolio selection problem since it ignores risk and leads to portfolios of only one asset. To improve it, we impose upper bound constraints on the holdings of the assets and we notice that we have more diversified portfolios. Then, we implement a piecewise linear approximation, for which we construct an update rule for the slopes of the approximate value functions that preserves concavity as well as the number of slopes. Unlike the simple linear approximation, in the piecewise linear approximation we notice that risk affects the composition of the selected portfolios. Further, unlike the linear approximation with upper bounds, here wealth flows naturally from one asset to another leading to diversified portfolios without us needing to impose any additional constraints on how much we can hold in each asset. For comparison, we consider existing portfolio selection methods, both myopic ones such as the equally weighted and a single-period portfolio models, and multi-period ones such as multistage stochastic programming. We perform extensive simulations using real-world equity data to evaluate the performance of all methods and compare all methods to a market Index. Computational results show that the piecewise linear ADP algorithm significantly outperforms the other methods as well as the market and runs in reasonable computational times. Comparative results of all methods are provided and some interesting conclusions are drawn especially when it comes to comparing the piecewise linear ADP algorithms with multistage stochastic programming.

The asymmetric distance-constrained vehicle routing problem (ADVRP) looks at finding vehicle tours to connect all customers with a depot, such that the total distance is minimised; each customer is visited once by one vehicle; every tour starts and ends at a depot; and the travelled distance by each vehicle is less than or equal to the given maximum value. We present three basic results in this thesis. In the first one, we present a general flow-based formulation to ADVRP. It is suitable for symmetric and asymmetric instances. It has been compared with the adapted Bus School Routing formulation and appears to solve the ADVRP faster. Comparisons are performed on random test instances with up to 200 customers. We reach a conclusion that our general formulation outperforms the adapted one. Moreover, it finds the optimal solution for small test instances quickly. For large instances, there is a high probability that an optimal solution can be found or at least improve upon the value of the best feasible solution found so far, compared to the other formulation which stops because of the time condition. This formulation is more general than Kara formulation since it does not require the distance matrix to satisfy the triangle inequality. The second result improves and modifies an old branch-and-bound method suggested by Laporte et al. in 1987. It is based on reformulating a distance-constrained vehicle routing problem into a travelling salesman problem and uses the assignment problem as a lower bounding procedure. In addition, its algorithm uses the best-first strategy and new branching rules. Since this method was fast but memory consuming, it would stop before optimality is proven. Therefore, we introduce randomness in choosing the node of the search tree in case we have more than one choice (usually we choose the smallest objective function). If an optimal solution is not found, then restart is required due to memory issues, so we restart our procedure. In that way, we get a multistart branch and bound method. Computational experiments show that we are able to exactly solve large test instances with up to 1000 customers. As far as we know, those instances are much larger than instances considered for other VRP models and exact solution approaches from recent literature. So, despite its simplicity, this proposed algorithm is capable of solving the largest instances ever solved in literature. Moreover, this approach is general and may be used in solving other types of vehicle routing problems. In the third result, we use VNS as a heuristic to find the best feasible solution for groups of instances. We wanted to determine how far the difference is between the best feasible solution obtained by VNS and the value of optimal solution in order to use the output of VNS as an initial feasible solution (upper bound procedure) to improve our multistart method. Unfortunately, based on the search strategy (best first search), using a heuristic to find an initial feasible solution is not useful. The reason for this is because the branch and bound is able to find the first feasible solution quickly. In other words, in our method using a good initial feasible solution as an upper bound will not increase the speed of the search. However, this would be different for the depth first search. However, we found a big gap between VNS feasible solution and an optimal solution, so VNS can not be used alone unless for large test instances when other exact methods are not able to find any feasible solution because of memory or stopping conditions.