Izvorni znanstveni članak
https://doi.org/10.17535/crorr.2024.0006
A dual method for polar cuts in disjoint bilinear programming
Xiaosong Ding
; International Business School, Beijing Foreign Studies University, Beijing, P.R.China, 100089
Jun Ma
; International Business School, Beijing Foreign Studies University, Beijing, P.R.China, 100089
Xi Chen
; International Business School, Beijing Foreign Studies University, Beijing, P.R.China, 100089
Chao Liu
; International Business School, Beijing Foreign Studies University, Beijing, P.R.China, 100089
Sažetak
As one branch of deterministic approaches to disjoint bilinear programming, cutting plane methods are renowned for its ability to systematically reduce the search space by adding cutting planes that are able to cut off regions deemed infeasible or suboptimal. Polar cuts have been widely utilized as a dominating type of cut in terms of deepness. During the establishment of a polar cut, the modified Newton's method is employed to derive the cutting points along the positive or negative extensions of edges emanating from a local solution. Nonetheless, its performance can be further improved along the positive extensions. Drawing inspiration from integer programming, we develop a new approach based on the LP duality theory for this purpose. It re-formulates the original program with a piece-wise linear concave objective function as a single LP. Moreover, we propose a new technique to derive the edges as accommodation to degeneracy. Numerical results show that, by utilizing our newly developed dual method, computing time can be gradually saved as the percentage of generated cutting points along the positive extensions of edges rises.
Ključne riječi
degeneracy; disjoint bilinear programming; duality; LP; polar cuts
Hrčak ID:
317484
URI
Datum izdavanja:
27.5.2024.
Posjeta: 0 *