FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » num-analysis
Minimal set of linear constraints
Post new topic   Reply to topic Page 1 of 1 [4 Posts] View previous topic :: View next topic
Author Message
Alec.Edgington@blueyonder
science forum beginner


Joined: 14 Jun 2006
Posts: 3

PostPosted: Wed Jun 14, 2006 10:21 am    Post subject: Minimal set of linear constraints Reply with quote
If I have a set of linear constraints of the form

< a , x > <= 1 (for all a in S)

for some finite set S of n-dimensional vectors, where <,> is the scalar
product, is there a good algorithm for finding the minimal subset T of
S such that the solution set to

< a , x > <= 1 (for all a in T)

is the same? In other words, I want to find which of the constraints
are relevant and which are redundant -- with reasonable efficiency.

Thanks for any help.

Alec
Back to top
Peter Spellucci
science forum Guru


Joined: 29 Apr 2005
Posts: 702

PostPosted: Wed Jun 14, 2006 2:26 pm    Post subject: Re: Minimal set of linear constraints Reply with quote
In article <1150280498.404844.8580@f6g2000cwb.googlegroups.com>,
Alec.Edgington@blueyonder.co.uk writes:
Quote:
If I have a set of linear constraints of the form

a , x > <= 1 (for all a in S)

for some finite set S of n-dimensional vectors, where <,> is the scalar
product, is there a good algorithm for finding the minimal subset T of
S such that the solution set to

a , x > <= 1 (for all a in T)

is the same? In other words, I want to find which of the constraints
are relevant and which are redundant -- with reasonable efficiency.

Thanks for any help.

Alec


this is not as easy as it might appear: there some papers on it, AMPL has it
built in, here are the papers:

10. Zbl 0651.90047 Caron, R.J.; McDonald, J.F.; Ponic, C.M.
A degenerate extreme point strategy for the classification of linear constraints as redundant or necessary. (English)
J. Optimization Theory Appl. 62, No.2, 225-237 (1989)

12. Zbl 0644.90085 Horst, Reiner; de Vries, Jakob; Thoai, Nguyen V.
On finding new vertices and redundant constraints in cutting plane algorithms for global optimization. (English)
Oper. Res. Lett. 7, No.2, 85-90 (1988).

13. Zbl 0527.90066 Telgen, Jan
Identifying redundant constraints and implicit equalities in systems of linear constraints. (English)
Manage. Sci. 29, 1209-1222 (1983). MSC 1991:

14. Zbl 0423.90043 Telgen, J.
On R. W. Llewellyn's rules to identify redundant constraints: A detailed critique and some generalizations. (English)
Z. Oper. Res., Ser. A 23, 197-206 (1979).

15. Zbl 0389.90065 Telgen, Jan
Redundant constraints in linear programming problems. (English)
Oper. Res. Verf. 28, 2nd Symp. Oper. Res., Teil 1, Aachen 1977, 420-433 (1978).

17. Zbl 0122.15302 Charnes, A.; Cooper, W.W.; Thompson, G.L.
Some properties of redundant constraints and extraneous variables in direct and dual linear programming problems (English)
Oper. Res. 10, 711-723 (1962).

astonishingly nothing else in Zentralblatt and Math. Reviews

hth
peter
Back to top
Alec.Edgington@blueyonder
science forum beginner


Joined: 14 Jun 2006
Posts: 3

PostPosted: Wed Jun 14, 2006 3:10 pm    Post subject: Re: Minimal set of linear constraints Reply with quote
Thanks very much for these pointers.

Alec
Back to top
Robert B. Israel
science forum Guru


Joined: 24 Mar 2005
Posts: 2151

PostPosted: Wed Jun 14, 2006 6:46 pm    Post subject: Re: Minimal set of linear constraints Reply with quote
In article <1150280498.404844.8580@f6g2000cwb.googlegroups.com>,
<Alec.Edgington@blueyonder.co.uk> wrote:
Quote:
If I have a set of linear constraints of the form

a , x > <= 1 (for all a in S)

for some finite set S of n-dimensional vectors, where <,> is the scalar
product, is there a good algorithm for finding the minimal subset T of
S such that the solution set to

a , x > <= 1 (for all a in T)

is the same? In other words, I want to find which of the constraints
are relevant and which are redundant -- with reasonable efficiency.

A quick-and-dirty way to do it: the constraint <a,x> <= 1 is redundant
iff the linear programming problem:

max <a,x>
subject to all the other constraints

has optimal value <= 1. Just go through the list of constraints once:

T := S;
for a in S do
if (max <a,x> subject to constraints in T minus {a}) <= 1 then
T := T minus {a}

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
Back to top
Google
Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [4 Posts] View previous topic :: View next topic
The time now is Sat Jan 10, 2009 12:58 am | All times are GMT
Forum index » Science and Technology » Math » num-analysis
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Linear operator and determinant aline Math 0 Wed Nov 29, 2006 2:37 am
No new posts Degrees of freedom = # constraints ? TTroy Math 4 Mon Jul 17, 2006 8:00 pm
No new posts approximating infinite linear program... diegotorquemada@yahoo.com Math 0 Mon Jul 17, 2006 10:29 am
No new posts Linear algebra txtbk recommendations... Snis Pilbor Math 1 Sat Jul 15, 2006 11:40 pm
No new posts Iterative solution to non-linear equa... laniik Math 5 Fri Jul 14, 2006 6:38 pm

Problem Mortgage | Naruto | Mobile Phone | Loans | Debt Consolidation
Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums


Powered by phpBB © 2001, 2005 phpBB Group

[ Time: 0.1536s ][ Queries: 16 (0.0757s) ][ GZIP on - Debug on ]