• 검색 결과가 없습니다.

PDF Research Reports on Mathematical and Computing Sciences

N/A
N/A
Protected

Academic year: 2023

Share "PDF Research Reports on Mathematical and Computing Sciences"

Copied!
31
0
0

로드 중.... (전체 텍스트 보기)

전체 글

The binary and complementarity conditions of combinatorial optimization problems can be expressed in several ways, each of which results in different conic relaxations. We also theoretically study the issue of primal and dual non-degeneracy, the existence of an interior solution and the magnitude of relaxations, as a result of different representations of the combinatorial state. These characteristics of conical relaxations affect the numerical efficiency and robustness of the solver used to solve them.

The optimal value of the non-convex QOP generally cannot be found exactly efficiently by a computational method. While many conic relaxations have been proposed for various QOP cases over the years, their equivalences and differences are not clearly understood for most conic relaxations. This difference is often caused by the difference in problem size, the existence of possible inner primal/dual solutions, and primal/dual non-degeneracy.

The aim of this paper is firstly to present a theoretical basis that reveals the underlying relations of various cone relaxations of QOPs arising from combinatorial optimization problems, in particular, their equivalences and differences with respect to the optimal value, the sizes of the conic relaxation problems, the existence of primal/dual interior feasible solutions, and the primal/dual non-degeneracy. This paper is organized as follows: In Section 2, we explain the lifting in Procedure (II) for QOP (1), and describe the simplification technique to reduce the size of the matrix variable, based on Burer's idea [9]. In Section 3.1 we first state three equivalent reformulations of the linear constraints in quadratic equalities, and show the equivalence between their lifted constraints.

Subsequently, the differences between the removed constraints of the 0-1 and complementarity conditions are discussed in section 3.2.

Representation of COP

By Lemma 3.3, the simplification technique described in section 2.3 can be applied to P(K1+n, L0 ∩La ∩Lb) without adding the lifted equalities x = Y h and hTY h = x0. In the remainder of this section, we impose an additional constraint, which is the barycenter of eJp (1≤p≤m), i.e. h= m1 Pm. DNN relaxations have been investigated as an efficient computational method to obtain good lower bounds for the QOP (2).

They are considered a good compromise between numerically intractable CPP relaxations and less efficient SDP relaxations. When we consider DNN relaxations for computation, we find that there are various DNN relaxations available. The size of the conic relaxations, the existence of primal/dual internal feasible solutions, and primal/dual non-degeneracy are the three most important factors for efficient and stable implementation of conic relaxations.

The size of a conic relaxation implies the dimension of the variable matrix and the number of linear equality constraints. The size (1 + n) of the variable matrix Z is reduced to n by the simplification technique in Section 3.4. The technique to reduce the number of linear equations can also be applied to L0E1 through L0C.

The existence of interior feasible solutions in the conical relaxations of QOP (2) is crucial for the successful computation of the primal dual interior points method and SDPNAL+, which were designed assuming the existence of primal and dual interior feasible solutions. If the assumption is not met, they may give inaccurate approximate optimal solutions and/or converge very slowly. Primal and dual nondegeneracy, which play an important role in the local convergence analysis of the primal dual interior point and SDPNAL+ methods, are discussed in Section 4.3.

The number of linear equalities

The existence of interior feasible solutions of COP and its dual

Nondegeneracy

It can be proved that if (Z,Z) is a non-degenerate feasible solution of SDP(11), then Z is a non-degenerate feasible solution of P(D1+nNN , L). 13) With a larger (or smaller)L, the possibility of the primary nondegeneracy (or the double nondegeneracy) can be expected to increase by both definitions of nondegeneracy for P(K1+n, L) and SDP ( 11). Burer argues in [9] that the simplification technique can increase the probability of the existence of viable interior solutions. Recall that the simplification depends on a nonzero h ∈ Rn+ satisfying x = Y h and hTY h = 1 for every feasible solution Z = x0 xT.

The primal and dual nondegeneracy of the simplified COP are discussed in Sections 5.1 and 5.3, respectively. Specifically, we show that the simplification is effective in increasing the possibility of non-degeneracy. We should note that the existence of an interior feasible solution of the dual of P(K1+n, L) and the primal and dual non-degeneracy depends on specific choices of La and Lb.

The dual nondegeneracy in the simplified COP

The binary integer quadratic problem

To enhance the DNN relaxation and derive the CPP reformulation [4, 9] of BIQP(15), we transform BIQP(15) into the following problem by using slack variables vj = 1−uj ≥0 (1≤i ≤r). Therefore, the discussions in Section 3 can be applied to derive different conic relaxations of BIQP (17) as special cases of P(K1+n, La∩Lb) and P0(Kn, L0a∩L0b). Applying Burer's CPP reformulation [9] of a class of linearly constrained QOPs in binary and continuous variables to BIQP (17), P(C1+nPP , LE3∩LZu) is obtained.

