Application Center - Maplesoft
  Submit your work
Application Center Applications A Computational Approach to Essential and Nonessential Objective Functions in Linear Multicriteria Optimization Preview

App Preview:

A Computational Approach to Essential and Nonessential Objective Functions in Linear Multicriteria Optimization

You can switch back to the summary page by clicking here.

Learn about Maple
Download Application

 

 

A Computational Approach to Essential and Nonessential Objective
Functions in Linear Multicriteria Optimization 

Agnieszka B. Malinowska
Faculty of Computer Science
Technical University of Bialystok
15-351 Bialystok, Poland
abmalina@pb.bialystok.pl 

Delfim F. M. Torres
Department of Mathematics
University of Aveiro
3810-193 Aveiro, Portugal
delfim@mat.ua.pt 

 

Last Change: 03 December 2008 

 

 

This work was initiated  while the first author was visiting the Department of Mathematics of the University of Aveiro, Portugal,
from June 5 to June 12, 2006, and then continued during two more visits of the first author to the University of Aveiro: January 4
to January 18, 2007; and from May 1 to May 10, 2007. 

 

The financial support and the good working conditions provided by the R&D Centre for "Research on Optimization and Control" of the
Department of Mathematics of the University of Aveiro is here acknowledged. 

 

The theory behind this Maple package can be found in the following reference and references therein: 

Main Reference 

[1]  Agnieszka B. Malinowska and Delfim F. M. Torres,
Computational Approach to Essential and Nonessential
Objective Functions in Linear Multicriteria Optimization,
J. Optim. Theory Appl. (2008) 139: 577--590.
[DOI: 10.1007/s10957-008-9397-z] 

 

> restart;
 

> ##################################################################
 

> # GL method
 

> # returns true if F[-1] is nonessential;
# returns false if we can not conclude nothing from GL method
 

> ##################################################################
 

> glm := proc(F,NumVar)
 

>  local c, f, v, LV, lc, SolSet, SS, i;
 

>  c := proc(var,exp)
 

>    local v;
 

>    v:= select(has,exp+abm,var);
 

>    if v = NULL then
 

>      return(0);
 

>    else
 

>      return(v/var):
 

>    fi:
 end proc;
 

>  f := o -> if type(o,numeric) then o else 0 fi:
 

>  v := (exp,n) -> Vector([seq(f(c(x||i,exp)),i=1..n)]):
 

>  LV := [seq(LinearAlgebra[VectorScalarMultiply](v(F[i],NumVar),alpha||i),i=1..nops(F)-1)];
 

>  lc := Vector(NumVar);
 

>  for i in LV do
 

>    lc := LinearAlgebra[VectorAdd](lc,i):
 

>  od;
 

>  SolSet := solve({seq(lc[i]=c(x||i,F[-1]),i=1..NumVar)});
 if SolSet = NULL then
   return(false);
 else
 

>    SS := {seq(simplex[maximize](alpha||i,SolSet,NONNEGATIVE),i=1..nops(F)-1)};
 

>    if SS = {{}} then
 

>      return(false);
 

>    else
 

>      return(true);
 

>    fi:
 fi:
 

> end proc:
 

> glm([x1-x2,3*x1+x2,x2],2);
 

false (1)
 

> glm([x1+3*x2,3*x1,2*x1+x2,-3*x1-x2],2);
 

false (2)
 

> glm([x1-3*x2-x3,2*x2+3*x3,2*x1-4*x2+x3],3);
 

true (3)
 

> glm([x1+3*x2,3*x1,-3*x1-x2,2*x1+x2],2);
 

true (4)
 

> glm([x1+x2+x3,-x1+x2+x3,x1+x2],3);
 

false (5)
 

> glm([-x2,x2],2);
 

false (6)
 

> ###################
 

> # step 1       
 

> ###################
 

> step1 := proc(F)
 

>  local of, const, S;
 

>  of := add(v||i,i=1..nops(F));
 

>  const := seq(-F[i]+v||i=0,i=1..nops(F));
 const := [const,seq(v||i>=0,i=1..nops(F))];
 

>  S := simplex[maximize](of,const);
 

>  return(not(evalb(subs(S,of)=0))):
 

> end proc:
 

> step1([x1+x2+x3, -x1+x2+x3, x1+x2]);
 

true (7)
 

> step1([x1+3*x2, 3*x1, -3*x1-x2, 2*x1+x2]);
 

false (8)
 

