Efficient automated schematic map drawing using multiobjective mixed integer programming

We present an efficient multiobjective mixed binary linear program that automates schematic mapping for network visualization and navigation. Schematic mapping has broad applications in representing transit networks, circuits, disease pathways, project tasks, organograms, and taxonomies. Good schematic maps employ distortion while preserving topology to facilitate access to physical or virtual networks. Automation is critical to saving time and costs, while encouraging adoption. We build upon previous work, particularly that of Nöllenburg and Wolff, improving upon the computational efficiency of their model by relaxing integrality constraints and reducing the number of objectives from three to two. We also employ an efficient augmented ϵ-constraint method to assist in obtaining all Pareto optimal solutions, both supported and unsupported, for a given network. Through the Vienna Underground network and a cancer pathway, along with three numerical examples, we demonstrate the applications of our methods. Finally, we discuss future directions for research in this area.     

A two-slope achievement scalarizing function for interactive multiobjective optimization

The use of achievement (scalarizing) functions in interactive multiobjective optimization methods is very popular, as indicated by the large number of algorithmic and applied scientific papers that use this approach. Key parameters in this approach are the reference point, which expresses desirable objective function values for the decision maker, and weights. The role of the weights can range from purely normalizing to fully preferential parameters that indicate the relative importance given by the decision maker to the achievement of each reference value. Technically, the influence of the weights in the solution generated by the achievement scalarizing function is different, depending on whether the reference point is achievable or not. Besides, from a psychological point of view, decision makers also react in a different way, depending on the achievability of the reference point. For this reason, in this work, we introduce the formulation of a new achievement scalarizing function with two different weight vectors, one for achievable reference points, and the other one for unachievable reference points. The new achievement scalarizing function is designed so that an appropriate weight vector is used in each case, without having to carry out any a priori achievability test. It allows us to reflect the decision maker's preferences in a better way as a part of an interactive solution method, and this can cause a quicker convergence of the method. The computational efficiency of this new formulation is shown in several test examples using different reference points.     

一种求解整数规划与混合整数规划非线性罚函数方法

证明了任何一个变量有界的整数规划问题（IP）和混合整数规划问题（MIP）都可以转化为一个等价的非整数（或连续化）规划问题（NIP），并给出一个用非线性精确罚函数法来求解该等价NIP的方法，从而达到求解IP或MIP的目的，数值实验表明了算法的可行性。该方法可广泛用于各应用领域里IP和MIP的求解，特别是为非线性IP和MIP问题提供了一条通用 的求解途径，对解决许多实际优化问题具有重要意义。     

Stability radius of an efficient solution of a vector problem of integer linear programming in the Gölder metric

A vector (multicriterion) problem of integer linear programming is considered on a finite set of feasible solutions. A metric l_p, 1 ≤ p ≤ ∞, is defined on the parameter space of the problem. A formula of the maximum permissible level of perturbations is obtained for the parameters that preserve the efficiency (Pareto optimality) of a given solution. Necessary and sufficient conditions of two types of stability of the problem are obtained as corollaries. This work has been carried out with financial support from the Belgosuniversity within the framework of the Intercollegiate Program “Fundamental and Applied Investigations” (project No. 492/28). __________ Translated from Kibernetika I Sistemnyi Analiz, No. 4, pp. 175–181, July–August 2006.     

On solutions of fuzzy random multiobjective quadratic programming with applications in portfolio problem

In this paper, a multiobjective quadratic programming problem fuzzy random coefficients matrix in the objectives and constraints and the decision vector are fuzzy variables is considered. First, we show that the efficient solutions fuzzy quadratic multiobjective programming problems series-optimal-solutions of relative scalar fuzzy quadratic programming. Some theorems are to find an optimal solution of the relative scalar quadratic multiobjective programming with fuzzy coefficients, having decision vectors as fuzzy variables. An application fuzzy portfolio optimization problem as a convex quadratic programming approach is discussed and an acceptable solution to such problem is given. At the end, numerical examples are illustrated in the support of the obtained results.     

rs-Sparse principal component analysis: A mixed integer nonlinear programming approach with VNS

Principal component analysis is a popular data analysis dimensionality reduction technique, aiming to project with minimum error for a given dataset into a subspace of smaller number of dimensions.In order to improve interpretability, different variants of the method have been proposed in the literature, in which, besides error minimization, sparsity is sought. In this paper we formulate as a mixed integer nonlinear program the problem of finding a subspace with a sparse basis minimizing the sum of squares of distances between the points and their projections. Contrary to other attempts in the literature, with our model the user can fix the level of sparseness of the resulting basis vectors. Variable neighborhood search is proposed to solve the problem obtained this way.Our numerical experience on test sets shows that our procedure outperforms benchmark methods in the literature, both in terms of sparsity and errors.     

整数规划的量子行为蝙蝠算法

