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.     

Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices

We present branching-on-hyperplane methods for solving mixed integer linear and mixed integer convex programs. In particular, we formulate the problem of finding a good branching hyperplane using a novel concept of adjoint lattice. We also reformulate the problem of rounding a continuous solution to a mixed integer solution. A worst case complexity of a Lenstra-type algorithm is established using an approximate log-barrier center to obtain an ellipsoidal rounding of the feasible set. The results for the mixed integer convex programming also establish a complexity result for the mixed integer second order cone programming and mixed integer semidefinite programming feasibility problems as a special case. Our results motivate an alternative reformulation technique and a branching heuristic using a generalized (e.g., ellipsoidal) norm reduced basis available at the root node.     

A comparative analysis of linear fitting for non-linear functions on optimization: A case study: Air pollution problems

A very frequent problem in advanced mathematical programming models is the linear approximation of convex and non-convex non-linear functions in either the constraints or the objective function of an otherwise linear programming problem. In this paper, based on a model that has been developed for the evaluation and selection of pollutant emission control policies and standards, we shall study several ways of representing non-linear functions of a single argument in mixed integer, separable and related programming terms. Thus we shall study the approximations based on piecewise constant, piecewise adjacent, piecewise non-adjacent additional and piecewise non-adjacent segmented functions. In each type of modelization we show the problem size and optimization results of using the following techniques: separable programming, mixed integer programming with Special Ordered Sets of type 1, linear programming with Special Ordered Sets of type 2 and mixed integer programming using strategies based on the quasi-integrality of the binary variables.     

Regulation of Overlaps in Technology Development Activities

In this paper, we present an algorithm for the solution of multiparametric mixed integer linear programming (mp-MILP) problems involving (i) 0-1 integer variables, and, (ii) more than one parameter, bounded between lower and upper bounds, present on the right hand side (RHS) of constraints. The solution is approached by decomposing the mp-MILP into two subproblems and then iterating between them. The first subproblem is obtained by fixing integer variables, resulting in a multiparametric linear programming (mp-LP) problem, whereas the second subproblem is formulated as a mixed integer linear programming (MILP) problem by relaxing the parameters as variables.     

On a pair of nonlinear mixed integer programming problems

We consider maximin and minimax nonlinear mixed integer programming problems which are nonsymmetric in duality sense. Under weaker (pseudo-convex/pseudo-concave) assumptions, we show that the supremum infimum of the maximin problem is greater than or equal to the infimum supremum of the minimax problem. As a particular case, this result reduces to the weak duality theorem for minimax and symmetric dual nonlinear mixed integer programming problems. Further, this is used to generalize available results on minimax and symmetric duality in nonlinear mixed integer programming.     

The transportation problem with exclusionary side constraints and two branch-and-bound algorithms

The transportation problem with exclusionary side constraints, a practical distribution and logistics problem, is formulated as a 0–1 mixed integer programming model. Two branch-and-bound (B&B) algorithms are developed and implemented in this study to solve this problem. Both algorithms use the Driebeek penalties to strengthen the lower bounds so as to fathom some of the subproblems, to peg variables, and to guide the selection of separation variables. One algorithm also strongly exploits the problem structure in selecting separation variables in order to find feasible solutions sooner. To take advantage of the underlying network structure of the problem, the algorithms employ the primal network simplex method to solve network relaxations of the problem. A computational experiment was conducted to test the performance of the algorithms and to characterize the problem difficulty. The commercial mixed integer programming software CPLEX and an existing special purpose algorithm specifically designed for this problem were used as benchmarks to measure the performance of the algorithms. Computational results show that the new algorithms completely dominate the existing special purpose algorithm and run from two to three orders of magnitude faster than CPLEX.     

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.     

Examining Optimal Criterion Weights in Mixed Integer Programming Approaches to the Multiple-group Classification Problem

Several mixed integer programming approaches to the multiple-group statistical classification problem are examined. Many papers have investigated conditions under which a degenerate solution occurs in linear programming approaches to the two-group discriminant problem. Very little research has been conducted in the multiple-group case. We investigate conditions under which a degenerate solution can occur in mixed integer programming approaches to the multiple-group classification problem. A multiple-group ‘minimize the sum of deviations’ model is presented. This model is similar in structure to the general single function classification model. Also, a two-goal approach to the multiple-group classification problem is discussed.     

The new Fundamental Tree Algorithm for production scheduling of open pit mines

The problem of annual production scheduling in surface mining consists of determining an optimal sequence of extracting the mineralized material from the ground. The main objective of the optimization process is usually to maximize the total Net Present Value of the operation. Production scheduling is typically a mixed integer programming (MIP) type problem. However, the large number of integer variables required in formulating the problem makes it impossible to solve. To overcome this obstacle, a new algorithm termed “Fundamental Tree Algorithm” is developed based on linear programming to aggregate blocks of material and decrease the number of integer variables and the number of constraints required within the MIP formulation. This paper proposes the new Fundamental Tree Algorithm in optimizing production scheduling in surface mining. A case study on a large copper deposit summarized in the paper shows substantial economic benefit of the proposed algorithm compared to existing methods.     

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.     

Finding all solutions of separable systems of piecewise-linear equations using integer programming

Finding all solutions of nonlinear or piecewise-linear equations is an important problem which is widely encountered in science and engineering. Various algorithms have been proposed for this problem. However, the implementation of these algorithms are generally difficult for non-experts or beginners. In this paper, an efficient method is proposed for finding all solutions of separable systems of piecewise-linear equations using integer programming. In this method, we formulate the problem of finding all solutions by a mixed integer programming problem, and solve it by a high-performance integer programming software such as GLPK, SCIP, or CPLEX. It is shown that the proposed method can be easily implemented without making complicated programs. It is also confirmed by numerical examples that the proposed method can find all solutions of medium-scale systems of piecewise-linear equations in practical computation time.     