> step1([x1+3*x2, 3*x1, 2*x1+x2, -3*x1-x2]);
 

false (9)
 

> step1([-x1-2*x2+2*x3, 2*x1+3*x2,-x1-x2-2*x3]);
 

false (10)
 

> step1([x1+4*x2-x3+2*x4-3*x5,2*x1-x3-4*x4+x5,-4*x1-8*x2+3*x3+5*x5,-7*x1-4*x2+4*x3+10*x4]);
 

false (11)
 

> ###################
 

> # step 2       
 

> ###################
 

> step2 := F -> step1(F[1..-2]):
 

> step2([x1+3*x2, 3*x1, -3*x1-x2, 2*x1+x2]);
 

false (12)
 

> step2([x1+3*x2, 3*x1, 2*x1+x2, -3*x1-x2]);
 

true (13)
 

> step2([-x1-2*x2+2*x3, 2*x1+3*x2,-x1-x2-2*x3]);
 

true (14)
 

> step2([x1+4*x2-x3+2*x4-3*x5,2*x1-x3-4*x4+x5,-4*x1-8*x2+3*x3+5*x5,-7*x1-4*x2+4*x3+10*x4]);
 

false (15)
 

> ###################
 

> # step 3
 

> ###################
 

> step3 := proc(NumVar,X)
 

>  local LHS, RHS, SC1, SC2, SC3, SC, SS3, i, a, epsilon, mylhs, myrhs;
 epsilon := 0.001;
 mylhs := E -> if type(lhs(E),numeric) then rhs(E) else lhs(E) fi:
 

>  myrhs := E -> if type(rhs(E),numeric) then rhs(E) else lhs(E) fi:
 

>  LHS := [seq(mylhs(i),i=X)];
 

>  RHS := [seq(myrhs(i),i=X)];
 

>  SC1 := {seq(LHS[i]+a+v||i = RHS[i],i=1..nops(LHS))};
 

>  SC2 := {seq(v||i >= 0,i=1..nops(LHS)), a>=0};
 

>  SC3 := {seq(x||i>=0.001,i=1..NumVar)};
 

>  SC := SC1 union SC2 union SC3;
 

>  SS3 := simplex[maximize](a,SC);
 

>  assign(select(has,SS3,a));
 

>  if a = 0 then return(false) else return(true) fi;
 

> end proc:
 

> step3(3,{x1 <= 1, x2 <= 1});
 

true (16)
 

> step3(2,{x1+x2<=1,-x1-x2<=-1});
 

false (17)
 

> step3(3,{x2+x3<=2,-x2-x3<=-2,x1+x2+x3<=3,-x1-x2-x3<=-2,x1+x2<=2});
 

false (18)
 

> step3(2,{x1+x2<=1,-x1-x2<=-1});
 

false (19)
 

> ###################################################################
 

> # step 4
 

> # uses rank method
 

> # procedure step4 does not use the last objective function F[-1]
 

> # procedure matrixA is used in steps 4 and 7  
 

> ###################################################################
 

> matrixA := proc(X,NumVar)
 

>  local c, LHS, row, mylhs;
 

>  mylhs := E -> if type(lhs(E),numeric) then rhs(E) else lhs(E) fi:  
 

>  c := (var,exp) -> if evalb({select(has,exp,var)} = {}) then 0 else select(has,exp,var)/var fi:
 

>  LHS := [seq(mylhs(i)+abm,i=X)];
 

>  row := (exp,NumVar) -> map(c,[seq(x||i,i=1..NumVar)],exp):
 

>  return(Matrix(map(row,LHS,NumVar)));
 

> end proc:
 

> ###############################
 

> Proposition4dot12 := proc(F,X,LE)
 

>  local SE, v, ETS, solW,  SS, SV;
 

>  SE := NULL;
 

>  for v in LE do
 

>    SV := subs(v,F);  
 

>    SE := SE, add(SV[i]*w||i,i=1..nops(SV));
 

>  od;
 

>  ETS := seq(SE[1]=i,i=SE[2..-1]), add(w||i,i=1..nops(SV))=1;
 

>  solW := solve({ETS, add(w||i,i=1..nops(SV))=1}) union {seq(w||i>=0.00001,i=1..nops(SV))};
 

>  SS := {seq(simplex[maximize](w||i,solW),i=1..nops(SV))};
 

>  return(not(remove(i->i={},SS) = {}));
 

> end proc:
 

> step4 := proc(F,X,NumVar)
 

