On the equivalence of linear complementarity problems

被引：18
作者：
De Schutter, B
Heemels, WPMH
Bemporad, A
机构：
[1] Delft Univ Technol, Fac ITS, NL-2600 GA Delft, Netherlands
[2] Eindhoven Univ Technol, Dept Elect Engn, NL-5600 MB Eindhoven, Netherlands
[3] Univ Siena, Dip Ingn Informaz, I-53100 Siena, Italy
来源：
OPERATIONS RESEARCH LETTERS | 2002年 / 30卷 / 04期
关键词：
complementarity problems; nonlinear algorithms; integer programming; optimization; linear complementarity problem;
D O I：
10.1016/S0167-6377(02)00159-1
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We show that the Extended Linear Complementarity Problem (ELCP) can be recast as a standard Linear Complementarity Problem (LCP) provided that the surplus variables or the feasible set of the ELCP are bounded. Since many extensions of the LCP are special cases of the ELCP, this implies that these extensions can be rewritten as an LCP as well. Our equivalence proof is constructive and leads to three possible numerical solution methods for a given ELCP: regular ELCP algorithms, mixed integer linear programming algorithms, and regular LCP algorithms. (C) 2002 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：211 / 222
页数：12
相关论文
共 47 条
[1]   On the convergence of the multisplitting methods for the linear complementarity problem [J].
Bai, ZZ .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1999, 21 (01) :67-78
[2]   Control of systems integrating logic, dynamics, and constraints [J].
Bemporad, A ;
Morari, M .
AUTOMATICA, 1999, 35 (03) :407-427
[3]   Smoothing methods for convex inequalities and linear complementarity problems [J].
Chen, CH ;
Mangasarian, OL .
MATHEMATICAL PROGRAMMING, 1995, 71 (01) :51-69
[4]   bc-opt:: a branch-and-cut code for mixed integer programs [J].
Cordier, C ;
Marchand, H ;
Laundy, R ;
Wolsey, LA .
MATHEMATICAL PROGRAMMING, 1999, 86 (02) :335-353
[5]  
Cottle R, 1992, The Linear Complementarity Problem
[6]  
Cottle RW., 1970, J COMBINATORIAL THEO, V8, P79, DOI [10.1016/S0021-9800(70)80010-2, DOI 10.1016/S0021-9800(70)80010-2]
[7]  
De Schutter B, 1998, SYST CONTROL LETT, V34, P63, DOI 10.1016/S0167-6911(97)00136-9
[8]   The extended linear complementarity problem [J].
De Schutter, B ;
De Moor, B .
MATHEMATICAL PROGRAMMING, 1995, 71 (03) :289-325
[9]   Optimal Traffic Light Control for a Single Intersection [J].
De Schutter, B. ;
De Moor, B. .
EUROPEAN JOURNAL OF CONTROL, 1998, 4 (03) :260-276
[10]   Optimal control of a class of linear hybrid systems with saturation [J].
De Schutter, B .
SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 2000, 39 (03) :835-851
12345