Finding Multiple Solutions in Nonlinear Integer Programming with Algebraic Test-Sets

Finding Multiple Solutions in Nonlinear Integer Programming with Algebraic Test-Sets M. I. Hartillo1(B),J.M.Jim´enez-Cobano2(B), and J. M. Ucha1,2(B) 1Departamento de Matem´atica Aplicada I., Universidad de Sevilla, Sevilla, Spain {hartillo,ucha}@us.es 2Insituto de Matem´aticas de la Universidad de Sevilla Antonio de Castro Brzezicki, Universidad de Sevilla, Sevilla, Spain [email protected] Abstract. We explain how to compute all the solutions of a nonlinear integer problem using the algebraic test-sets associated to a suitable linear subproblem. These test-sets are obtained using Gr¨obner bases. The main advantage of this method, compared to other available alternatives, is its exactness within a quite good efficiency. 1 Introduction In many real-life combinatorial optimization problems it is of great interest for the decision-maker to have not only one solution, but the set of all optimal solutions (see [15]or[11], for example). The information provided by this set can give some unexpected insights about the features of the solutions, and sometimes stands as a first step for multi-objective optimization as well. On the other hand, sometimes these problems require nonlinear constraints to be modeled properly. In [14] a method for problems of the form min cxt s.t.Ax t≤bt x∈Ω x∈Nn (1) where A∈Zm×n,c ∈Zn,b ∈Zm(operator tstands for transposition) and the region Ωis finite and defined by linear and nonlinear constraints, was proposed. This method makes use of the so called test-sets associated to the linear subproblem min cxt s.t.Ax t≤bt(2) x ∈ Nn First author is partially supported by MTM2016-75024-P and MTM2016-74983-C21-R. Third author is partially supported by MTM2016-75024-P, P12-FQM-2696 and MTM2016-74983-C2-1-R. V. P. Gerdt et al. (Eds.): CASC 2018, LNCS 11077, pp. 230–237, 2018. https://doi.org/10.1007/978-3-319-99639-4_16 Multiple Solutions in Nonlinear IP with Test-Sets 231 Definition 1. AsetT⊂Znis a test-set associated to problem 2if T⊂ker(A), and for any non optimal xfeasible for 2there exists a t∈Tsuch that x−tis feasible and c(x−t)<c(x). As a consequence of this definition, starting from an optimal point ˆxof problem 2you can recover the set of all the feasible points, adding elements of the test-set until you eventually complete all the feasible region. In this way, you can obtain the optimal points of problem 1walking back from the linear optimal point until you reach the region Ω. Technical details can be found in [14]. The feasible region will be supposed finite, although this is not strictly necessary. There are several ways of computing test-sets (as a matter of fact, they can be computed depending only on the cost and the matrix of constraints, not taking into account the right hand side, for example). One of the most efficient and manageable ways is using Gr¨obner bases (see for example [7]) with the software 4ti2 (see [9]). This approach is based in the classical paper [4], that shows how to solve a Linear Integer problem obtaining Gr¨obner bases of a suitable binomial ideal with respect to an ordering compatible with the cost function. In [3,10] the method of [14] is applied to real-life size problems with very competitive results. In this work, we (1) explain how to modify the walk-back method to obtain all the optimal points, and (2) compare its performance with the natural generalization of the algorithm presented in [15] and with the commercial software BARON (see [1]). Remark 1. The ideals corresponding to the method that we present in this work are not zero-dimensional, so some efficient strategies as Triangular Decomposition can not be applied for the Gr¨obner bases computations. In principle, the method proposed in [2] would be an alternative to treat some Nonlinear Integer Optimization problems with zero-dimensional ideals, but as soon as some constraints can not be expressed in terms of polynomials or the rank of values of the variables is big the method is useless. 2 Finding All the Optimal Points with a General Integer Cut In [15] a method is introduced to show how to compute all the optimal points in Integer Linear Problems. Once an optimal point is obtained, the idea is to add some conditions to make it unfeasible and solve again. More precisely, if you are solving the problem 1and have obtained an optimal solution (x0 1,...,x 0 n)you can add the constraint n  i=1 |xi−x0 i|≥1 to assure that (x0 1,...,x 0 n) is unfeasible for this new problem. As you obtain new optimal solutions you have to add a similar constraint for each solution. This formulation can be linearized, as it is explained in [15, Prop. 1]. This method 232 M. I. Hartillo et al. can be used for Nonlinear Integer problems simply considering problems of the form min cxt s.t.Ax t≤bt n i=1 |xi−xj i|≥1,j =1,...,N x∈Ω x∈Nn with Nconstraints to try to obtain the (N+ 1)-th optimal point. One of the aims of this paper is to compare this natural approach to an alternative algebraic method. 3 Finding All the Optimal Points with Test-Sets Our algorithm is based on the algebraic algorithm of [14] that provides one solution for a given nonlinear integer problem of the form min cxt s.t.Ax t≤bt x∈Ω x∈Nn (P) where A∈Zm×n,c∈Zn,andb∈Zm. Let us describe the steps of our method: – We start, as in the algorithm proposed in [14], in the optimal point for a suitable linear subproblem min cxt s.t.Ax t≤bt x∈Nn (PL) Remark 2. The selection of the subproblem has to do first with the computability of the test-set, that can be a bottleneck as it is a computation of a Gr¨obner basis of a certain ideal (see [7]). Moreover, although the test-set of the whole linear part of problem 1is available, sometimes it is better to compute the test-set associated to a submatrix of Athat gives us a more manageable number of directions to be considered at any point during the walk-back. The constraints that are not included in the submatrix are simply added to the description of Ω. – Then we systematically add the elements of the corresponding test-set, thus worsening the cost function trying to obtain in return feasible points for problem 1, until we get into Ω. – The difference to the original method (that was designed to find only one optimal point) is that now we have to manage the searching of new possible optimal points inside Ω, once we have reached a candidate. While in the algorithm of [14] you discard new points with the same optimal value, we instead stock them in a provisional list. This list will be the set of optimal points as long as we find a new better value inside the region Ω. Multiple Solutions in Nonlinear IP with Test-Sets 233 – If we eventually find an improvement in the cost we delete the provisional list. Otherwise, we already have the set of optimal points. The pseudocode of our algorithm is the following one: INPUT: c, A, b;Ω; optimal point βof 2;Tassociated test-set of problem 2. Opt := ∅; Leaves := {β+t|∀t∈T}∩Nn costOpt =∞ IF β∈Ω THEN Opt := {β}; costOpt := cβt WHILE (Leaves =∅)DO FOR h∈Leaves DO IF c(h)<costOpt Leaves =(Leaves \{h})∪({h+t|∀t∈T}∩Nn) IF h∈Ω THEN Opt ={h}; costOpt =cht; Leaves =(Leaves \{h})∪({h+t|∀t∈T}∩Nn) the list of old candidates is deleted and updated with a new candidate ELSE IF c(h)>costOpt THEN Leaves =Leaves \{h} these branches are discarded ELSE IF c(h)=costOpt THEN Leaves =(Leave \{h})∪({h+t|∀t∈T}∩Nn) IF h∈Ω THEN Opt =Opt ∪{h}; a new candidate to be an optimal point has been obtained END WHILE OUTPUT: Opt the set of all optimal points of problem 1with cost costOpt Remark 3. It is straightforward to modify this algorithm to obtain the Kbest optimal points for a given K,asin[11]. 4 Computational Experiments We have run all the examples to test our algorithm coded in Python in a computer with an Intel Core i5, 3.5 Ghz, 8 Gb of RAM, under Ubuntu. The examples with BARON [1] and COUENNE [6] have been sent to neos-server.org. We have studied two families of examples: the integer portfolio problem and the problem of reliability in series-parallel systems. 234 M. I. Hartillo et al. 4.1 Integer Portfolio Problem In the integer portfolio problem (see [3]) we have to solve problems of the form max n  i=1 cixi s.t. xCxt≤R0 n  i=1 bixi≤B x∈Nn (3) where biare the prices today of nalternative investments or assets; cia forecast for their future prices; the matrix Chas to do with the covariance matrix of the historical returns of the assets and it is a way of measuring the risk of a portfolio; R0stands for the maximum admissible risk; Bis the available budget. This so called mean-variance portfolio model was introduced by Markowitz with continuous variables (see [12] for the model and [5]or[16] for the mixedinteger case), but it is interesting to consider the case of integer variables: first to take into account the finite divisibility of the assets and second to consider some logical conditions that appear in these problems. If you consider tailored examples for which two or more variables have the same price and risk you obtain many different optima and can compare our method to the generalization of [15]. As a general outcome we have obtained that as the number of optimal points increases our method overcomes by far the general cut method (coded in GAMS for COUENNE). Thereby, you can consider for example the simple case max 2x1+x2+x3+···+xn−1+xn s.t. x1+x2+x3+···+xn−1+xn≤B x1···xnC⎛ ⎜ ⎝ x1 . . . xn ⎞ ⎟ ⎠≤R0 x∈Nn (4) with Cdefined by cii =0.05,c ij =−0.01 if i=jfor n=10,15,20,50,100, B= 10 and a not very tight R0to include many points. In this family of examples you can obtain thousands of optimal points. In average our method is more than a hundred times faster for big numbers of optimal points. Remark 4. Comparing with the commercial software BARON, that has the option of computing the Kbest optimal solutions, we obtain better running times only in 15% of the cases. Nevertheless, our method obtains exactly the complete set of optimal points in all cases. BARON, in contrast to our method, fails in 11% of the cases: in 5% of the cases it does not obtain the optimal cost and in 6% does not find the complete set, due to rounding problems. Multiple Solutions in Nonlinear IP with Test-Sets 235 4.2 Reliability Problems The redundancy allocation problem can be formulated as the minimization of the design cost of a series-parallel system with multiple component choices, while ensuring a given system reliability level. The obtained model is a nonlinear integer programming problem with a nonlinear, nonseparable constraint (see [8,13] or [10]). It has the form min n  i=0 k  j=1 cijxij s.a. R(x)≥R0 k  j=1 xij ≥1,∀i=1,...,n 0≤xij ≤uij,∀i=1,...,n, j =1,...,k xij ∈Z+ (5) with R(x)= n  i=1 1− k  j=1 (1 −rij)xij . In this problem nis the number of subsystems (in series); kithe number of different types of available components (in parallel) for the i-thsubsystem,1≤i≤n;rij the reliability of the j-th component for the i-th subsystem, 1 ≤i≤n, 1≤j≤ki;cij , the cost of the j-th component for the i-th subsystem, 1 ≤i≤n, 1≤j≤ki;lij,u ij, lower/upper bounds of number of jcomponents for the i-th subsystem, 1 ≤i≤n, 1≤j≤ki; R0, an admissible level of reliability of the whole system; xij, number of jcomponents used in the i-th subsystem, 1 ≤i≤n, 1≤j≤ki. We have studied about 100 examples with 2, 3 and 4 subsystems and with 2 or 3 components in each subsystem (the costs and reliabilities generated randomly, rij ∈[0.90,0.99] and R0=0.90). The summary is in Tables 1,2and 3 and contains only the information about the examples with multiple number of solutions. Table 1. Reliability examples n=3,k=2,3. Average CPU Time % Complete set of optimal solutions found Test-set 0.2 100 % BARON K-best 0.2 100 % General cut 0.54 100 % Table 2. Reliability examples n=4,k=2. Average CPU Time % Complete set of optimal solution found Test-set 0.46 100 % BARON K-best 0.21 72.72 % General cut 0.98 100 % 236 M. I. Hartillo et al. Table 3. Reliability examples n=4,k=3. Average CPU Time % Complete set of optimal solution found Test-set 1.1 100 % BARON K-best 0.19 61.54 % General cut 1.29 100 % We can observe that: – The test-set method and the general cut method are exact. BARON, on the contrary, does not give the complete set of optimal points or even one (in fact, usually provides only one although you ask for the best 3 or 4 best) in about30%ofthecases. – BARON is better in CPU time than the test-set method, and this is better than the general cut method, and much better as the number of optimal points increases substantially. If, for example, you treat an example with a hundred optimal points you have to solve 99 problems with 1, 2, ...,99new constraints, respectively. 5 Conclusions We have presented an exact method to obtain the set of all optimal points for a given Nonlinear Integer problem as problem 1. A convenient linear subproblem is selected and then, walking back from an optimal point of this linear subproblem with the help of a test-set, the feasible region of the original problem is reached in all different ways, updating a list of optimal points. In this work we have studied two families of examples: – Portfolio integer problems that can produce a huge number of optimal points and for which our algorithm overcomes a general cut approach as the one proposed in [15]. – Reliability problems, in which we point out problems of lack of exactness in the commercial software BARON compared with our approach. References 1. Sahinidis, N. V.: BARON 14.4.0: Global Optimization of Mixed-Integer Nonlinear Programs. User’s Manual (2014) 2. Bertsimas, D., Perakis, G., Tayur, S.: A new algebraic geometry algorithm for integer programming. Manag. Sci. 46(7), 999–1008 (2000) 3. Castro, F.J., Gago, J., Hartillo, I., Puerto, J., Ucha, J.M.: An algebraic approach to integer portfolio problems. Eur. J. Oper. Res. 210(3), 647–659 (2011) 4. Conti, P., Traverso, C.: Buchberger algorithm and integer programming. In: Mattson, H.F., Mora, T., Rao, T.R.N. (eds.) AAECC 1991. LNCS, vol. 539, pp. 130–139. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-54522-0 102 Multiple Solutions in Nonlinear IP with Test-Sets 237 5. Corazza, M., Favaretto, D.: On the existence of solutions to the quadratic mixedinteger mean-variance portfolio selection problem. Eur. J. Oper. Res. 176, 1947– 1960 (2007) 6. Belotti, P.: COUENNE: a user’s manual. Department of Mathematics Sciences, Clemson University. https://www.coin-or.org/Couenne/ 7. Cox, D.A., Little, J., O’Shea, D.: Using Algebraic Geometry. Graduate Texts in Mathematics, vol. 185, 2nd edn. Springer, Hiedelberg (2005). https://doi.org/10. 1007/978-1-4757-6911-1 8. Djerdjour, M., Rekab, K.: A branch and bound algorithm for designing reliable systems at a minimum cost. Appl. Math. Comput. 118, 247–59 (2001) 9. 4ti2 team: 4ti2 - a software package for algebraic, geometric and combinatorial problems on linear spaces (2013). https://www.4ti2.de 10. Gago, J., Hartillo, I., Puerto, J., Ucha, J.M.: Exact cost minimization of a series-parallel reliable system with multiple component choices using an algebraic method. Comput. Oper. Res. 40(11), 2752–2759 (2013) 11. Le˜ao, A.A.S., Cherri, L.H., Arenales, M.N.: Determining the K-best solutions of knapsack problems. Comput. Oper. Res. 49, 71–82 (2014) 12. Markowitz, H.: Portfolio selection. J. Finance 7, 77–91 (1952) 13. Ruan, N., Sun, X.L.: An exact algorithm for cost minimization in series reliability systems with multiple component choices. Appl. Math. Comput. 181, 732–41 (2006) 14. Tayur, S.R., Thomas, R.R., Natraj, N.R.: An algebraic geometry algorithm for scheduling in presence of setups and correlated demands. Math. Program. Ser. A 69(3), 369–401 (1995). https://doi.org/10.1007/BF01585566 15. Tsai, J.-F., Lin, M.-H., Hu, Y.-C.: Finding multiple solutions to general integer linear programs. Eur. J. Oper. Res. 184(2), 802–809 (2008) 16. Li, H.-L., Tsai, J.-F.: A distributed computation algorithm for solving portfolio problems with integer variables. Eur. J. Oper. Res. 186(2), 882–891 (2008)