>  local NX,NNumVar,b,A,rnk,dif,LP,zero,efficient,v,admissible,
       vs,AM,sol,of,cstEps,cst,SC,p,myrhs,mylhs,LE, tv, val;
 myrhs := E -> if type(rhs(E),numeric) then rhs(E) else lhs(E) fi:
 mylhs := E -> if type(lhs(E),numeric) then rhs(E) else lhs(E) fi:
 tv := (x,s) -> myrhs(op(select(has,s,x))):
 

>  b := X -> Vector([seq(myrhs(i),i=X)]):  
 

>  NX := {seq(mylhs(X[i])+x||(NumVar+i)=myrhs(X[i]),i=1..nops(X))};
 

>  NNumVar := NumVar+nops(X);
 

>  A := matrixA(NX,NNumVar);
 

>  rnk := LinearAlgebra[Rank](A);
 

>  dif := NNumVar - rnk;
 

>  LP := combinat[choose]([seq(x||i,i=1..NNumVar)],dif);
 

>  zero := L -> {seq(i=0,i=L)}:
 

>  efficient := true;
 

>  v := Vector([seq(x||i,i=1..NNumVar)]);
 

>  admissible := sc -> not(member(false,{seq(evalb(myrhs(i)>=0),i=sc)})):
 LE := NULL;
 

>  for p in LP while efficient do
 

>    vs := subs({seq(i=0,i=p)},v);
 

>    AM := LinearAlgebra[MatrixVectorMultiply](A,vs);
 

>    sol := solve({seq(AM[i]=b(NX)[i],i=1..nops(NX))});
   if not(sol = NULL) and admissible(sol) then
     sol := sol union zero(p):
 

>      of := add(epsilon||i,i=1..nops(F)-1);    
 

>      cstEps := seq(epsilon||i>=0,i=1..nops(F)-1);
 

>      cst := seq(F[i]-epsilon||i=subs(sol,F[i]),i=1..nops(F)-1);
 

>      SC := {cst} union {cstEps} union NX;
 

>      efficient := evalb(subs(simplex[maximize](of,SC,NONNEGATIVE),of)=0);
     if efficient then
       val := [seq(tv(x||i, sol),i=1..NumVar)];        
       if not(member(false,map(i->type(i,numeric),val))) then
         LE := LE, {seq(x||i=val[i],i=1..NumVar)};
       fi;
     fi;
   fi:
 

>  od;
 if not(efficient) then
 

>    return(efficient);
 else
   Proposition4dot12(F[1..-2],X,{LE});
 fi:
 

> end proc:
 

> # examples
 

> step4([x1+3*x2, 2*x1+x2],{x1+x2<=1,-x1-x2<=-1},2);
 

false (20)
 

> step4([x1+3*x2, 2*x1+x2, 3*x1, -3*x1-x2],{x1+x2<=1,-x1-x2<=-1},2);
 

true (21)
 

> step4([-x1-2*x2+2*x3, 2*x1+3*x2,x1],{x2+x3<=2,-x2-x3<=-2,x1+x2+x3<=3,-x1-x2-x3<=-2,x1+x2<=2},3);
 

false (22)
 

> step4([x2,-x2],{-x1<=-1,x1<=1,x2<=1},2);
 

false (23)
 

> step4([x1+x2,x1,-3*x1-x2],{x1+x2<=1,-x1-x2<=-1},2);
 

false (24)
 

> step4([x1+x2,x1,-3*x1-x2],{x1+x2<=1,-x1-x2<=-1},2);
 

false (25)
 

> step4([-x1-2*x2+2*x3, 2*x1+3*x2,-x1-x2-2*x3],{x2+x3<=2,-x2-x3<=-2,x1+x2+x3<=3,-x1-x2-x3<=-2,x1+x2<=2},3);
 

false (26)
 

> ##########################################################
 

> # step 5
 

> # We only use the last objective function, that is F[-1]
 

> # We use an auxiliar procedure vert that receives:
 

> # - Sol (one solution given by simplex method);
 

> # - of (objective function);
 

> # - X = set of constraints.
 

> ##########################################################
 

> vert := proc(Sol,of,X)
 

>  local v,S,LFV,LS,i,tv,Min,Max,LL,LV,gaa,ga,VFV,freeVar,Sub,LSub,s,delFreeVar,varSol,varOF1,varOF,VerifySol,aux,NX, mylhs, myrhs;
 mylhs := E -> if type(lhs(E),numeric) then rhs(E) else lhs(E) fi:
 myrhs := E -> if type(rhs(E),numeric) then rhs(E) else lhs(E) fi:
 