蝙蝠算法是一种新型群体智能算法,传统的蝙蝠算法在解决整数规划问题时容易陷入局部最优并出现早熟收敛现象,为了解决这些弊端,提出了一种基于势阱的具有量子行为的蝙蝠算法。论述了算法的优化原理和实现方式,并通过仿真实验,与粒子群算法和量子行为粒子群算法进行性能对比。实验结果表明,量子行为蝙蝠算法不仅能够有效地解决整数规划问题,而且比其他算法具有更好的性能。     

Interactive multiobjective fuzzy random programming through the level set-based probability model

This paper considers a multiobjective linear programming problem involving fuzzy random variable coefficients. A new fuzzy random programming model is proposed by extending the ideas of level set-based optimality and a stochastic programming model. The original problem involving fuzzy random variables is transformed into a deterministic equivalent problem through the proposed model. An interactive algorithm is provided to obtain a satisficing solution for a decision maker from among a set of newly defined Pareto optimal solutions. It is shown that an optimal solution of the problem to be solved iteratively in the interactive algorithm is analytically obtained by a combination of the bisection method and the simplex method.     

Analysis of integer programming formulations of clustering problems

Five different integer programming formulations of the clustering problem are discussed. Three new heuristic algorithms for solving these problems are presented. Some of the existing algorithms are generalized. The relevance of integer programming and combinatorial theory to cluster analysis is discussed. Many other applicable algorithms are listed.     

Applying software engineering techniques in the development and management of linear and integer programming applications

This work addresses characteristics of software environments for mathematical modeling and proposes a system for developing and managing models of linear and integer programming (IP) problems. The main features of this modeling environment are: version control of models and data; client‐server architecture, which allows the interaction among modelers and decision makers; the use of a database to store information about the models and data scenarios; and the use of remote servers of optimization, which allows the optimization problems to be solved on different machines. The modeling environment proposed in this work was validated using mathematical programming models that exploit different characteristics, such as the treatment of conditions for generating variables and constraints, the use of calculated parameters derived from other parameters, and the use of integer and continuous variables in mixed IP models among others. This validation showed that the proposed environment is able to treat models found in various application areas of operations research and to solve problems with tens of thousands of variables and constraints.     

A variable-grouping based genetic algorithm for large-scale integer programming

To effectively reduce the dimensionality of search space, this paper proposes a variable-grouping based genetic algorithm (VGGA) for large-scale integer programming problems (IPs). The VGGA first groups IP’s decision variables based on the optimal solution to the IP’s continuous relaxation problem, and then applies a standard genetic algorithm (GA) to the subproblem for each group of variables. We compare the VGGA with the standard GA and GAs based on even variable-grouping by applying them to solve randomly generated convex quadratic knapsack problems and integer knapsack problems. Numerical results suggest that the VGGA is superior to the standard GA and GAs based on even variable-grouping both on computation time and solution quality.     

Methods of constructing suboptimal solutions of integer programming problems and successive improvement of these solutions

Two-stage methods of constructing an improved suboptimal solution of problems of integer linear programs with nonnegative coefficients are developed. A solution is constructed on the first stage on the basis of newly introduced criteria, and the indices of the intervals of the variables determined, where the coordinates of the optimal solution may differ from the suboptimal solutions already constructed. On the second stage, new solutions are constructed by varying the values of the variations only within these intervals and the best of these new solutions are selected. Computational experiments for high-dimension problems confirm the high degree of efficiency of the newly developed methods.     

Alternative mixed integer linear programming models for identifying the most efficient decision making unit in data envelopment analysis

A mixed integer linear model for selecting the best decision making unit (DMU) in data envelopment analysis (DEA) has recently been proposed by Foroughi [Foroughi, A. A. (2011a). A new mixed integer linear model for selecting the best decision making units in data envelopment analysis. Computers and Industrial Engineering, 60(4), 550–554], which involves many unnecessary constraints and requires specifying an assurance region (AR) for input weights and output weights, respectively. Its selection of the best DMU is easy to be affected by outliers and may sometimes be incorrect. To avoid these drawbacks, this paper proposes three alternative mixed integer linear programming (MILP) models for identifying the most efficient DMU under different returns to scales, which contain only essential constraints and decision variables and are much simpler and more succinct than Foroughi’s. The proposed alternative MILP models can make full use of input and output information without the need of specifying any assurance regions for input and output weights to avoid zero weights, can make correct selections without being affected by outliers, and are of significant importance to the decision makers whose concerns are not DMU ranking, but the correct selection of the most efficient DMU. The potential applications of the proposed alternative MILP models and their effectiveness are illustrated with four numerical examples.     

A genetic algorithm for interval nonlinear integer programming problem

In this paper, we formulate an optimal design of system reliability problem as a nonlinear integer programming problem with interval coefficients, transform it into a single objective nonlinear integer programming problem without interval coefficients, and solve it directly with keeping nonlinearity of the objective function by using Genetic Algorithms (GA). Also, we demonstrate the efficiency of this method with incomplete Fault Detecting and Switching (FDS) for allocating redundant units.     