对带有盒约束的二次整数规划的一种线性化方法

本文主要讨论了二次整数规划问题的线性化方法.在目标函数为二次函数的情况下,我们讨论了带有二次约束的整数规划问题的线性化方法,并将文献中对二次0-1问题的研究拓展为对带有盒约束的二次整数规划问题的研究.最终将带有盒约束的二次整数规划问题转化为线性混合本文主要讨论了二次整数规划问题的线性化方法.在目标函数为二次函数的情况下,我们讨论了带有二次约束的整数规划问题的线性化方法,并将文献中对二次0-1问题的研究拓展为对带有盒约束的二次整数规划问题的研究.最终将带有盒约束的二次整数规划问题转化为线性混合0-1整数规划问题,然后利用Ilog-cplex或Excel软件中的规划求解工具进行求解,从而解决原二次整数规划.     

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.     

Column enumeration based decomposition techniques for a class of non-convex MINLP problems

We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration approach. The master problem is a partitioning problem whose objective function coefficients are computed via subproblems. These problems can be linear, mixed integer linear, (non-)convex nonlinear, or mixed integer nonlinear. However, the important property of the subproblems is that we can compute their exact global optimum quickly. The proposed technique will be illustrated solving a cutting problem with optimum nonlinear programming subproblems.     

A Reference Direction Algorithm for Solving Multiple Objective Integer Linear Programming Problems

In this paper, we propose a reference direction approach and an interactive algorithm to solve the general multiple objective integer linear programming problem. At each iteration, only one mixed integer linear programming problem is solved to find an (weak) efficient solution. Each intermediate solution is integer. The decision maker has to provide only the reference point at each iteration. No special software is required to implement the proposed algorithm. The algorithm is illustrated with an example.     

ASEAN industrial cooperation: The case of multi-product capacity expansion

The Association of South East Asian Nation (ASEAN) was formed in 1967 to promote economic growth in the region through regional cooperation. As a vivid manifestation of this cooperation, since 1976 various industrial projects have been designated as ASEAN industrial projects. A number of studies have been conducted to examine the feasibility, in a heuristic sense, of these projects as regional projects. In this paper, a mixed integer programming model is derived for the optimal locations and time phasing of a package of industrial projects as ASEAN projects. Two solution approaches are then formulated to provide optimal or close-to-optimal solutions to the model. The performance of these two approaches are then compared against a mixed integer programming code on several real-life versions of the ASEAN industrial cooperation problem. The results indicate that these approaches are extremely efficient in providing optimal solutions to the problem. Since industrial projects last over a long time, this model which allows for dynamic analysis of the ASEAN industrial cooperation problem is a useful extension of the static models developed so far.     

Development of a new approach for deterministic supply chain network design

This paper proposes a mixed integer linear programming model and solution algorithm for solving supply chain network design problems in deterministic, multi-commodity, single-period contexts. The strategic level of supply chain planning and tactical level planning of supply chain are aggregated to propose an integrated model. The model integrates location and capacity choices for suppliers, plants and warehouses selection, product range assignment and production flows. The open-or-close decisions for the facilities are binary decision variables and the production and transportation flow decisions are continuous decision variables. Consequently, this problem is a binary mixed integer linear programming problem. In this paper, a modified version of Benders’ decomposition is proposed to solve the model. The most difficulty associated with the Benders’ decomposition is the solution of master problem, as in many real-life problems the model will be NP-hard and very time consuming. In the proposed procedure, the master problem will be developed using the surrogate constraints. We show that the main constraints of the master problem can be replaced by the strongest surrogate constraint. The generated problem with the strongest surrogate constraint is a valid relaxation of the main problem. Furthermore, a near-optimal initial solution is generated for a reduction in the number of iterations.     

A continuous model for production–distribution system design

The production–distribution system design problem (PDSDP) involves decisions concerning the structure of a firm's supply chain. An overwhelming majority of the literature uses mixed integer programming formulations in representing such facility design decisions. In this paper, we present an alternative modeling framework, which is based on the use of continuous functions to represent spatial distributions of cost and customer demand. The proposed continuous model allows the derivation of a number of insights about the impact of problem parameters on facility design decisions. It is proposed that discrete and continuous modeling approaches complement each other.     

The reformulation of two mixed integer programming problems

Two practical problems are described, each of which can be formulated in more than one way as a mixed integer programming problem. The computational experience with two formulations of each problem is given. It is pointed out how in each case a reformulation results in the associated linear programming problem being more constrained. As a result the reformulated mixed integer problem is easier to solve. The problems are a multi-period blending problem and a mining investment problem.     

Optimizing a multi-stage production/inventory system by DC programming based approaches

This paper deals with optimizing the cost of set up, transportation and inventory of a multi-stage production system in presence of bottleneck. The considered optimization model is a mixed integer nonlinear program. We propose two methods based on DC (Difference of Convex) programming and DCA (DC Algorithm)—an innovative approach in nonconvex programming framework. The mixed integer nonlinear problem is first reformulated as a DC program and then DCA is developed to solve the resulting problem. In order to globally solve the problem, we combine DCA with a Branch and Bound algorithm (BB-DCA). A convex minorant of the objective function is introduced. DCA is used to compute upper bounds while lower bounds are calculated from a convex relaxation problem. The numerical results compared with those of COUENNE (http://www.coin-or.org/download/binary/Couenne/), a solver for mixed integer nonconvex programming, show the rapidity and the ?-globality of DCA in almost cases, as well as the efficiency of the combined DCA-Branch and Bound algorithm. We also propose a simple heuristic algorithm which is proved by experimental results to be better than an existing heuristic in the literature for this problem.