>  v := subs(Sol,of);
 varOF1 := t -> op(select(i->not(type(i,numeric)),[op(t)])):
 varOF := of -> map(varOF1,{op(of)}):
 

>  S := solve(of = v,varOF(of));
 freeVar := SS -> {seq(mylhs(i),i=select(i->mylhs(i)=myrhs(i),SS))}:
 varSol := E -> {seq(mylhs(i),i=E)}:
 

>  LFV := freeVar(S) union (varSol(Sol) minus varOF(of));
 

>  tv := (x,s) -> myrhs(op(select(has,s,x))):
 

>  Min := (x,X) -> simplex[minimize](x,X union S,NONNEGATIVE):
 

>  Max := (x,X) -> simplex[maximize](x,X union S,NONNEGATIVE):
 

>  LL := [seq([tv(x,Min(x,X)),tv(x,Max(x,X))],x=LFV)];
 

>  LV := n -> [seq(i[j],j=1..n)]:
 

>  gaa := (n,m,L) -> if m=n then seq(LV(m),i[m]=L[m]) else seq(gaa(n,m+1,L),i[m]=L[m]) fi:
 

>  ga := L -> gaa(nops(L),1,L):
 

>  VFV := {ga(LL)};
 

>  Sub := (C1,C2) -> seq({seq(C2[j]=i[j],j=1..nops(i))},i=C1):
 

>  LSub := Sub(VFV,LFV);
 delFreeVar := SS -> SS minus {seq(i,i=select(i->mylhs(i)=myrhs(i),SS))}:
 NX := X union {seq(i>=0,i=varSol(Sol))}:
 VerifySol := PS -> not(member(false,{seq(evalb(subs(PS,i)),i=NX)})):
 aux := {seq(subs(s,delFreeVar(S)) union s,s={LSub})}:
 

>  return(select(VerifySol,aux));
 

> end proc:
 

> ##############
 

> # examples
 

> ##############
 

> vert({x1 = 1, x2 = 0},x1+x2,{x1+x2>=1,-x1-x2>=-1});
 

{{x2 = 0, x1 = 1}, {x1 = 0, x2 = 1}} (27)
 

> vert({x1 = 0, x2 = 1},x1+x2,{x1+x2>=1,-x1-x2>=-1});
 

{{x2 = 0, x1 = 1}, {x1 = 0, x2 = 1}} (28)
 

> simplex[maximize](x1+x2,{x1<=1,x2<=1,x3<=1},NONNEGATIVE);
 

{x3 = 0, x2 = 1, x1 = 1} (29)
 

> vert({x1 = 1, x2 = 1, x3 = 0},x1+x2,{x1<=1,x2<=1,x3<=1});
 

{{x3 = 0, x2 = 1, x1 = 1}, {x3 = 1, x2 = 1, x1 = 1}} (30)
 

> simplex[maximize](x1+x2+x3,{x1+x2+x3<=1,-x1-x2-x3<=-1},NONNEGATIVE);
 

{x2 = 0, x3 = 0, x1 = 1} (31)
 

> vert({x1 = 1, x2 = 0, x3 = 0},x1+x2+x3,{x1+x2+x3<=1,-x1-x2-x3<=-1});
 

{{x1 = 0, x2 = 0, x3 = 1}, {x2 = 0, x3 = 0, x1 = 1}, {x1 = 0, x3 = 0, x2 = 1}} (32)
 

> simplex[maximize](x1+x2,{x1<=1,x2<=1},NONNEGATIVE);
 

{x2 = 1, x1 = 1} (33)
 

> vert({x1 = 1, x2 = 1},x1+x2,{x1<=1,x2<=1});
 

{{x2 = 1, x1 = 1}} (34)
 

> #####################################
 

> step5 := proc(F,X)
 

>  local SolSM;
 

>  SolSM := simplex[maximize](F[-1],X,NONNEGATIVE);
 

>  return(vert(SolSM,F[-1],X));
 

> end proc:
 

> step5([x1+x2+x3,-x1+x2+x3,x1+x2],{x1<=1,x2<=1,x3<=1});
 

{{x3 = 0, x2 = 1, x1 = 1}, {x3 = 1, x2 = 1, x1 = 1}} (35)
 

> ###########
 

> # step 6
 

> ###########
 

> step6 := proc(F,X)
 