A two-stage stochastic integer programming model for a thermal power system expansion

In this paper the obtaining of an optimum policy in the capacity expansion planning of a particular thermal‐electric power system is proposed. Therefore, a two‐stage stochastic integer programming is formulated. The model includes, through a finite group of scenarios, the existent uncertainty related to the future availability of the thermal plants currently under operation. The resultant model is solved numerically by the application of the L‐shaped method, whose implementation and development were executed using the software AMPL, with CPLEX as a solver. The results reached are shown, which validate the use of the methodology adopted in this work.     

Binary integer programming formulations for scheduling in market-driven foundries

This paper describes the development and solution of binary integer formulations for production scheduling problems in market-driven foundries. This industrial sector is comprised of small and mid-sized companies with little or no automation, working with diversified production, involving several different metal alloy specifications in small tailor-made product lots. The characteristics and constraints involved in a typical production environment at these industries challenge the formulation of mathematical programming models that can be computationally solved when considering real applications. However, despite the interest on the part of these industries in counting on effective methods for production scheduling, there are few studies available on the subject. The computational tests prove the robustness and feasibility of proposed models in situations analogous to those found in production scheduling at the analyzed industrial sector.     

Gamma deployment problem in grids: hardness and new integer linear programming formulation

Vehicular networks are mobile networks designed for the domain of vehicles and pedestrians. These networks are an essential component of intelligent transportation systems and have the potential to ease traffic management, lower accident rates, and offer other solutions to smart cities. One of the most challenging aspects in the design of a vehicular network is the distribution of its infrastructure units, which are called roadside units (RSUs). In this work, we tackle the gamma deployment problem that consists of deploying the minimum number of RSUs in a vehicular network in accordance with a quality of service metric called gamma deployment. This metric defines a vehicle as covered if it connects to some RSUs at least once in a given time interval during its whole trip. Then, the metric parameterizes the minimum percentage of covered vehicles necessary to make a deployment acceptable or feasible. In this paper, we prove that the decision version of the gamma deployment problem in grids is NP‐complete. Moreover, we correct the multiflow integer linear programming formulation present in the literature and introduce a new formulation based on set covering that is at least as strong as the multiflow formulation. In experiments with a commercial solver, the set covering formulation widely outperforms the multiflow formulation with respect to running time and linear programming relaxation gap.     

Target setting with minimum improving costs in data envelopment analysis: A mixed integer linear programming approach

This study addresses a problem called cost‐minimizing target setting in data envelopment analysis (DEA) methodology. The problem is how to make an inefficient decision‐making unit efficient by allocating to it as few organizational resources as possible, assuming that the marginal costs of reducing inputs or increasing outputs are known and available, which is different from previous furthest and closest DEA targets setting methods. In this study, an existed cost minimizing target setting heuristics approach based on input‐oriented model is examined to show that there exist some limitations. This study develops a simple mixed integer linear programming to determine the desired targets on the strongly efficient frontier based on non‐oriented DEA model considering the situation in the presence of known marginal costs of reducing inputs and increasing outputs simultaneously. Some experiments with the simulated datasets are conducted, and results show that the proposed model can obtain more accurate projections with lower costs compared with those from furthest and closest target setting approaches. Besides, the proposed model can be realistic and efficient in solving cost‐minimizing target setting problem.     

OOESAlgorithm.jl: a julia package for optimizing a linear function over the set of efficient solutions for biobjective mixed integer linear programming

We present OOESAlgorithm.jl , a package for optimizing a linear function over the efficient set of biobjective mixed integer linear programs. The proposed package extends our recent study (see Sierra‐Altamiranda and Charkhgard [INFORMS Journal on Computing, https://doi.org/10.1287/ijoc.2018.0851]) by adding two main features: (a) in addition to CPLEX, the package allows employing any single‐objective solver supported by MathProgBase.jl , for example, GLPK, CPLEX, and SCIP; (b) the package supports execution on multiple processors and is compatible with the JuMP modeling language. An extensive computational study shows the efficacy of the package and its features.     

A hybrid metaheuristic for multiobjective unconstrained binary quadratic programming

The conventional unconstrained binary quadratic programming (UBQP) problem is known to be a unified modeling and solution framework for many combinatorial optimization problems. This paper extends the single-objective UBQP to the multiobjective case (mUBQP) where multiple objectives are to be optimized simultaneously. We propose a hybrid metaheuristic which combines an elitist evolutionary multiobjective optimization algorithm and a state-of-the-art single-objective tabu search procedure by using an achievement scalarizing function. Finally, we define a formal model to generate mUBQP instances and validate the performance of the proposed approach in obtaining competitive results on large-size mUBQP instances with two and three objectives.