On the use of internal rate of return in linear and integer programming

Internal rate of return (IRR) is used as a criterion many investment decisions. For example many issuers of new municipal debt evaluate competitive bids on the basis of IRR. We incorporate IRR into mathematical programming formulations in such a way that the resulting problem becomes linear. This linearization permits linear programming and integer linear programming algorithms to be brought to bear on problems which had heretofore been solved in an iterative, time consuming fashion.     

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.     

A Simultaneous Enumeration Approach to the Traveling Salesman Problem

The solution procedure proposed in this paper uses certain principles of analog computers. The idea of using analog rather than digital computers to solve mathematical programming problems is not new—various methods have been proposed to solve linear programming, network flows, as well as shortest path problems (Dennis, 1959; Stern, 1965). These problems can be more efficiently solved with digital computers. To find a solution to the traveling salesman problem as well as other integer programming problems is difficult with existing hardware, especially if the number of variables is large. The question thus arises whether different hardware configurations make it possible to solve integer problems more efficiently. One such configuration is proposed below for the traveling salesman problem.     

Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming

Decomposition has proved to be one of the more effective tools for the solution of large-scale problems, especially those arising in stochastic programming. A decomposition method with wide applicability is Benders' decomposition, which has been applied to both stochastic programming as well as integer programming problems. However, this method of decomposition relies on convexity of the value function of linear programming subproblems. This paper is devoted to a class of problems in which the second-stage subproblem(s) may impose integer restrictions on some variables. The value function of such integer subproblem(s) is not convex, and new approaches must be designed. In this paper, we discuss alternative decomposition methods in which the second-stage integer subproblems are solved using branch-and-cut methods. One of the main advantages of our decomposition scheme is that Stochastic Mixed-Integer Programming (SMIP) problems can be solved by dividing a large problem into smaller MIP subproblems that can be solved in parallel. This paper lays the foundation for such decomposition methods for two-stage stochastic mixed-integer programs.     

A Representation and Economic Interpretation of a Two-Level Programming Problem

This paper first presents a formulation for a class of hierarchial problems that show a two-stage decision making process; this formulation is termed multilevel programming and could be defined, in general, as a mathematical programming problem (master) containing other multilevel programs in the constraints (subproblems). A two-level problem is analyzed in detail, and we develop a solution procedure that replaces the subproblem by its Kuhn-Tucker conditions and then further transforms it into a mixed integer quadratic programming problem by exploiting the disjunctive nature of the complementary slackness conditions.An example problem is solved and the economic implications of the formulation and its solution are reviewed.     

An optimization model for combined selecting,planting and harvesting sugarcane varieties

The problem of selecting sugarcane varieties has been widely discussed due to its computational complexity and its great impact for the sugar and ethanol industry. This paper proposes a new integrated mathematical programming model to deal with the selection of sugarcane varieties to be planted and the determination of the optimal period for planting and harvesting in order to increase production in the sugarcane industry. The proposed model optimizes the production of sugarcane and improves the quality of biomass whilst satisfying the main constraints imposed by sugarcane companies. The problem is modelled as an integer linear program and solved using an exact method to generate optimal solutions for small and medium problems. For large problems, metaheuristic approaches based on Genetic Algorithm and Variable Neighbourhood Search are proposed. According to the results, the proposed methodology provides sugarcane company managers with decision support in selecting the most suitable varieties and in determining the best period to plant and harvest their sugarcane.

     

MOP/GP models for machine learning

Techniques for machine learning have been extensively studied in recent years as effective tools in data mining. Although there have been several approaches to machine learning, we focus on the mathematical programming (in particular, multi-objective and goal programming; MOP/GP) approaches in this paper. Among them, Support Vector Machine (SVM) is gaining much popularity recently. In pattern classification problems with two class sets, its idea is to find a maximal margin separating hyperplane which gives the greatest separation between the classes in a high dimensional feature space. This task is performed by solving a quadratic programming problem in a traditional formulation, and can be reduced to solving a linear programming in another formulation. However, the idea of maximal margin separation is not quite new: in the 1960s the multi-surface method (MSM) was suggested by Mangasarian. In the 1980s, linear classifiers using goal programming were developed extensively.This paper presents an overview on how effectively MOP/GP techniques can be applied to machine learning such as SVM, and discusses their problems.     

Multiprocessor scheduling under precedence constraints: Polyhedral results

We consider the problem of scheduling a set of tasks related by precedence constraints to a set of processors, so as to minimize their makespan. Each task has to be assigned to a unique processor and no preemption is allowed. A new integer programming formulation of the problem is given and strong valid inequalities are derived. A subset of the inequalities in this formulation has a strong combinatorial structure, which we use to define the polytope of partitions into linear orders. The facial structure of this polytope is investigated and facet defining inequalities are presented which may be helpful to tighten the integer programming formulation of other variants of multiprocessor scheduling problems. Numerical results on real-life problems are presented.     

A method for solving the general parametric linear complementarity problem

This paper presents a solution method for the general (mixed integer) parametric linear complementarity problem pLCP(q(θ),M), where the matrix M has a general structure and integrality restriction can be enforced on the solution. Based on the equivalence between the linear complementarity problem and mixed integer feasibility problem, we propose a mixed integer programming formulation with an objective of finding the minimum 1-norm solution for the original linear complementarity problem. The parametric linear complementarity problem is then formulated as multiparametric mixed integer programming problem, which is solved using a multiparametric programming algorithm. The proposed method is illustrated through a number of examples.     

Berth allocation at indented berths for mega-containerships