>  local STEP5, of, cstEps, notEfficient, sol, cst, SC;
 

>  STEP5 := step5(F,X);
 

>  of := add(epsilon||i,i=1..nops(F)-1);
 

>  cstEps := seq(epsilon||i>=0,i=1..nops(F)-1);
 

>  notEfficient := true;
 

>  for sol in STEP5 while notEfficient do
 

>    cst := seq(F[i]-epsilon||i=subs(sol,F[i]),i=1..nops(F)-1):  
 

>    SC := {cst} union {cstEps} union X:
 

>    subs(simplex[maximize](of,SC,NONNEGATIVE),of);
 

>    notEfficient := evalb(subs(simplex[maximize](of,SC,NONNEGATIVE),of)<>0);
 

>  end do;
 

>  return(not(notEfficient));
 

> end proc:
 

> step6([x1+x2+x3,-x1+x2+x3,x1+x2],{x1<=1,x2<=1,x3<=1});
 

true (36)
 

> step6([x1-x2,3*x1+x2,x2],{x1<=5,x1+x2<=10});
 

false (37)
 

> step6([x1+x2,x1,-x1-x2],{x1<=1,x2<=1});
 

false (38)
 

> step6([x1+2*x2-x3+3*x4+2*x5+x7,x2+x3+2*x4+3*x5+x6,x1+x3-x4-x6-x7],{x1+2*x2+x3+x4+2*x5+x6+2*x7<=16,-2*x1-x2+x4+2*x5+x7<=16,-x1+x3+2*x5-2*x7<=16,x2+2*x3-x4+x5-2*x6-x7<=1});
 

false (39)
 

> ###########
 

> # step 7
 

> ###########
 

> step7a := proc(F,X,NumVar)
 

>  local b,A,rnk,dif,LP,zero,efficient,v,admissible,vs,AM,sol,of,cstEps,cst,SC,p,LE,myrhs;
 myrhs := E -> if type(rhs(E),numeric) then rhs(E) else lhs(E) fi:
 

>  b := X -> Vector([seq(myrhs(i),i=X)]):
 

>  A := matrixA(X,NumVar);
 

>  rnk := LinearAlgebra[Rank](A);
 

>  dif := NumVar - rnk;
 

>  LP := combinat[choose]([seq(x||i,i=1..NumVar)],dif);
 

>  zero := L -> {seq(i=0,i=L)}:
 

>  LE := NULL;
 

>  v := Vector([seq(x||i,i=1..NumVar)]);
 

>  admissible := sc -> not(member(false,{seq(evalb(myrhs(i)>=0),i=sc)})):
 

>  for p in LP do
 

>    vs := subs({seq(i=0,i=p)},v);
 

>    AM := LinearAlgebra[MatrixVectorMultiply](A,vs);
 

>    sol := solve({seq(AM[i]=b(X)[i],i=1..nops(X))});
   if not(sol = NULL) and admissible(sol) then
     sol := sol union zero(p):
 

>      of := add(epsilon||i,i=1..nops(F)-1);    
 

>      cstEps := seq(epsilon||i>=0,i=1..nops(F)-1);
 

>      cst := seq(F[i]-epsilon||i=subs(sol,F[i]),i=1..nops(F)-1);
 

>      SC := {cst} union {cstEps} union X;
 

>      efficient := evalb(subs(simplex[maximize](of,SC,NONNEGATIVE),of)=0);
     if efficient then LE := LE, sol; fi:
   fi:
 

>  od;
 

>  return([LE]);
 

> end proc:
 

> ##############################################################
 

> # In step7b we change X
 

> # Note: All inequalities must be given in the form Ax <= b
 

> ##############################################################
 

> step7b := proc(F,X,NumVar)
 

>  local TX, SEV, good, sel, mylhs, myrhs;
 mylhs := E -> if type(lhs(E),numeric) then rhs(E) else lhs(E) fi:
 myrhs := E -> if type(rhs(E),numeric) then rhs(E) else lhs(E) fi:
 

>  TX := {seq(mylhs(X[i])+x||(NumVar+i)=myrhs(X[i]),i=1..nops(X))};
 

>  SEV := step7a(F,TX,NumVar+nops(X));
 

>  good := (v,nv) -> member(v,{seq(x||i,i=1..nv)}):
 

>  sel := (es,NumVar) -> select(e->good(mylhs(e),NumVar),es):
 

>  return(map(sel,SEV,NumVar));
 

> end proc:
 

> ###############################
 

