A test instance generator for multiobjective mixed-integer optimization
Abstract
EconStor is a publication server for scholarly economic literature, provided as a non-commercial public service by the ZBW.
Full text
Eichfelder, Gabriele; Gerlach, Tobias; Warnow, Leo Article — Published Version A test instance generator for multiobjective mixed-integer optimization Mathematical Methods of Operations Research Provided in Cooperation with: Springer Nature Suggested Citation: Eichfelder, Gabriele; Gerlach, Tobias; Warnow, Leo (2023) : A test instance generator for multiobjective mixed-integer optimization, Mathematical Methods of Operations Research, ISSN 1432-5217, Springer, Berlin, Heidelberg, Vol. 100, Iss. 1, pp. 385-410, https://doi.org/10.1007/s00186-023-00826-z This Version is available at: https://hdl.handle.net/10419/309517 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by/4.0/
Mathematical Methods of Operations Research (2024) 100:385–410 https://doi.org/10.1007/s00186-023-00826-z ORIGINAL ARTICLE A test instance generator for multiobjective mixed-integer optimization Gabriele Eichfelder1 ·Tobias Gerlach1 ·Leo Warnow1 Received: 22 February 2023 / Revised: 21 June 2023 / Accepted: 28 June 2023 / Published online: 19 July 2023 © The Author(s) 2023 Abstract Application problems can often not be solved adequately by numerical algorithms as several difficulties might arise at the same time. When developing and improving algorithms which hopefully allow to handle those difficulties in the future, good test instances are required. These can then be used to detect the strengths and weaknesses of different algorithmic approaches. In this paper we present a generator for test instances to evaluate solvers for multiobjective mixed-integer linear and nonlinear optimization problems. Based on test instances for purely continuous and purely integer problems with known efficient solutions and known nondominated points, suitable multiobjective mixed-integer test instances can be generated. The special structure allows to construct instances scalable in the number of variables and objective functions. Moreover, it allows to control the resulting efficient and nondominated sets as well as the number of efficient integer assignments. Keywords Multiobjective optimization ·Mixed-integer optimization ·Test instances ·Nonconvex optimization Mathematics Subject Classification 90C11 ·90C26 ·90C29 ·90C30 BGabriele Eichfelder [email protected] Tobias Gerlach [email protected] Leo Warnow leo.warno[email protected] 1Institute of Mathematics, Technische Universität Ilmenau, Po 10 05 65, 98684 Ilmenau, Germany 123
386 G. Eichfelder et al. 1 Introduction Optimization problems that arise within practical applications often turn out to be very challenging for solution algorithms from a numerical point of view. Thereby, the challenges can be caused, for instance, by a high number of variables or objective functions as well as certain properties of the objective and constraint functions including nonlinearity or nonconvexity. Hence, there is a need to evaluate the strengths and weaknesses of different solution algorithms. This is important to decide which of them might perform best for a specific type of optimization problems or how the algorithm can be improved to do so in the future. This is typically done by evaluating the performance of an algorithm on a set of certain test instances that cover the above mentioned challenges. In this paper we present a generator for such test instances that yields multiobjective mixed-integer optimization problems. This means that multiple objective functions have to be optimized at the same time and that some of the variables are continuous while others are only allowed to take integer values. When it comes to multiobjective mixed-integer optimization, most of the literature focuses on multiobjective mixed-integer linear optimization problems. This includes, for instance, the Triangle Splitting Method from Boland et al. (2015) and the Boxed Line Method from Perini et al. (2019) for the biobjective setting, as well as the GoNDEF algorithm from Rasmi and Türkay (2019) for an arbitrary number of objective functions. For a comprehensive overview of algorithmic approaches to solve multiobjective mixed-integer linear optimization problems we refer to Halffmann et al. (2022). To the best of our knowledge, the first deterministic solution method for multiobjective mixed-integer convex optimization problems is given in De Santis et al. (2020). Only recently, also a solution approach for multiobjective mixed-integer nonconvex optimization problems has been presented in Eichfelder et al. (2022). Further solution methods can be found for multiobjective mixed-integer convex optimization problems in Eichfelder and Warnow (2021a,2023), for biobjective mixed-integer convex optimization problems in Cabrera-Guerrero et al. (2022), Diessel (2022), for biobjective mixed-integer quadratic optimization problems in Jayasekara Merenchige and Wiecek (2022), and for multiobjective mixed-integer nonconvex optimization problems in Link and Volkwein (2022), respectively. While a relatively large number of (even scalable) test instances exists for multiobjective continuous optimization (e.g. Brockhoff et al. 2022; Cheng et al. 2017; Deb et al. 2005; Fonseca and Fleming 1995; Fonseca et al. 2020; Huband et al. 2006; Schaffer 1985), so far only a limited number of test instances for multiobjective mixedinteger optimization problems was introduced and used for numerical testing. Such instances can be found for the convex case in De Santis et al. (2020), Eichfelder and Warnow (2021a,b,2023), Jayasekara Merenchige and Wiecek (2022), Papalexandri and Dimkou (1998) and for the nonconvex case in Cabrera-Guerrero et al. (2022), Eichfelder et al. (2022); Eichfelder and Warnow (2023), Link and Volkwein (2022), Mela et al. (2007), respectively. Note that these test instances consist of 16 biobjective and four triobjective mixed-integer problems. Only one test problem is scalable in the number of objective functions (by using the identity for the continuous variables). We refer to Eichfelder et al. (2023) for a more in-depth discussion and classification of these existing test instances. 123
A test instance generator for MOMIPs 387 However, for a systematic evaluation of the strengths and weaknesses of solution algorithms for multiobjective mixed-integer optimization problems more test instances are needed. For instance, there is a demand for test instances that allow to investigate the influence of the number of continuous and integer variables on the performance of the solver, i.e., test instances scalable in the number of variables. This property is especially useful to evaluate the performance of decision space based solution approaches and to compare them with criterion space based solution approaches. Typically, one would expect that decision space based approaches are more influenced by the size of the decision space than criterion space based approaches. In this regard it should be noted that only six of the above mentioned test instances from the literature are scalable in the number of integer variables, and only four of them are additionally scalable in the number of continuous variables. Further important properties of test instances to evaluate the performance of different solution algorithms are for instance the number of so called feasible integer assignments and of efficient integer assignments. These are fixings of the integer variables in such a way that there also exists a fixing of the continuous variables which together yield a feasible or efficient solution of the optimization problem. Especially for algorithms that decompose the mixed-integer optimization problem into a family of purely continuous optimization problems obtained for certain fixings of the integer variables (see also the forthcoming Remark 2.1) these are of high importance. Taking all of this into account, the new generator for test instances allows to vary the numbers of variables as well as the number of objective functions depending on its input. The proposed method generates test instances that possess a separable structure. This is also the case for several of the known test instances for multiobjective mixedinteger optimization problems from the literature. Thereby, separable means that these test instances can be decomposed into a multiobjective continuous subproblem and into a multiobjective integer subproblem. We will show that under certain assumptions this provides us with full control over the resulting efficient and nondominated sets of the test instances, as well as their number of efficient integer assignments. This allows to verify the correctness of the results from a solution algorithm for multiobjective mixedinteger optimization problems and to evaluate the quality of its output. Especially for the evaluation of nondeterministic or heuristic approaches this is an important feature. The remaining paper is structured as follows. In Sect. 2we briefly present the notations and definitions that are used within this paper. We then analyze separable multiobjective mixed-integer optimization problems in Sect. 3. Based on this, in Sect.4, we provide the test instance generator for multiobjective mixed-integer optimization problems. Some (scalable) multiobjective continuous and integer optimization problems as possible inputs for the generator are listed and discussed in Sect. 4.1 and Sect. 4.2, respectively. Finally, we provide an outlook for future research in Sect.5. 2 Notations and definitions For a positive integer p∈Nand real numbers a,b∈Rwith a≤bwe use the notations [p]:={1,...,p},[a,b]:={x∈R|a≤x≤b}, and ]a,b]:={x∈ 123
388 G. Eichfelder et al. R|a<x≤b}. Moreover, the inequalities ≤and <between vectors are understood componentwise, i.e., for x,x∈Rpit holds x≤xor x<xif and only if xi≤x i or xi<x iis fulfilled for all i∈[p], respectively. Based on this we denote for l,u∈Rpwith l≤uby [l,u]:={y∈Rp|l≤y≤u}the box with lower bound land upper bound u. Throughout the paper the addition of functions is defined pointwise, i.e., for two functions g,h:Rn→Rpwe define g+h:Rn→Rpby (g+h)(x):= g(x)+h(x)for all x∈Rn, and the addition of two sets is defined in the Minkowski-sense. For two sets A,Bthe Cartesian product is defined as A×B:= {(a,b)|a∈A,b∈B}. For two vectors x,x∈Rptheir Hadamard product is defined by x◦x:= (x1x 1,...,xpxp). Finally, for a nonempty set ⊆Rpwe denote its cardinality by ||and its convex hull by conv(). In the following, we consider multiobjective mixed-integer optimization problems, i.e., multiobjective optimization problems defined by min xf(x) s.t. g(x)≤0q, x∈X:= XC×XI. (MOMIP) Thereby, let n,m∈N0with n≥1orm≥1 and let fi:Rn+m→R, i∈[p],p≥2, gj:Rn+m→R,j∈[q]be continuous functions, where f=(f1,..., fp):Rn+m→Rp,g=(g1,...,gq):Rn+m→Rq, and 0q:= 0Rq. Moreover, let XC:= [lC,uC]⊆Rnbe a box with lC,uC∈Rn,letXI:= [lI,uI]∩Zm be a finite subset of Zmwith lI,uI∈Zmand let the feasible set S:= {x∈Rn+m| g(x)≤0q,x∈X}of (MOMIP) be nonempty. For the variables x∈Xof (MOMIP), we will write in the following x=(xC,xI) with xC∈XCand xI∈XIto distinguish between the continuous and the integer variables. We call (MOMIP) a multiobjective mixed-integer convex optimization problem if all involved functions fi,i∈[p]and gj,j∈[q]are convex. Otherwise, we call it a multiobjective mixed-integer nonconvex optimization problem. Obviously, for m=0 and for n=0 the special cases of a multiobjective continuous optimization problem (MOP) given by min xf(x) s.t. g(x)≤0q, x∈XC (MOP) and of a multiobjective integer optimization problem (MOIP) given by min xf(x) s.t. g(x)≤0q, x∈XI (MOIP) are included in (MOMIP). 123
A test instance generator for MOMIPs 389 Recall that a feasible point ¯x∈Sis called an efficient solution of (MOMIP) if there exists no x∈Swith f(x)≤f(¯x)and f(x)= f(¯x). Moreover, a point ¯y=f(¯x) with ¯x∈Sis called a nondominated point of (MOMIP)if ¯xis an efficient solution. The set E⊆Sdenotes the set of all efficient solutions (also called the efficient set) and the set N⊆f(S)denotes the set of all nondominated points (also called the nondominated set)of(MOMIP). If for all x∈Sthere exists an ¯x∈Esuch that f(¯x)≤f(x), then the multiobjective optimization problem is said to satisfy the so called domination property. Note that by the continuity of the objective and constraint functions and the box constraints (MOMIP), and thus also the special cases (MOP) and (MOIP), fulfill the domination property and it holds E=∅and N=∅. For the multiobjective mixed-integer optimization problem (MOMIP) we call xI∈ XIafeasible integer assignment if there exists xC∈XCsuch that (xC,xI)is feasible for (MOMIP). Analogously, we call xI∈XIan efficient integer assignment if there exists xC∈XCsuch that (xC,xI)∈E, i.e., (xC,xI)is an efficient solution of (MOMIP). We denote by SIthe set of all feasible integer assignments and by EIthe set of all efficient integer assignments of (MOMIP). Remark 2.1 The absolute number (and the percentage) of efficient integer assignments within the set of feasible integer assignments is an important characteristic of a multiobjective mixed-integer optimization problem. It might also influence the performance of numerical algorithms depending on how they are constructed. Note that this is a significant difference to the singleobjective setting: in singleobjective mixed-integer optimization the optimal value is unique and hence it is enough to find one optimal integer assignment. For p≥2 there are in general infinitely many nondominated points. As a consequence, there can be instances with a large number of efficient integer assignments which lead to different nondominated points. Even all feasible integer assignments can be efficient. Hence, algorithms that decompose (MOMIP) into a family of purely continuous problems may be forced to a full enumeration in that case. 3 Separable multiobjective mixed-integer optimization problems Many of the known test instances for multiobjective mixed-integer (nonlinear) optimization have a common structure, which we will formalize and study in this section. The results form the basis for our approach regarding the test instance generator. A multiobjective mixed-integer optimization problem (MOMIP) which can be formulated by a decomposition min x=(xC,xI)fC(xC)+fI(xI) s.t. gC(xC)≤0qC, gI(xI)≤0qI, x∈X=XC×XI (sMOMIP) 123
390 G. Eichfelder et al. with continuous objective functions fC:Rn→Rp,fI:Rm→Rpwith n,m∈N, and continuous constraint functions gC:Rn→RqC,gI:Rm→RqIis called separable. To the separable multiobjective mixed-integer optimization problem (sMOMIP) we formulate the following two subproblems: the multiobjective continuous subproblem min xC fC(xC) s.t. gC(xC)≤0qC, xC∈XC (sMOMIPC) and the multiobjective integer subproblem min xI fI(xI) s.t. gI(xI)≤0qI, xI∈XI. (sMOMIPI) The efficient solutions and the nondominated points of the subproblems and of the original separable problem are related to what we discuss next. We denote by Ss C/Es C/Ns C and by Ss I/Es I/Ns Ithe feasible set/the set of all efficient solutions/the set of all nondominated points of (sMOMIPC) and of (sMOMIPI), respectively. It is easy to see that for a separable multiobjective mixed-integer optimization problem (sMOMIP) and the corresponding subproblems (sMOMIPC) and (sMOMIPI) it holds S=Ss C×Ss Iand SI=Ss I. Here, Sdenotes the feasible set and SIdenotes the set of all feasible integer assignments of (sMOMIP). Note that under our assumptions it holds Ss C=∅and Ss I=∅, and both subproblems fulfill the domination property. Hence, it holds Es C=∅, Es I=∅,Ns C=∅, and Ns I=∅. We illustrate such a decomposable mixed-integer optimization problem with the following example. Example 3.1 The separable biobjective mixed-integer nonconvex optimization problem given by min x ⎛ ⎜ ⎜ ⎝ 1−exp − n i=1xi−1 √n2+xn+1+xn+2 1−exp − n i=1xi+1 √n2−xn+1−xn+2 ⎞ ⎟ ⎟ ⎠ s.t. x∈X=[−4,4]n×([−1,1]2∩Z2). (3.1) can be decomposed into the (well known) biobjective continuous subproblem min x ⎛ ⎜ ⎜ ⎝ 1−exp − n i=1xi−1 √n2 1−exp − n i=1xi+1 √n2⎞ ⎟ ⎟ ⎠ s.t. x∈XC=[−4,4]n (3.2) 123
A test instance generator for MOMIPs 391 Fig. 1 Nondominated set Nof the separable optimization problem (3.1) and nondominated set Ns Iof the integer subproblem (3.3) from Example 3.1 introduced in Fonseca and Fleming (1995) and into the biobjective integer linear subproblem given by min xx1+x2 −x1−x2 s.t. x∈XI={−1,0,1}2. (3.3) The efficient and nondominated sets of the subproblems are given by Es C=x∈XC|x1=x2=...=xn∈−1 √n,1 √n, Ns C=1−exp(−4(t−1)2), 1−exp(−4t2)|t∈[0,1], Es I=XI={−1,0,1}2, Ns I={(δ, −δ) |δ∈{−2,−1,0,1,2}} = {(−2,2), (−1,1), (0,0), (1,−1), (2,−2)}. For further explanations regarding the corresponding sets E,N, and EIwe refer to Example 4.8 (i). For an illustration of the nondominated sets Ns Iand Nsee Fig.1. With the following lemma we start the examination of the relations between the efficient solutions and the nondominated points regarding the subproblems and the original separable problem. Lemma 3.2 Let Edenote the set of all efficient solutions, Nthe set of all nondominated points, and EIthe set of all efficient integer assignments of (sMOMIP). Then for the corresponding subproblems (sMOMIPC)and (sMOMIPI)it holds: (i) E⊆Es C×Es I. (ii) N⊆Ns C+Ns I. 123
392 G. Eichfelder et al. (iii) EI⊆Es I. Proof The relations (ii)and (iii)follow immediately by (i). For the proof of (i)let ¯x=(¯xC,¯xI)∈E⊆S=Ss C×Ss Iand assume that ¯xC/∈Es C. Then there exists ˆxC∈Ss Csuch that fC(ˆxC)≤fC(¯xC)and fC(ˆxC)= fC(¯xC). Thus we obtain for x=(ˆxC,¯xI)∈Ss C×Ss I=Sthat f(x)=fC(ˆxC)+fI(¯xI)≤fC(¯xC)+fI(¯xI)=f(¯x)and f(x)= f(¯x), which contradicts ¯x∈E. The proof for ¯xI∈Es Iis analogous. Note that equality for (i),(ii)and (iii)from Lemma 3.2 is trivially fulfilled in the scalar-valued setting p=1. In the vector-valued case p≥2 these equalities do, in general, not hold as the following example shows. Example 3.3 We consider the separable biobjective mixed-integer optimization problem min xx1+x2+0.75x3 −x1−x2−0.25x3 s.t. x∈X=[0,1]×([−1,1]×[0,1])∩Z2. (3.4) It can be decomposed into the biobjective continuous subproblem min xx −x s.t. x∈XC=[0,1] (3.5) and the biobjective integer subproblem min xx1+0.75x2 −x1−0.25x2 s.t. x∈XI={−1,0,1}×{0,1}. (3.6) The efficient and nondominated sets of (3.4), (3.5) and (3.6)aregivenby Es C=XC, Es I=XI, E=[0,1]×{(−1,0), (0,0), (1,0)}∪]3 4,1]×(1,1), Ns C=conv{(0,0), (1,−1)}, Ns I=(−1,1), (0,0), (1,−1), −1 4,3 4,3 4,−1 4,7 4,−5 4,and N=conv{(0,0), (1,−1)}+{(−1,1), (0,0), (1,−1)} ∪conv 3 4,−3 4,(1,−1)\3 4,−3 4+7 4,−5 4. 123
A test instance generator for MOMIPs 399 Example 4.2 If we choose in the test instance generator for the multiobjective continuous optimization problem (4.1) the optimization problem min x⎛ ⎝ (1+x3)(x3 1x2 2−10x1−4x2) (1+x3)(x3 1x2 2−10x1+4x2) 3(1+x3)x2 1 ⎞ ⎠ s.t. x∈XC=[1,3.5]×[−2,2]×[0,1] as introduced in Deb et al. (2005), then it holds Es C⊆x∈R3|1≤x1≤3.5,−2≤x3 1x2≤2,−2≤x2≤2,x3=0=: M. By simple calculations we obtain (−47,−47,3)≤idealCand a-idealC≤(2,2,37). Thus every C∈R3with C≥(49,49,34)≥a-idealC−idealCis an upper bound of C. A possibility for the determination of a lower bound Iof Iis to use the finite cardinality of the set XI=[lI,uI]∩Zm. Moreover, to ensure that I>0pand thus I≤Ican be chosen such that I>0pwe can use the following property introduced and examined in De Santis et al. (2022,2020). Definition 4.3 (De Santis et al. 2022, Definition 2.3) Let X⊆Rmand γ>0. A function g:X→Ris called a positive γ-function over X∩Zmif it holds |g(x)− g(x)|≥γfor all x,x∈X∩Zmwith g(x)= g(x). For instance, every quadratic function g:X→Rwith g(x):= xQx +cxfor all x∈Xwith Q∈Zm×m,c∈Zmis a positive γ-function over X∩Zmwith γ=1. For more classes of positive γ-functions and the corresponding values of γwe refer to (De Santis et al. 2020, Section 4.3). If now fI,i,i∈[p]is a positive γi-function over XI=[lI,uI]∩Zm, then we obtain I,i=inf{|yi−ˆyi||y,ˆy∈Ns I,yi=ˆyi} =inf{|fI,i(x)−fI,i(x)||x,x∈Es I,fI,i(x)= fI,i(x)} ≥inf{|fI,i(x)−fI,i(x)||x,x∈XI,fI,i(x)= fI,i(x)} ≥γi>0. Hence, if there exists some γ∈Rpsuch that γi>0 and fI,iis a positive γi-function over XIfor all i∈[p], then every Iwith 0p<I≤γis a lower bound of I. In the following we provide some multiobjective continuous optimization problems and some multiobjective integer optimization problems that can be used as input for the formulated test instance generator. What is more, all of these optimization problems are scalable in the number of decision variables. 123
400 G. Eichfelder et al. 4.1 Scalable multiobjective continuous problems The major advantage of Theorem 3.4 is that we can generate test instances for which the efficient set, the nondominated set, and the set of efficient integer assignments are known as long as the nondominated and the efficient sets of the input problems (4.1) and (4.2) are known. Regarding a listing of suitable inputs for the test instance generator we start with two biobjective continuous optimization problems scalable in the number of variables. This scalability is a useful property in order to evaluate and compare the performance of (especially decision space based) solution algorithms. The following simple convex optimization problem is based on a well known univariate biobjective test instance introduced in Schaffer (1985): min x ⎛ ⎜ ⎜ ⎝ 1 n n i=1 x2 i 1 n n i=1 (xi−2)2 ⎞ ⎟ ⎟ ⎠ s.t. x∈XC=[0,2]n. (4.4) Besides the efficient and nondominated sets also the vector C∈R2is known for this optimization problems. More precisely, we have that E={x∈XC|x1=x2=...=xn}, N=t2,(t−2)2t∈[0,2],and C,i=4 for all i∈[2]. (4.5) Another possible choice for (4.1) is the biobjective continuous nonconvex optimization problem introduced in Fonseca and Fleming (1995): min x ⎛ ⎜ ⎜ ⎝ 1−exp − n i=1xi−1 √n2 1−exp − n i=1xi+1 √n2⎞ ⎟ ⎟ ⎠ s.t. x∈XC=[−4,4]n. (4.6) For the efficient set, the nondominated set, and C∈R2we obtain E=x∈XC x1=x2=...=xn∈−1 √n,1 √n, N=1−exp(−4(t−1)2), 1−exp(−4t2)t∈[0,1],and C,i=1−exp(−4)for all i∈[2]. (4.7) One well-known method to generate other input problems where E,Nand also an overestimator Cof Care known is presented in (Deb et al. 2005, Section 6.4). The 123
A test instance generator for MOMIPs 401 main idea of this approach is to start with a parametric description of the nondominated set (for instance a part of the unit sphere in the forthcoming optimization problem (4.9)) and then to extend this in order to obtain an optimization problem. What is more, all of the multiobjective continuous optimization problems that are generated with that technique are scalable in the number of variables. Besides that, one can also generate problems that are scalable in the number of objective functions. Again, this is a useful property when generating a collection of test instances to evaluate and compare the performance of different (especially criterion space based) solution algorithms. In the following, we present two examples of continuous optimization problems from Deb et al. (2005) that are scalable in both the number n∈Nof (continuous) variables and p∈Nof objective functions. The first one is test problem DTLZ1 given by min xf(x) s.t. g(x)≤0, x∈XC=[0,1]n (4.8) where n>p. The objective functions fi:Rn→R,i∈[p]are defined as f1(x):= 0.5(1−g(x))x1x2···xp−1, fi(x):= 0.5(1−g(x))x1x2···xp−i(1−xp−i+1)for all i∈([p]\{1,p}), fp(x):= 0.5(1−g(x))(1−x1) and g:Rn→Ronly depends on the last n−pvariables, i.e., there exists h:Rn−p→ Rsuch that g(x)=h(xp+1,...,xn)for all x∈[0,1]n. Further, we assume that there exists some x∈[0,1]nsuch that g(x)=0. It then holds for (4.8) that E={x∈[0,1]n|g(x)=0}, N={y∈[0,1]p|y1=0.5},and C,i=0.5 for all i∈[p]. The next optimization problem can be found as (6.7) in Deb et al. (2005) and is given by min xf(x) s.t. g(x)≤0, x∈XC=[0,π/2]n (4.9) where n>p, the objective functions fi:Rn→R,i∈[p]are defined as f1(x):= (1−g(x)) cos(x1)cos(x2)···cos(xp−1), fi(x):= (1−g(x)) cos(x1)cos(x2)···cos(xp−i)sin(xp−i+1)for all i∈([p]\{1,p}), fp(x):= (1−g(x)) sin(x1) 123
402 G. Eichfelder et al. and g:Rn→Ronly depends on the last n−pvariables. Again, we assume that there exists some x∈[0,π/2]nsuch that g(x)=0. Then it holds for (4.9) that E={x∈[0,π/2]n|g(x)=0}, N={y∈[0,1]p|y2=1},and C,i=1 for all i∈[p]. We remark that for the specific choice of g(x):= n i=p+1(xi−π/4)2,x∈[0,π/2]n this leads to the test problem DTLZ2 from Deb et al. (2005). 4.2 Scalable multiobjective integer problems Besides the continuous subproblems we also need suitable integer subproblems. In the following we present two such problems that are not only scalable in the number of variables, but for which we are also able to control the number of efficient solutions and nondominated points. Lemma 4.4 Let J [m]. Then for the scalable biobjective integer linear optimization problem min x ⎛ ⎜ ⎝ i∈J xi+ i∈[m]\J xi i∈J xi− i∈[m]\J xi ⎞ ⎟ ⎠ s.t. x ∈XI=[−1,1]m∩Zm (4.10) it holds: (i) E={x∈XI|xi=−1for all i ∈J}. (ii) |E|=3m−|J|. (iii) N={(−m+δ, m−2|J|−δ) ∈Z2|δ∈{0}∪[2(m−|J|)]}. (iv) |N|=2(m−|J|)+1. (v) I,i=1for all i ∈[2]. Proof Statement (ii)follows by (i), and the statements (iv) and (v) follow by (iii). We start with the proof of (i). Here, for every ¯x∈E⊆XIit obviously holds that ¯xi=−1 for all i∈Jand we obtain E⊆{x∈XI|xi=−1 for all i∈J}. Let now ¯x∈{x∈XI|xi=−1 for all i∈J}and assume that ¯x/∈E. Then by the domination property there exists x∈Ewith ⎛ ⎜ ⎝ i∈J xi+ i∈[m]\J xi i∈J xi− i∈[m]\J xi ⎞ ⎟ ⎠≤⎛ ⎜ ⎝ i∈J¯xi+ i∈[m]\J¯xi i∈J¯xi− i∈[m]\J¯xi ⎞ ⎟ ⎠ 123
A test instance generator for MOMIPs 403 and with strict inequality in one component. By componentwise addition of the inequalities it follows 2 i∈J xi<2 i∈J¯xi. In case J=∅this contradicts x∈E⊆XIand ¯xi=−1 for all i∈J. In case J=∅we obtain 0 <0. Hence, it holds ¯x∈Eand thus also {x∈XI|xi=−1 for all i∈J}⊆ E. For the proof of (iii)let at first ¯y∈N. Then by definition there exists ¯x∈Esuch that f(¯x)=¯y, and by (i)it holds ¯xi=−1 for all i∈J. Moreover, let ¯ J−1:= {i∈ [m]\J|¯xi=−1},¯ J0:= {i∈[m]\J|¯xi=0}and ¯ J1:= {i∈[m]\J|¯xi=1}. Then we obtain that ¯y1=f1(¯x)= i∈J xi+ i∈¯ J−1 xi+ i∈¯ J1 xi =−|J|−|¯ J−1|+|¯ J1| =−|J|−|¯ J−1|−|¯ J0|−|¯ J1|+|¯ J0|+2|¯ J1| =−|J|−(m−|J|)+|¯ J0|+2|¯ J1| =−m+|¯ J0|+2|¯ J1| and similarly ¯y2=m−2|J|−|¯ J0|+2|¯ J1|. Thus, we derive for δ:= | ¯ J0|+2|¯ J1|≥ 0 that δ=|¯ J0|+2|¯ J1| =|¯ J−1|+|¯ J0|+|¯ J1|−|¯ J−1|+|¯ J1| =m−|J|−|¯ J−1|+|¯ J1| ≤m−|J|+|¯ J1| ≤2(m−|J|), and consequently N⊆{(−m+δ, m−2|J|−δ) ∈Z2|δ∈{0}∪[2(m−|J|)]}. Let now δ∈N0with 0 ≤δ≤2(m−|J|)and let ¯y∈R2with ¯y1:= −m+δand ¯y2:= m−2|J|−δ. Further, let ¯ J−1,¯ J1⊆[m]\Jwith ¯ J−1=max{m−|J|−δ, 0}and ¯ J1=max{δ−(m−|J|), 0}. Then at least one of the sets ¯ J−1or ¯ J1is empty (as at least m−|J|−δ≤0or δ−(m−|J|)≤0). Moreover, J∪¯ J−1∪¯ J1≤m. Define ¯x∈XIby ¯xi=−1for all i∈J∪¯ J−1,¯xi=1 for all i∈¯ J1, and ¯xi=0 for all i∈m\(J∪¯ J−1∪¯ J1). Then we obtain ¯x∈Eby (i). Moreover, one can verify that f1(¯x)=−m+δ=¯y1, f2(¯x)=m−2|J|−δ=¯y2, and thus {(−m+δ,m−2|J|−δ) ∈Z2|δ∈ {0}∪[2(m−|J|)]} ⊆ N, which concludes the proof. 123
404 G. Eichfelder et al. The structure of the nondominated set of (4.10) is quite simple, since all nondominated points are located on a line. In particular, all of the nondominated points are so-called supported nondominated points. This means that they can be found by solving a weighted sum scalarization of (4.10). For this reason, we also present a slight modification of this problem, see (4.11), for which only nearly half of the nondominated set consists of supported nondominated points. The proof of Lemma 4.5 is similar to the proof of Lemma 4.4 and thus omitted. Lemma 4.5 Let J [m−1]. Then for the scalable biobjective integer linear optimization problem min x ⎛ ⎜ ⎝ i∈J xi+ i∈[m−1]\J xi+0.75xm i∈J xi− i∈[m−1]\J xi−0.25xm ⎞ ⎟ ⎠ s.t. x ∈XI=([−1,1]m−1×[0,1])∩Zm (4.11) it holds: (i) E={x∈XI|xi=−1for all i ∈J}. (ii) |E|=2·3m−1−|J|. (iii) N=N1∪N2with N1:= {(−(m−1)+δ,m−1−2|J|−δ) ∈Z2|δ∈}, N2:= (−(m−1)+0.75 +δ,m−1−2|J|−0.25 −δ)∈Z2δ∈, := {0}∪[2(m−1−|J|)]. (iv) |N|=4(m−1−|J|)+2. (v) I,i=0.25 for all i ∈[2]. Remark 4.6 Note that for the optimization problems (4.10) in Lemma 4.4 and (4.11) in Lemma 4.5 not only the absolute number of efficient solutions but also their share in relation to the feasible set XIcan be controlled by the choice of the set J. We obtain in both cases |E| |XI|=3−|J|. This equals the percentage of efficient integer assignments within the set of feasible integer assignments if one of these problems is chosen as input for the test instance generator. Further examples for an integer optimization problem (sMOMIPI) can be obtained from (4.10) and (4.11) and basically any other multiobjective integer optimization problem by replacing the decision variables x∈XIby functions ˜x:Rk→Rm,k∈N such that for some box ˜ X⊆Rkit holds that ˜x(˜ X∩Zk)=XI. The following lemma presents one possible realization of such a replacement of the decision variables x∈XI for (4.10) and (4.11). Lemma 4.7 Let u1,u2,u3,u4∈N0with u := u1+u2+u3+u4≥1, u odd, and let x∈{−1,0,1}. Then it holds x=xu1·sinu2x·π 2·cosu3(x−1)·π 2·tanu4x·π 4. 123
A test instance generator for MOMIPs 405 The idea of replacing decision variables by functions is also mentioned in Deb et al. (2005) as one possibility to obtain new optimization problems out of an existing one for which the nondominated set is already known. Moreover, while in Deb et al. (2005) the authors focus on purely continuous optimization problems, their approach to generate (scalable) test problems works in the purely integer case as well. Hence, we can use the exact same approach to also obtain multiobjective integer optimization problems (4.2). In fact, we can even reuse the presented test problem. More precisely, we can modify (4.8) and reduce it to the multiobjective binary optimization problem min xf(x) s.t. g(x)≤0, x∈XI={0,1}n (4.12) with the same assumptions, objective functions fi:Rn→R,i∈[p]and constraint function g:Rn→R. Then it holds for (4.12) that E={x∈{0,1}n|g(x)=0}, N={y∈{0,0.5}p|y1=0.5},and I,i=0.5 for all i∈[p]. However, one should keep in mind that for the construction of a test instance with the methods from Deb et al. (2005) a parametric description of the nondominated set is needed as a starting point. While this is often possible in continuous optimization, for the discrete nondominated set of multiobjective integer optimization problems this is usually much harder or leads to nondominated sets of a very simple structure as in the example above. For the same reason the approach from Deb et al. (2005) is not well suited in order to directly obtain test instances for multiobjective mixed-integer optimization problems. However, if there was some (nontrivial) nondominated set that has a parametric description consisting of both continuous and integer parameters then such a construction of test instances would be possible. To conclude this section, we present some examples for multiobjective mixedinteger optimization problems that are obtained by the proposed test instance generator when using the continuous and integer subproblems from the previous subsections as input. Example 4.8 (i) We choose as input for the multiobjective continuous optimization problem the biobjective subproblem (4.6) and for the multiobjective integer optimization problem the biobjective subproblem (4.10) with J=∅and m=2. Then we obtain by (4.7) and Lemma 4.4 (v) that C,i=1−exp(−4)<1=I,ifor all i∈[2]. Thus, we can set C:= C,I:= I, and α:= (1,1). The output of the test instance generator then is the separable biobjective mixed-integer nonconvex optimization problem (3.1) of Example 3.1 with E=x∈[−4,4]n x1=x2=...=xn∈−1 √n,1 √n 123
406 G. Eichfelder et al. ×{−1,0,1}2, N=1−exp(−4(t−1)2), 1−exp(−4t2)t∈[0,1] +{(δ, −δ) |δ∈{−2,−1,0,1,2}},and EI={−1,0,1}2. (ii) Let (4.4) be the input for the multiobjective continuous subproblem and (4.10)the input for the multiobjective integer subproblem. Then by (4.5) and Lemma 4.4 (v) it holds C,i=4>1=I,ifor all i∈[2]. Thus, we can use C:= C, I:= I, and 0 <α i<0.25 for all i∈[2]. The resulting test instance is the scalable separable biobjective mixed-integer convex optimization problem given by min x ⎛ ⎜ ⎜ ⎝ α1 n n i=1 x2 i+ i∈J xi+ i∈{n+1,...,n+m}\J xi α2 n n i=1 (xi−2)2+ i∈J xi− i∈{n+1,...,n+m}\J xi ⎞ ⎟ ⎟ ⎠ s.t. x∈X=[0,2]n×[−1,1]m∩Zm (4.13) with J{n+1,...,n+m}. For the efficient set, the nondominated set, and the set of efficient integer assignments we derive E=x∈[0,2]n|x1=x2=...=xn ×x∈[−1,1]m∩Zm|xi=−1 for all i+n∈J, N=α1t2,α 2(t−2)2t∈[0,2] +{(−m+δ,m−2|J|−δ) ∈Z2|δ∈{0}∪[2(m−|J|)]},and EI=x∈[−1,1]m∩Zm|xi=−1 for all i+n∈J. For an illustration of the nondominated set Nsee Fig.5. (iii) If (4.6) and (4.11) are chosen as input, then it holds C,i=1−exp(−4)> 0.25 =I,ifor all i∈[2]by (4.7) and Lemma 4.5 (v). Thus, we can again choose C:= Cand I:= I. For any choice 0 <α i<1 4·(1−exp(−4))for all i∈[2]we then obtain the scalable separable biobjective mixed-integer nonconvex optimization problem 123
A test instance generator for MOMIPs 407 Fig. 5 Nondominated set Nof the separable optimization problem (4.13)and nondominated set Ns Iof the corresponding integer subproblem (4.10) from Example 4.8 (ii)for J={n+1},m=3, and α1=α2=0.2 f1 f2 -3 -2 1 2 -3 -2 1 2 Ns I N min x ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ α11−exp − n i=1xi−1 √n2 + i∈J xi+ i∈{n+1,...,n+m−1}\J xi+0.75xm+n α21−exp − n i=1xi+1 √n2 + i∈J xi− i∈{n+1,...,n+m−1}\J xi−0.25xm+n ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ s.t. x∈X=[−4,4]n×([−1,1]m−1×[0,1])∩Zm (4.14) with J{n+1,...,n+m−1}. This leads to the efficient set, nondominated set, and set of efficient integer assignments given by E=x∈[−4,4]n x1=x2=...=xn∈−1 √n,1 √n ×x∈([−1,1]m−1×[0,1])∩Zm|xi=−1foralli+n∈J, N=α1(1−exp(−4(t−1)2)), α2(1−exp(−4t2))t∈[0,1]+(N1∪N2), N1={(−(m−1)+δ,m−1−2|J|−δ) ∈Z2|δ∈}, N2=(−(m−1)+0.75 +δ,m−1−2|J|−0.25 −δ)∈Z2δ∈, ={0}∪[2(m−1−|J|)],and EI=x∈([−1,1]m−1×[0,1])∩Zm|xi=−1foralli+n∈J. For an illustration of the nondominated set Nsee Fig.6. 123
408 G. Eichfelder et al. Fig. 6 Nondominated set Nof the separable optimization problem (4.14)and nondominated set Ns Iof the corresponding integer subproblem (4.11) from Example 4.8 (iii)for J={n+1},m=4, and α1=α2=0.2 f1 f2 -3 -2 1 2 -3 -2 1 2 Ns I N 5 Outlook In this paper, we presented a test instance generator for multiobjective mixed-integer optimization problems based on test instances for purely continuous and purely integer subproblems. By using the special separable structure, we were able to control the resulting efficient and nondominated sets as well as the number of efficient integer assignments. In this final section, we provide a brief outlook for three topics for further research. A first direction to follow is the collection and development of continuous and integer subproblems for the test instance generator. In particular, there is a need for subproblems with more than two or even a scalable number of objective functions. With regard to the purely integer subproblems (sMOMIPI), it would also be interesting to find examples that allow even more control over the efficient and nondominated set than (4.11). For instance, one could think of subproblems where the portion of supported nondominated points, i.e, nondominated points which can be found by solving a weighted sum of the objectives, can be controlled in a more direct way. Another aspect for future work would be a generalization of the test instance generator for non-separable test instances. A possible approach in this regard could be the use of a finite family of continuous subproblems instead of only a single subproblem (4.1). This would allow for a slightly stronger coupling of the integer and the continuous variables. Finally, recall that the main motivation for the development of the test instance generator was to obtain a set of benchmark problems that allows to compare and evaluate the strengths and weaknesses of solution algorithms for multiobjective mixedinteger optimization problems. Since such a set of benchmark problems can now be generated, corresponding numerical experiments would be the logical next step and a highly valuable contribution for the community. 123