A simple augmented ∊-constraint method for multi-objective mathematical integer programming problems

A simple augmented ?-constraint (SAUGMECON) method is put forward to generate all non-dominated solutions of multi-objective integer programming (MOIP) problems. The SAUGMECON method is a variant of the augmented ?-constraint (AUGMECON) method proposed in 2009 and improved in 2013 by Mavrotas et al. However, with the SAUGMECON method, all non-dominated solutions can be found much more efficiently thanks to our innovations to algorithm acceleration. These innovative acceleration mechanisms include: (1) an extension to the acceleration algorithm with early exit and (2) an addition of an acceleration algorithm with bouncing steps. The same numerical example in Lokman and Köksalan (2012) is used to illustrate workings of the method. Then comparisons of computational performance among the method proposed by  and , the method developed by Lokman and Köksalan (2012) and the SAUGMECON method are made by solving randomly generated general MOIP problem instances as well as special MOIP problem instances such as the MOKP and MOSP problem instances presented in Table 4 in Lokman and Köksalan (2012). The experimental results show that the SAUGMECON method performs the best among these methods. More importantly, the advantage of the SAUGMECON method over the method proposed by Lokman and Köksalan (2012) turns out to be increasingly more prominent as the number of objectives increases.     

Optimising a nonlinear utility function in multi-objective integer programming

In this paper we develop an algorithm to optimise a nonlinear utility function of multiple objectives over the integer efficient set. Our approach is based on identifying and updating bounds on the individual objectives as well as the optimal utility value. This is done using already known solutions, linear programming relaxations, utility function inversion, and integer programming. We develop a general optimisation algorithm for use with k objectives, and we illustrate our approach using a tri-objective integer programming problem.     

Interactive bicriterion decision support for a large scale industrial scheduling system

In this paper we develop an interactive decision analysis approach to treat a large scale bicriterion integer programming problem, addressing a real world assembly line scheduling problem of a manufacturing company. This company receives periodically a set of orders for the production of specific items (jobs) through a number of specialised production (assembly) lines. The paper presents a non compensatory approach based on an interactive implementation of the ε-constraint method that enables the decision maker to achieve a satisfactory goal for each objective separately. In fact, the method generates and evaluates a large number of non dominated solutions that constitute a representative sample of the criteria ranges. The experience with a specific numerical example shows the efficiency and usefulness of the proposed model in solving large scale bicriterion industrial integer programming problems, highlighting at the same time the modelling limitations.     

Integer Programming Duality in Multiple Objective Programming

The weighted sums approach for linear and convex multiple criteria optimization is well studied. The weights determine a linear function of the criteria approximating a decision makers overall utility. Any efficient solution may be found in this way. This is not the case for multiple criteria integer programming. However, in this case one may apply the more general e-constraint approach, resulting in particular single-criteria integer programming problems to generate efficient solutions. We show how this approach implies a more general, composite utility function of the criteria yielding a unified treatment of multiple criteria optimization with and without integrality constraints. Moreover, any efficient solution can be found using appropriate composite functions. The functions may be generated by the classical solution methods such as cutting plane and branch and bound algorithms.     

A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems

Most real-life decision-making activities require more than one objective to be considered. Therefore, several studies have been presented in the literature that use multiple objectives in decision models. In a mathematical programming context, the majority of these studies deal with two objective functions known as bicriteria optimization, while few of them consider more than two objective functions. In this study, a new algorithm is proposed to generate all nondominated solutions for multiobjective discrete optimization problems with any number of objective functions. In this algorithm, the search is managed over (p − 1)-dimensional rectangles where p represents the number of objectives in the problem and for each rectangle two-stage optimization problems are solved. The algorithm is motivated by the well-known ε-constraint scalarization and its contribution lies in the way rectangles are defined and tracked. The algorithm is compared with former studies on multiobjective knapsack and multiobjective assignment problem instances. The method is highly competitive in terms of solution time and the number of optimization models solved.     

On the exactness of the ε-constraint method for biobjective nonlinear integer programming

The ε-constraint method is a well-known scalarization technique used for multiobjective optimization. We explore how to properly define the step size parameter of the method in order to guarantee its exactness when dealing with biobjective nonlinear integer problems. Under specific assumptions, we prove that the number of subproblems that the method needs to address to detect the complete Pareto front is finite. We report numerical results on portfolio optimization instances built on real-world data and show a comparison with an existing criterion space algorithm.     

A multi-objective approach to simultaneous determination of spare part numbers and preventive replacement times