> step7 := proc(F,X,NumVar)
 

>  local C, kernel, S7, tv, five, SD, basis, IBK, myrhs;
 myrhs := E -> if type(rhs(E),numeric) then rhs(E) else lhs(E) fi:
 

>  C := matrixA([seq(i=0,i=F[1..-2])],NumVar);
 

>  kernel := LinearAlgebra[NullSpace](C);
 

>  if kernel = {} then
 

>    printf("Objective function %a is nonessential from step 7\n",F[-1]);
 

>  else
 

>    S7 := step7b(F,X,NumVar);
 

>    tv := (x,S) -> myrhs(op(select(has,S,x))):
 

>    five := (S1,S2,NumVar) -> Vector([seq(tv(x||i,S2)-tv(x||i,S1),i=1..NumVar)]):
 

>    SD := [seq(five(S7[1],S7[i],NumVar),i=2..nops(S7))];
 

>    basis := LinearAlgebra[Basis](SD);
 

>    IBK := LinearAlgebra[IntersectionBasis]([basis,kernel]);
   if IBK = {} then
     printf("Objective function %a is nonessential from step 7\n",F[-1]);    
   else
     printf("X_E^%a C X_E^%a from step 7\n",nops(F),nops(F)-1);
   fi:
 fi:
 

> end proc:
 

> step7([x2,x1],{-x1<=-1,x1<=1,x2<=1},2);
 

Objective function x1 is nonessential from step 7
 

> step7([x1+x2+x3,-x1+x2+x3,x1+x2],{x1<=1,x2<=1,x3<=1},3);
 

Objective function x1+x2 is nonessential from step 7
 

> step7([x2,-x2,x1],{x1<=1,x2<=1},2);
 

X_E^3 C X_E^2 from step 7
 

> #######################################
 

> # mm stands for Malinowska Method
 

> #######################################
 

> mm := proc(F,X,NumVar)
 

>  if step1(F) then
 

>    if step6(F,X) then
 

>      step7(F,X,NumVar);
 

>    else
 

>      printf("Objective function %a is essential from step 6\n",F[-1]);
 

>    fi;
 

>  else
 

>    if not(step2(F)) then    
 

>      printf("Objective function %a is nonessential from step 2\n",F[-1]);
 

>    else
 

>      if step3(NumVar,X) then
 

>        printf("Objective function %a is essential from step 3\n",F[-1]);
 

>      else
 

>        if step4(F,X,NumVar) then
 

>          printf("Objective function %a is nonessential from step 4\n",F[-1]);
 

>        else  
 