This paper addresses the berth allocation problem at a multi-user container terminal with indented berths for fast handling of mega-containerships. In a previous research conducted by the authors, the berth allocation problem at a conventional form of the multi-user terminal was formulated as a nonlinear mathematical programming, where more than one ship are allowed to be moored at a specific berth if the berth and ship lengths restriction is satisfied. In this paper, we first construct a new integer linear programming formulation for easier calculation and then the formulation is extended to model the berth allocation problem at a terminal with indented berths, where both mega-containerships and feeder ships are to be served for higher berth productivity. The berth allocation problem at the indented berths is solved by genetic algorithms. A wide variety of numerical experiments were conducted and interesting findings were explored.     

A heuristic for scheduling problems,especially for scheduling farm operations

Scheduling problems in agriculture are often solved using techniques such as linear programming (the multi-period formulation) and dynamic programming. But it is difficult to obtain an optimal schedule with these techniques for any but the smallest problems, because the model is unwieldly and much time is needed to solve the problem. Therefore, a new algorithm, a heuristic, has been developed to handle scheduling problems in agriculture. It is based on a search technique (i.e. hill-climbing) supported by a strong heuristic evaluation function. In this paper the heuristic performance is compared with dynamic programming. The heuristic offers near-optimal solutions and is much faster than the dynamic programming model. When tested against dynamic programming the difference in results was about 3%. This heuristic could probably also be applied in an industrial environment (e.g. agribusiness or road construction).     

Constraint Programming and Hybrid Formulations for Three Life Designs

Conway's game of Life provides an interesting testbed for exploring issues in formulation, symmetry, and optimization with constraint programming and hybrid constraint programming/integer programming methods. We consider three Life pattern-creation problems: finding maximum density still-Lifes, finding smallest immediate predecessor patterns, and finding period-2 oscillators. For the first two problems, integrating integer programming and constraint programming approaches provides a much better solution procedure than either individually. For the final problem, the constraint programming formulation provides the better approach.     

Polynomial Algorithms for a Class of Discrete Minmax Linear Programming Problems

We consider the problem of obtaining integer solutions to a minmax linear programming problem. Although this general problem is NP-complete, it is shown that a restricted version of this problem can be solved in polynomial time. For this restricted class of problems two polynomial time algorithms are suggested, one of which is strongly polynomial whenever its continuous analogue and an associated linear programming problem can be solved by a strongly polynomial algorithm. Our algorithms can also be used to obtain integer solutions for the minmax transportation problem with an inequality budget constraint. The equality constrained version of this problem is shown to be NP-complete. We also provide some new insights into the solution procedures for the continuous minmax linear programming problem.     

Comparative studies on dynamic programming and integer programming approaches for concave cost production/inventory control problems

This paper is concerned with classical concave cost multi-echelon production/inventory control problems studied by W. Zangwill and others. It is well known that the problem with m production steps and n time periods can be solved by a dynamic programming algorithm in O(n ⁴ m) steps, which is considered as the fastest algorithm for solving this class of problems. In this paper, we will show that an alternative 0–1 integer programming approach can solve the same problem much faster particularly when n is large and the number of 0–1 integer variables is relatively few. This class of problems include, among others problem with set-up cost function and piecewise linear cost function with fewer linear pieces. The new approach can solve problems with mixed concave/convex cost functions, which cannot be solved by dynamic programming algorithms.     

Fair transfer price and inventory holding policies in two-enterprise supply chains

A key issue in supply chain optimisation involving multiple enterprises is the determination of policies that optimise the performance of the supply chain as a whole while ensuring adequate rewards for each participant.In this paper, we present a mathematical programming formulation for fair, optimised profit distribution between echelons in a general multi-enterprise supply chain. The proposed formulation is based on an approach applying the Nash bargaining solution for finding optimal multi-partner profit levels subject to given minimum echelon profit requirements.The overall problem is first formulated as a mixed integer non-linear programming (MINLP) model. A spatial and binary variable branch-and-bound algorithm is then applied to the above problem based on exact and approximate linearisations of the bilinear terms involved in the model, while at each node of the search tree, a mixed integer linear programming (MILP) problem is solved. The solution comprises inter-firm transfer prices, production and inventory levels, flows of products between echelons, and sales profiles.The applicability of the proposed approach is demonstrated by a number of illustrative examples based on industrial processes.     

Strong valid inequalities for fluence map optimization problem under dose-volume restrictions

Fluence map optimization problems are commonly solved in intensity modulated radiation therapy (IMRT) planning. We show that, when subject to dose-volume restrictions, these problems are NP-hard and that the linear programming relaxation of their natural mixed integer programming formulation can be arbitrarily weak. We then derive strong valid inequalities for fluence map optimization problems under dose-volume restrictions using disjunctive programming theory and show that strengthening mixed integer programming formulations with these valid inequalities has significant computational benefits.     

The single-assignment hub covering problem: Models and linearizations

We study the hub covering problem which, so far, has remained one of the unstudied hub location problems in the literature. We give a combinatorial and a new integer programming formulation of the hub covering problem that is different from earlier integer programming formulations. Both new and old formulations are nonlinear binary integer programs. We give three linearizations for the old model and one linearization for the new one and test their computational performances based on 80 instances of the CAB data set. Computational results indicate that the linear version of the new model performs significantly better than the most successful linearization of the old model both in terms of average and maximum CPU times as well as in core storage requirements.     

Upper Bounds on the Covering Number of Galois-Planes with Small Order

Our paper deals with the covering number of finite projective planes which is related to an unsolved question of P. Erdös. An integer linear programming (ILP) formulation of the covering number of finite projective planes is introduced for projective planes of given orders. The mathematical programming based approach for this problem is new in the area of finite projective planes. Since the ILP problem is NP-hard and may involve up to 360.000 boolean variables for the considered problems, we propose a heuristic based on Simulated Annealing. The computational study gives a new insight into the structure of projective planes and their (minimal) blocking sets. This computational study indicates that the current theoretical results may be improved.