Different models have been proposed in the field of preventive maintenance planning for finding optimal age replacement policies. While previous studies have focused mainly on classical cost objectives, this paper presents a novel multi-objective model for preventive replacement of a part over a planning horizon. The proposed model considers different objectives and practical issues, such as corrective replacement and its consequences, residual lifetime objective, and kind of productivity index. Also, the model determines number of spare parts, required for replacement with the defected part, to be provided at the beginning of the planning horizon. The multi-objective model is applicable for machines or equipments which are repaired through replacing their defected part with new spare part.For solving the multi-objective model, regarding to ability of ε-constraint method to generate different pareto-optimal solutions, a procedure is developed based on this method. The procedure shows how the ε-constraint method can be used for finding preferred solution in situations where there is no access to decision maker. The model and solution procedure are illustrated by a numerical example.     

Approximation algorithms for the m-dimensional 0–1 knapsack problem: Worst-case and probabilistic analyses

We describe a polynomial approximation scheme for an m-constraint 0–1 integer programming problem (m fixed) based on the use of the dual simplex algorithm for linear programming.We also analyse the asymptotic properties of a particular random model.     

A multi-objective facility location model for closed-loop supply chain network under uncertain demand and return

A closed-loop supply chain (CLSC) network consists of both forward and reverse supply chains. In this paper, a CLSC network is investigated which includes multiple plants, collection centres, demand markets, and products. To this aim, a mixed-integer linear programming model is proposed that minimizes the total cost. Besides, two test problems are examined. The model is extended to consider environmental factors by weighed sums and ε-constraint methods. In addition, we investigate the impact of demand and return uncertainties on the network configuration by stochastic programming (scenario-based). Computational results show that the model can handle demand and return uncertainties, simultaneously.     

A discussion of scalarization techniques for multiple objective integer programming

In this paper we consider solution methods for multiobjective integer programming (MOIP) problems based on scalarization. We define the MOIP, discuss some common scalarizations, and provide a general formulation that encompasses most scalarizations that have been applied in the MOIP context as special cases. We show that these methods suffer some drawbacks by either only being able to find supported efficient solutions or introducing constraints that can make the computational effort to solve the scalarization prohibitive. We show that Lagrangian duality applied to the general scalarization does not remedy the situation. We also introduce a new scalarization technique, the method of elastic constraints, which is shown to be able to find all efficient solutions and overcome the computational burden of the scalarizations that use constraints on objective values. Finally, we present some results from an application in airline crew scheduling as evidence. This research is partially supported by University of Auckland grant 3602178/9275 and by the Deutsche Forschungsgemeinschaft grant Ka 477/27-1.     

Portfolio construction on the Athens Stock Exchange: a multiobjective optimization approach

In this research article, our purpose is to propose a single-period multiobjective mixed-integer programming model for equity portfolio construction, in order to generate the Pareto optimal portfolios, using a variant of the well-known ε-constraint method. The decision maker's investment policy, i.e. constraints regarding the portfolio structure, is strongly taken into account. An illustrative application in the Athens Stock Exchange market is also presented.     

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.     

A review of interactive methods for multiobjective integer and mixed-integer programming

This paper makes a review of interactive methods devoted to multiobjective integer and mixed-integer programming (MOIP/MOMIP) problems. The basic concepts concerning the characterization of the non-dominated solution set are first introduced, followed by a remark about non-interactive methods vs. interactive methods. Then, we focus on interactive MOIP/MOMIP methods, including their characterization according to the type of preference information required from the decision maker, the computing process used to determine non-dominated solutions and the interactive protocol used to communicate with the decision maker. We try to draw out some contrasts and similarities of the different types of methods.     

An extended assignment problem considering multiple inputs and outputs

The existing assignment problems for assigning n jobs to n individuals are limited to the considerations of cost or profit incurred by each possible assignment. However, in real applications, various inputs and outputs are usually concerned in an assignment problem, such as a general decision-making problem. This paper develops a procedure for resolving assignment problems with multiple incommensurate inputs and outputs for each possible assignment. The concept of the relative efficiency in using various resources, instead of cost or profit, is adopted for each possible assignment of the problem. Data envelopment analysis (DEA) is employed in this paper to measure the efficiency of one assignment relative to that of the others according to a set of decision-making units. A composite efficiency index, consisting of two kinds of relative efficiencies under different comparison bases, is defined to serve as the performance measurement of each possible assignment in the problem formulation. A mathematical programming model for the extended assignment problem is proposed, which is then expressed as a classical integer linear programming model to determine the assignments with the maximum efficiency. A numerical example is used to demonstrate the approach.     

On the stability of some integer programming algorithms