>          printf("Objective function %a is essential from step 4
                 and X_E^%a C X_E^%a\n",F[-1],nops(F)-1,nops(F));
 

>        fi:
 

>      fi:
 

>    fi:
 

>  fi:
 

> end proc:
 

> mm([x1+x2+x3,-x1+x2+x3,x1+x2],{x1<=1,x2<=1,x3<=1},3);
 

Objective function x1+x2 is nonessential from step 7
 

> mm([x1+3*x2,3*x1,-3*x1-x2,2*x1+x2],{},2);
 

Objective function 2*x1+x2 is nonessential from step 2
 

> mm([x1+3*x2,2*x1+x2,3*x1,-3*x1-x2],{x1<=1,x2<=1},2);
 

Objective function -3*x1-x2 is essential from step 3
 

> mm([x1+3*x2,2*x1+x2,3*x1,-3*x1-x2],{x1+x2<=1,-x1-x2<=-1},2);
 

Objective function -3*x1-x2 is nonessential from step 4
 

> mm([x1-x2,x2,-2*x1+x2],{x1<=5,x1+x2<=10},2);
 

Objective function -2*x1+x2 is essential from step 3
 

> mm([x1-x2,3*x1+x2,x2],{x1=5,x1+x2<=10},2);
 

Objective function x2 is nonessential from step 7
 

> mm([x1-x2,3*x1+x2,x2],{x1<=5,x1+x2<=10},2);
 

Objective function x2 is essential from step 6
 

> ####################
 

> # Main Procedure
 

> ####################
 

> nonessential := proc(F,X)
 local NumVar, y, cs;
 cs := x -> [op(x)][-1]:
 y := sort(map(cs,remove(i->type(i,numeric),map(i->op(i),[seq(op(i),i=F),        seq(op(i),i=X)]))))[-1];
 for NumVar from 1 by 1 while not(evalb(x||NumVar = y) or evalb(-x||NumVar = y)) do od;
 

>  if glm(F,NumVar) then
 

>    printf("Objective function %a is nonessential from GL method\n",F[-1]);
 

>  else
 

>    mm(F,X,NumVar);
 

>  fi:
 

> end proc:
 

> nonessential([x1+x2+x3,-x1+x2+x3,x1+x2],{x1<=1,x2<=1,x3<=1});
 

Objective function x1+x2 is nonessential from step 7
 

> nonessential([x1+3*x2,3*x1,-3*x1-x2,2*x1+x2],{x1+x2<=1});
 

Objective function 2*x1+x2 is nonessential from GL method
 

> nonessential([x1+3*x2,3*x1,-3*x1-x2],{x1+x2<=1});
 

Objective function -3*x1-x2 is essential from step 3
 

> nonessential([x1+3*x2,2*x1+x2,3*x1,-3*x1-x2],{x1<=1,x2<=1});
 

Objective function -3*x1-x2 is essential from step 3
 

> nonessential([x1+3*x2,2*x1+x2,3*x1,-3*x1-x2],{x1+x2<=1,-x1-x2<=-1});
 

Objective function -3*x1-x2 is nonessential from step 4
 

> nonessential([x1+3*x2,2*x1+x2,3*x1],{x1+x2<=1,-x1-x2<=-1});
 

Objective function 3*x1 is nonessential from step 7
 

> nonessential([x1+3*x2,2*x1+x2],{x1+x2<=1,-x1-x2<=-1});
 

Objective function 2*x1+x2 is essential from step 6
 

> nonessential([2*x1+x2,x1+3*x2],{x1+x2<=1,-x1-x2<=-1});
 

Objective function x1+3*x2 is essential from step 6
 

> nonessential([x1-x2,x2,-2*x1+x2],{x1<=5,x1+x2<=10});
 

Objective function -2*x1+x2 is essential from step 3
 

> nonessential([x1-x2,3*x1+x2,x2],{x1=5,x1+x2<=10});
 

Objective function x2 is nonessential from step 7
 

> nonessential([x1-x2,3*x1+x2,x2],{x1<=5,x1+x2<=10});
 

Objective function x2 is essential from step 6
 

> st:= time(): nonessential([x1,x1+x2+x3],{x1<=1,x2<=1,x3<=1}); printf("%a seconds\n",time() - st);
 

X_E^2 C X_E^1 from step 7
 

.187 seconds
 

> st:= time(): nonessential([x1+x2+x3+x4+x5,-x1+x2+x3+x4+x5,-x1-x2+x3+x4+x5,x1+x2],{x1<=1,x2<=1,x3<=1,x4<=1,x5<=1}); printf("%a seconds\n",time() - st);
 

Objective function x1+x2 is nonessential from step 7
 

2.047 seconds
 

> nonessential([x2,x3,x1+x3],{x1<=1,x2<=1,x3<=1});
 

X_E^3 C X_E^2 from step 7
 

> nonessential([x2,x3],{x1<=1,x2<=1,x3<=1});
 

X_E^2 C X_E^1 from step 7
 

> nonessential([x1+x2+x3,x1+x2-x3,x3],{x1<=1,x2<=1,x3<=1});
 

Objective function x3 is nonessential from step 7
 

> nonessential([x2,x3,x2+3*x3],{x1<=1,x2<=1,x3<=1});
 

Objective function x2+3*x3 is nonessential from GL method
 

> nonessential([-x1-2*x2+2*x3,2*x1+3*x2],{x2+x3<=2,-x2-x3<=-2,x1+x2+x3<=3,-x1-x2-x3<=-2,x1+x2<=2});
 

Objective function 2*x1+3*x2 is essential from step 6
 

> nonessential([x1+x2,x1,-3*x1-x2],{x1+x2<=1,-x1-x2<=-1});
 

Objective function -3*x1-x2 is essential from step 4
 

                 and X_E^2 C X_E^3
 

> nonessential([x2,4*x1+x2,-x1+4*x2],{x1+4*x2<=24,-x1-x2<=6,-x2<=-1,3*x1+2*x2<=32});
 

Objective function -x1+4*x2 is nonessential from step 7
 

> nonessential([x2,x1],{-x1<=-1,x1<=1,x2<=1});
 

Objective function x1 is nonessential from step 7
 

> nonessential([x2,-x2],{-x1<=-1,x1<=1,x2<=1});
 

Objective function -x2 is essential from step 4
 

                 and X_E^1 C X_E^2
 

> nonessential([-x2,x2],{-x1<=-1,x1<=1,x2<=1},2);
 

Objective function x2 is essential from step 4
 

                 and X_E^1 C X_E^2
 

> nonessential([x1+x2,x1,-3*x1-x2],{x1+x2<=1,-x1-x2<=-1});
 

Objective function -3*x1-x2 is essential from step 4
 

                 and X_E^2 C X_E^3
 

> nonessential([-x1-2*x2+2*x3,2*x1+3*x2,x1],{x2+x3<=2,-x2-x3<=-2,x1+x2+x3<=3,-x1-x2-x3<=-2,x1+x2<=2});
 

X_E^3 C X_E^2 from step 7
 

> nonessential([-x1-2*x2+2*x3,2*x1+3*x2,-x1-x2-2*x3],{x2+x3<=2,-x2-x3<=-2,x1+x2+x3<=3,-x1-x2-x3<=-2,x1+x2<=2});
 

Objective function -x1-x2-2*x3 is essential from step 4
 

                 and X_E^2 C X_E^3
 

> st:= time(): nonessential([x1+2*x2-x3+3*x4+2*x5+x7,x2+x3+2*x4+3*x5+x6,x1+x3-x4-x6-x7],{x1+2*x2+x3+x4+2*x5+x6+2*x7<=16,-2*x1-x2+x4+2*x5+x7<=16,-x1+x3+2*x5-2*x7<=16,x2+2*x3-x4+x5-2*x6-x7<=1}); printf("%a seconds\n",time() - st);# Zeleny p.244
 

Objective function x1+x3-x4-x6-x7 is essential from step 6
 

.188 seconds
 

> st:= time(): nonessential([x1+3*x2-x3,4*x1+x2+2*x3, -x1+x2+4*x3],{x1+x2+x3<=3,2*x1+2*x2+x3<=4,x1-x2<=0}); printf("%a seconds\n",time() - st);# Zeleny p.273
 

Objective function -x1+x2+4*x3 is essential from step 6
 

.93e-1 seconds
 

> st:= time(): nonessential([3*x1+x2+x3,x1-x2+2*x3, x1+x2],{4*x1+2*x2+3*x3<=10,x1+4*x2+2*x3<=8,x3<=5}); printf("%a seconds\n",time() - st);# Zeleny p.277
 

Objective function x1+x2 is essential from step 6
 

.62e-1 seconds
 

> st:= time(): nonessential([-x3-x4,-x5-x6,-x4-x6],{x1+3*x2<=24,3*x1+x2<=24,x1+4*x2+x3-x4<=40, -x1+4*x2-x3+x4<=-40,4*x1+x2+x5-x6<=40,-4*x1-x2-x5+x6<=-40}); printf("%a seconds\n",time() - st);# Zeleny p.273
 

X_E^3 C X_E^2 from step 7
 

10.062 seconds
 

> nonessential([x1+x2,x1,-3*x1-x2],{x1+x2<=1,-x1-x2<=-1});
 

Objective function -3*x1-x2 is essential from step 4
 

                 and X_E^2 C X_E^3
 

> st:= time(): nonessential([x1+2*x2+3*x3+x4,x2+3*x3+4*x4,-4*x1+2*x2+6*x3,2*x1+x2-x3,10*x1+11*x2+7*x3+6*x4],
{}); printf("%a seconds\n",time() - st);
 

Objective function 10*x1+11*x2+7*x3+6*x4 is nonessential from GL method
 

.47e-1 seconds
 

> st:= time(): nonessential([x1+4*x2-x3+2*x4-3*x5,2*x1-x3-4*x4+x5,-4*x1-8*x2+3*x3+5*x5,-7*x1-4*x2+4*x3+10*x4],
{}); printf("%a seconds\n",time() - st);
 

Objective function -7*x1-4*x2+4*x3+10*x4 is nonessential from GL method
 

.47e-1 seconds
 

> nonessential([x1+x2,x1+x2+x3,-3*x1-3*x2-x3],{x1+x2+x3 <= 1});
 

Objective function -3*x1-3*x2-x3 is essential from step 3
 

>
 

Legal Notice: The copyright for this application is owned by the authors. Neither Maplesoft nor the authors are responsible for any errors contained within and are not liable for any damages resulting from the use of this material.  This application is intended for non-commercial, non-profit use only. Contact the authors for permission if you wish to use this application in for-profit activities.