Disjoint bilinear programming: a two-stage robust optimization perspective

Jianzhe Zhen, A. Marandi (Corresponding author), Dick den Hertog, Lieven Vandenberghe

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademic

Uittreksel

In this paper, we focus on a subclass of quadratic optimization problems, that is, disjoint bilinear programming problems. We show that disjoint bilinear programming problems can be cast as two-stage robust linear optimization problems with fixed-recourse and right-hand-side uncertainty, and techniques for two-stage robust optimization can be used to solve the resulting problems. To this end, a scheme based on a blending of Fourier-Motzkin elimination and linear decision rules is used. Moreover, we show that the approximation via linear decision rules for the two-stage robust optimization reformulation is equivalent to applying a reformulation-linearization technique to the original disjoint bilinear problem.
We then extend our approach to solve general bilinear problems. Numerical experiments on bimatrix games and concave quadratic minimization problems show that the proposed method is superior to the off-the-shelf solvers SCIP and CPLEX.
TaalEngels
Aantal pagina's34
TijdschriftOptimization Online
StatusGepubliceerd - 2018

Vingerafdruk

Linearization
Experiments
Uncertainty

Trefwoorden

    Citeer dit

    Zhen, Jianzhe ; Marandi, A. ; den Hertog, Dick ; Vandenberghe, Lieven . / Disjoint bilinear programming: a two-stage robust optimization perspective. In: Optimization Online. 2018
    @article{77fe2fa4486c42ada4391862f9054227,
    title = "Disjoint bilinear programming: a two-stage robust optimization perspective",
    abstract = "In this paper, we focus on a subclass of quadratic optimization problems, that is, disjoint bilinear programming problems. We show that disjoint bilinear programming problems can be cast as two-stage robust linear optimization problems with fixed-recourse and right-hand-side uncertainty, and techniques for two-stage robust optimization can be used to solve the resulting problems. To this end, a scheme based on a blending of Fourier-Motzkin elimination and linear decision rules is used. Moreover, we show that the approximation via linear decision rules for the two-stage robust optimization reformulation is equivalent to applying a reformulation-linearization technique to the original disjoint bilinear problem. We then extend our approach to solve general bilinear problems. Numerical experiments on bimatrix games and concave quadratic minimization problems show that the proposed method is superior to the off-the-shelf solvers SCIP and CPLEX.",
    keywords = "bilinear programming, linear decision rules, Fourier-Motzkin elimination, reformulation-linearization technique",
    author = "Jianzhe Zhen and A. Marandi and {den Hertog}, Dick and Lieven Vandenberghe",
    year = "2018",
    language = "English",
    journal = "Optimization Online",

    }

    Disjoint bilinear programming: a two-stage robust optimization perspective. / Zhen, Jianzhe; Marandi, A. (Corresponding author); den Hertog, Dick; Vandenberghe, Lieven .

    In: Optimization Online, 2018.

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademic

    TY - JOUR

    T1 - Disjoint bilinear programming: a two-stage robust optimization perspective

    AU - Zhen,Jianzhe

    AU - Marandi,A.

    AU - den Hertog,Dick

    AU - Vandenberghe,Lieven

    PY - 2018

    Y1 - 2018

    N2 - In this paper, we focus on a subclass of quadratic optimization problems, that is, disjoint bilinear programming problems. We show that disjoint bilinear programming problems can be cast as two-stage robust linear optimization problems with fixed-recourse and right-hand-side uncertainty, and techniques for two-stage robust optimization can be used to solve the resulting problems. To this end, a scheme based on a blending of Fourier-Motzkin elimination and linear decision rules is used. Moreover, we show that the approximation via linear decision rules for the two-stage robust optimization reformulation is equivalent to applying a reformulation-linearization technique to the original disjoint bilinear problem. We then extend our approach to solve general bilinear problems. Numerical experiments on bimatrix games and concave quadratic minimization problems show that the proposed method is superior to the off-the-shelf solvers SCIP and CPLEX.

    AB - In this paper, we focus on a subclass of quadratic optimization problems, that is, disjoint bilinear programming problems. We show that disjoint bilinear programming problems can be cast as two-stage robust linear optimization problems with fixed-recourse and right-hand-side uncertainty, and techniques for two-stage robust optimization can be used to solve the resulting problems. To this end, a scheme based on a blending of Fourier-Motzkin elimination and linear decision rules is used. Moreover, we show that the approximation via linear decision rules for the two-stage robust optimization reformulation is equivalent to applying a reformulation-linearization technique to the original disjoint bilinear problem. We then extend our approach to solve general bilinear problems. Numerical experiments on bimatrix games and concave quadratic minimization problems show that the proposed method is superior to the off-the-shelf solvers SCIP and CPLEX.

    KW - bilinear programming

    KW - linear decision rules

    KW - Fourier-Motzkin elimination

    KW - reformulation-linearization technique

    M3 - Article

    JO - Optimization Online

    T2 - Optimization Online

    JF - Optimization Online

    ER -