On the other hand, applying the CPP reformulation proposed by Arima, Kim and Kojima in [3] (see also [5, 16]) for a class of quadratic-constrained QOPs on BIQP (17) to P( C1+) leads nPP, LE1∩LC). They showed that the second relaxation is at least as effective as the first, that is, η(D1+rNN)≤ζp(D1+2rNN , LE1∩LC) in theory, and provided randomly generated numerical cases for which strict inequalities money. Furthermore, Kim and Kojima [14] presented a numerical example of BIQP (15) with r= 3 so that its DNN relaxation (16) with K1+r =D1+3NN only provides a strict lower bound ˆζ for the optimal value ζBIQP ∗ reached .

The quadratic assignment problem

More precisely, their optimal values ​​are the same, but the descriptions of the feasible regions are different. Other conditions appear in sections 6.2.1 and 6.2.2, but their exact forms are not relevant to the discussions there. The purpose of the numerical experiments here is to compare the numerical results obtained by solving those COPs with SDPT3 [26], SDPNAL+ [27] and the bisection and projection method (BP.

Recall that LE1sum is defined by (10), and that its simplification L0E1sum is given by Φ−1(LE1sum). c) The effectiveness and efficiency of solving a COP depends on numerical methods. We should note that DNN relaxations of the tested QAP instances are too large for SDPT3 to solve within reasonable CPU time. For BP, the stopping criterion for the length of the target search interval was set to δ = 0.1.

These values ​​are converted into differences in relative lower bounds relative to the upper lower bound and the ratio of run time and. We also calculate their mean and worst values ​​for all La, Lb, L0a and L0b (rows with 'all La' and 'all L0a', columns with 'all Lb' and 'all L0b' in Table 3.). The DNN relaxations with La ∈ {LE1sum, LE1} for sets 1, 2, and 3 of QAPs having only 1 or m linear equalities, on the other hand, are worse than the others in terms of lower bounds and runtime.

The performance could have been affected by the lack of dual interior feasible solutions and/or the failure of dual non-degeneracy due to the small dimension of L⊥a. When the DNN relaxation with Lb =LC and L0b =L0C was solved by SDPNAL+, the obtained average and worst lower bounds (ηm and ηw) were significantly inferior to the other cases of Lb =LZ and L0b =L0Z, especially when combined with La ∈ {LE1sum, LE1} and L0a ∈ {L0E1sum, L0E1}. In particular, BP has superior performance in solving the DNN relaxations with L0b = L0C in each set of QAP instances.

This demonstrates the robustness of BP for solving degenerate DNN problems and the effectiveness of the simplification technique when combined with BP. Since the stability of BP depends on the stability of the numerical algorithm used to check the dual feasibility of a given matrix, a simple condition (C) that imposes constraints on each element independently would be numerically preferable to condition (Z). Regarding the question (c) mentioned at the beginning of this section, we can conclude from the numerical results in Tables 2 and 3 that the relaxation of DNN with (La, Lb) = (LE3, LZ) and that of (L0a, L0b) = ( L0E3, L0Z) give better results when solved with SDPNAL+, while the DNN relaxation with (L0a, L0b) = (L0E1sum, L0C) is better solved with BP.

Many conic relaxations proposed for the combinatorial optimization problem are equivalent in terms of the quality of the optimal values ​​they provide. However, they differ in the size of the matrix variable, the number of linear equality and inequality constraints, the existence of an internally feasible solution, and primal/dual degeneracy, which are key issues for the operation of the numerical method.

Table 1: A sketch of the correspondence of some existing relaxations of the QAP to P( K 1+n , L a ∩L b ) with K 1+n = S 1+n+ , D 1+n NN or C 1+nPP , and P 0 ( K n , L 0 a ∩L 0 b ) with K n = S n + , D n NN or C n PP
Table 1: A sketch of the correspondence of some existing relaxations of the QAP to P( K 1+n , L a ∩L b ) with K 1+n = S 1+n+ , D 1+n NN or C 1+nPP , and P 0 ( K n , L 0 a ∩L 0 b ) with K n = S n + , D n NN or C n PP

수치

Table 1: A sketch of the correspondence of some existing relaxations of the QAP to P( K 1+n , L a ∩L b ) with K 1+n = S 1+n+ , D 1+n NN or C 1+nPP , and P 0 ( K n , L 0 a ∩L 0 b ) with K n = S n + , D n NN or C n PP
Table 2: Approximate optimal values of P( K 1+n , L a ∩ L b ) and P 0 ( K n , L 0 a ∩ L 0 b ) for small size QAP instances, tai10 and chr12a.
Table 3: The mean and worst-case values of relative lower bound differences η and ratios of the execution time σ

참조

관련 문서

The Australian Institute of Health and Welfare (AIHW) annually collects data from organisations funded by the Australian Government to provide one or more of the following