We are very pleased to introduce this special issue on multiobjective evolutionary optimization for machine learning (MOML). Optimization is at the heart of many machine-learning techniques. However, there is still room to exploit optimization in machine learning. Every machine-learning technique has hyperparameters that can be tuned using evolutionary computation and optimization, considering normally multiple criteria, such as bias, variance, complexity, and fairness in model selection. Multiobjective evolutionary optimization can help meet these criteria for optimizing machine-learning models. Some of the existing approaches address these multiple criteria by transforming the problem into a single-objective optimization problem. However, multiobjective optimization models are able to outperform single-objective ones in contributing to multiple intended objectives (criteria). In recent years, evolutionary computation has been shown to be the premier method for solving multiobjective optimization problems (MOPs), producing both optimal and diverse solutions beyond the capabilities of other heuristics. This is particularly true for very large solution spaces, which is the case in real-world machine-learning problems with many features.

Sharing data and computation among concurrent queries has been an active research topic in database systems. While work in this area developed algorithms and systems that are shown to be effective, there is a lack of logical foundation for query processing and optimization. In this paper, we present PsiDB, a system model for processing a large number of database queries in a batch. The key idea is to generate a single query expression that returns a global relation containing all the data needed for individual queries. For that, we propose the use of a type of relational operators called ψ-operators in combining the individual queries into the global expression. We tackle the algebraic optimization problem in PsiDB by developing equivalence rules to transform concurrent queries with the purpose of revealing query optimization opportunities. Centering around the ψ-operator, our rules not only cover many optimization techniques adopted in existing batch processing systems, but also revealed new optimization opportunities. Experiments conducted on an early prototype of PsiDB show a performance improvement of up to 36X over a mainstream commercial DBMS.

This study introduces a branch-and-bound algorithm to solve mixed-integer bilinear maximum multiplicative programs (MIBL-MMPs). This class of optimization problems arises in many applications, such as finding a Nash bargaining solution (Nash social welfare optimization), capacity allocation markets, reliability optimization, etc. The proposed algorithm applies multiobjective optimization principles to solve MIBL-MMPs exploiting a special characteristic in these problems. That is, taking each multiplicative term in the objective function as a dummy objective function, the projection of an optimal solution of MIBL-MMPs is a nondominated point in the space of dummy objectives. Moreover, several enhancements are applied and adjusted to tighten the bounds and improve the performance of the algorithm. The performance of the algorithm is investigated by 400 randomly generated sample instances of MIBL-MMPs. The obtained result is compared against the outputs of the mixed-integer second order cone programming (SOCP) solver in CPLEX and a state-of-the-art algorithm in the literature for this problem. Our analysis on this comparison shows that the proposed algorithm outperforms the fastest existing method, that is, the SOCP solver, by a factor of 6.54 on average. Summary of Contribution: The scope of this paper is defined over a class of mixed-integer programs, the so-called mixed-integer bilinear maximum multiplicative programs (MIBL-MMPs). The importance of MIBL-MMPs is highlighted by the fact that they are encountered in applications, such as Nash bargaining, capacity allocation markets, reliability optimization, etc. The mission of the paper is to introduce a novel and effective criterion space branch-and-cut algorithm to solve MIBL-MMPs by solving a finite number of single-objective mixed-integer linear programs. Starting with an initial set of primal and dual bounds, our proposed approach explores the efficient set of the multiobjective problem counterpart of the MIBL-MMP through a criterion space–based branch-and-cut paradigm and iteratively improves the bounds using a branch-and-bound scheme. The bounds are obtained using novel operations developed based on Chebyshev distance and piecewise McCormick envelopes. An extensive computational study demonstrates the efficacy of the proposed algorithm.

While work in Techniques based on sharing data and computation among queries developed algorithms and systems that are shown to be effective, there is a lack of logical foundation for query processing and optimization. In this paper, we present PsiDB, a system model for processing a large number of database queries in a batch. The key idea is to generate a single query expression that returns a global relation containing all the data needed for individual queries. For that, we propose the use of a type of relational operators called ψ-operators in combining the individual queries into the global expression. We tackle the algebraic optimization problem in PsiDB by developing equivalence rules to transform concurrent queries with the purpose of revealing query optimization opportunities. Experiments conducted on an early prototype of PsiDB show a major performance improvement over a mainstream commercial DBMS.

We present a new heuristic algorithm to approximately generate the nondominated frontier of bi-objective pure integer linear programs. The proposed algorithm employs a customized version of several existing algorithms in the literature of both single-objective and bi-objective optimization. Our proposed method has two desirable characteristics: (1) there is no parameter to be tuned by users other than the time limit; (2) it can naturally exploit parallelism. An extensive computational study shows the efficacy of the proposed method on some existing standard test instances in which the true frontier is known, and also some large randomly generated instances. We show that even a basic version of our algorithm can significantly outperform the Nondominated Sorting Genetic Algorithm II (Deb et al. 2002), and the sophisticated version of our algorithm is competitive with Multidirectional Local Search (Tricoire 2012). We also show the value of parallelization on the proposed approach.

We present the first (criterion space search) algorithm for optimizing a linear function over the set of efficient solutions of biobjective mixed integer linear programs. The proposed algorithm is developed based on the triangle splitting method [Boland N, Charkhgard H, Savelsbergh M (2015) A criterion space search algorithm for biobjective mixed integer programming: The triangle splitting method. INFORMS J. Comput. 27(4):597–618.], which can find a full representation of the nondominated frontier of any biobjective mixed integer linear program. The proposed algorithm is easy to implement and converges quickly to an optimal solution. An extensive computational study shows the efficacy of the algorithm. We numerically show that the proposed algorithm can be used to quickly generate a provably high-quality approximate solution because it maintains a lower and an upper bound on the optimal value of the linear function at any point in time.

We present the first criterion space search algorithm, the triangle splitting method, for finding all nondominated points of a biobjective mixed integer program. The algorithm is relatively easy to implement and converges quickly to the complete set of nondominated points. The algorithm maintains, at any point in time, a diverse set of nondominated points, and is thus ideally suited for fast approximation of the nondominated frontier. An extensive computational study demonstrates the efficacy of the triangle splitting method. Data, as supplemental material, are available at http://dx.doi.org/10.1287/ijoc.2015.0646 .

We present a new criterion space search algorithm, the balanced box method, for finding all nondominated points of a biobjective integer program. The method extends the box algorithm, is easy to implement, and converges quickly to the complete set of nondominated points. Because the method maintains, at any point in time, a diverse set of nondominated points, it is ideally suited for fast approximation of the efficient frontier. In addition, we present several enhancements of the well-known ε-constraint, augmented weighted Tchebycheff, and perpendicular search methods. An extensive computational study, using instances from different classes of combinatorial optimization problems, demonstrates the efficacy of the balanced box method.