In the present paper we develop our approach for studying the stability of integer programming problems. We prove that the L-class enumeration method is stable on integer linear programming problems in the case of bounded relaxation sets [9]. The stability of some cutting plane algorithms is discussed.     

Robust optimization for interactive multiobjective programming with imprecise information applied to R&D project portfolio selection

A multiobjective binary integer programming model for R&D project portfolio selection with competing objectives is developed when problem coefficients in both objective functions and constraints are uncertain. Robust optimization is used in dealing with uncertainty while an interactive procedure is used in making tradeoffs among the multiple objectives. Robust nondominated solutions are generated by solving the linearized counterpart of the robust augmented weighted Tchebycheff programs. A decision maker’s most preferred solution is identified in the interactive robust weighted Tchebycheff procedure by progressively eliciting and incorporating the decision maker’s preference information into the solution process. An example is presented to illustrate the solution approach and performance. The developed approach can also be applied to general multiobjective mixed integer programming problems.     

Mathematical programming approach to the Petri nets reachability problem

This paper focuses on the resolution of the reachability problem in Petri nets, using the mathematical programming paradigm. The proposed approach is based on an implicit traversal of the Petri net reachability graph. This is done by constructing a unique sequence of Steps that represents exactly the total behaviour of the net. We propose several formulations based on integer and/or binary linear programming, and the corresponding sets of adjustments to the particular class of problem considered. Our models are validated on a set of benchmarks and compared with standard approaches from IA and Petri nets community.     

pth Power Lagrangian Method for Integer Programming

When does there exist an optimal generating Lagrangian multiplier vector (that generates an optimal solution of an integer programming problem in a Lagrangian relaxation formulation), and in cases of nonexistence, can we produce the existence in some other equivalent representation space? Under what conditions does there exist an optimal primal-dual pair in integer programming? This paper considers both questions. A theoretical characterization of the perturbation function in integer programming yields a new insight on the existence of an optimal generating Lagrangian multiplier vector, the existence of an optimal primal-dual pair, and the duality gap. The proposed pth power Lagrangian method convexifies the perturbation function and guarantees the existence of an optimal generating Lagrangian multiplier vector. A condition for the existence of an optimal primal-dual pair is given for the Lagrangian relaxation method to be successful in identifying an optimal solution of the primal problem via the maximization of the Lagrangian dual. The existence of an optimal primal-dual pair is assured for cases with a single Lagrangian constraint, while adopting the pth power Lagrangian method. This paper then shows that an integer programming problem with multiple constraints can be always converted into an equivalent form with a single surrogate constraint. Therefore, success of a dual search is guaranteed for a general class of finite integer programming problems with a prominent feature of a one-dimensional dual search.     

Optimizing fuzzy p-hub center problem with generalized value-at-risk criterion

In this study, we reduce the uncertainty embedded in secondary possibility distribution of a type-2 fuzzy variable by fuzzy integral, and apply the proposed reduction method to p-hub center problem, which is a nonlinear optimization problem due to the existence of integer decision variables. In order to optimize p-hub center problem, this paper develops a robust optimization method to describe travel times by employing parametric possibility distributions. We first derive the parametric possibility distributions of reduced fuzzy variables. After that, we apply the reduction methods to p-hub center problem and develop a new generalized value-at-risk (VaR) p-hub center problem, in which the travel times are characterized by parametric possibility distributions. Under mild assumptions, we turn the original fuzzy p-hub center problem into its equivalent parametric mixed-integer programming problems. So, we can solve the equivalent parametric mixed-integer programming problems by general-purpose optimization software. Finally, some numerical experiments are performed to demonstrate the new modeling idea and the efficiency of the proposed solution methods.     

An interactive dynamic approach based on hybrid swarm optimization for solving multiobjective programming problem with fuzzy parameters

Real engineering design problems are generally characterized by the presence of many often conflicting and incommensurable objectives. Naturally, these objectives involve many parameters whose possible values may be assigned by the experts. The aim of this paper is to introduce a hybrid approach combining three optimization techniques, dynamic programming (DP), genetic algorithms and particle swarm optimization (PSO). Our approach integrates the merits of both DP and artificial optimization techniques and it has two characteristic features. Firstly, the proposed algorithm converts fuzzy multiobjective optimization problem to a sequence of a crisp nonlinear programming problems. Secondly, the proposed algorithm uses H-SOA for solving nonlinear programming problem. In which, any complex problem under certain structure can be solved and there is no need for the existence of some properties rather than traditional methods that need some features of the problem such as differentiability and continuity. Finally, with different degree of α we get different α-Pareto optimal solution of the problem. A numerical example is given to illustrate the results developed in this paper.