Changeset 27e935 in git for IntegerProgramming/IP.lib


Ignore:
Timestamp:
May 11, 2000, 11:04:05 AM (24 years ago)
Author:
Hans Schönemann <hannes@…>
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
54b3568dedfbe0f7886ed616396038a36933c3e3
Parents:
0658d94b02b071f2a019543baea28fe2c95d9226
Message:
*hannes: formatiing


git-svn-id: file:///usr/local/Singular/svn/trunk@4311 2c84dea3-7e68-4137-9b89-c4e89433aadc
File:
1 edited

Legend:

Unmodified
Added
Removed

  • IntegerProgramming/IP.lib

    r0658d9 r27e935  
    1 // $Id: IP.lib,v 1.1.1.1 2000-05-02 12:58:31 Singular Exp $
     1// $Id: IP.lib,v 1.2 2000-05-11 09:04:05 Singular Exp $
    22//
    33// author : Christine Theis
    44//
    55
    6 //version="$Id: IP.lib,v 1.1.1.1 2000-05-02 12:58:31 Singular Exp $";
     6//version="$Id: IP.lib,v 1.2 2000-05-11 09:04:05 Singular Exp $";
    77
    88///////////////////////////////////////////////////////////////////////////////
    99
    1010info="
    11 LIBRARY: IP.lib         PROCEDURES FOR INTEGER PROGRAMMING USING GROEBNER BASIS METHODS   
     11LIBRARY: IP.lib                PROCEDURES FOR INTEGER PROGRAMMING USING GROEBNER BASIS METHODS
    1212
    1313
    1414Let A an integral (mxn)-matrix, b a vector with m integral
    1515coefficients and c a vector with n nonnegative integral coefficients. The
    16 solution of the IP-problem 
    17          
     16solution of the IP-problem
     17
    1818(*)    minimize{ cx | Ax=b, all components of x are nonnegative integers }
    19              
     19
    2020proceeds in two steps:
    21            
     21
    22221. We compute the toric ideal of A and its Groebner basis with respect
    2323   to a term ordering refining the cost function c (such an ordering
    2424   exists because c is nonnegative).
    25            
     25
    26262. We reduce the right hand vector b or an initial solution of the problem
    2727   modulo this ideal.
    28              
     28
    2929For these purposes, we can use seven different algorithms:
    3030The algorithm of Conti/Traverso (ct) can compute an optimal solution
    3131of the IP-problem directly from the right hand vector b. The same is
    3232true for its `positive' variant (pct) which can only be applied if A
    33 and b have nonnegative entries, but should be faster in that case. 
     33and b have nonnegative entries, but should be faster in that case.
    3434All other algorithms need initial solutions of the IP-problem. Except
    3535from the Conti-Traverso algorithm with elimination (ect),
    … …  
    4040
    4141
    42 solve_IP(intmat A, intvec bx, intvec c, string alg);   
     42solve_IP(intmat A, intvec bx, intvec c, string alg);
    4343solve_IP(intmat A, list bx, intvec c, string alg);
    44 solve_IP(intmat A, intvec bx, intvec c, string alg, intvec prsv);       
     44solve_IP(intmat A, intvec bx, intvec c, string alg, intvec prsv);
    4545solve_IP(intmat A, list bx, intvec c, string alg, intvec prsv);
    46        
    47         procedures for solving the IP-problem (*)
    48     They return the solution(s) of the given problem(s) or the 
     46
     47        procedures for solving the IP-problem (*)
     48    They return the solution(s) of the given problem(s) or the
    4949    message `not solvable'.
    5050    `alg' may be one of the algorithm abbreviations as above.
    51     If `alg' is chosen to be `ct' or `pct', bx is read as the right 
     51    If `alg' is chosen to be `ct' or `pct', bx is read as the right
    5252    hand vector b of the system Ax=b. b should then be an intvec of
    5353    size m where m is the number of rows of A. Furthermore, bx and
    54     A should be nonnegative if `pct' is used. 
    55         If `alg' is chosen to be `ect',`pt',`blr',`hs' or `du', bx is
    56         read as an initial solution x of the system Ax=b. bx should
    57         then be a nonnegative intvec of size n where n is the number
    58         of columns of A.
     54    A should be nonnegative if `pct' is used.
     55        If `alg' is chosen to be `ect',`pt',`blr',`hs' or `du', bx is
     56        read as an initial solution x of the system Ax=b. bx should
     57        then be a nonnegative intvec of size n where n is the number
     58        of columns of A.
    5959    If `alg' is chosen to be `blr' or `hs', the algorithm needs a
    6060    vector with positive coefficcients in the row space of A. If
    6161    no row of A contains only positive entries, one must use the
    6262    versions of solve_IP which take such a vector prsv as
    63     argument. 
    64         solve_IP may also be called with a list bx of intvecs instead
    65         of a single intvec.       
    66    
    67                          
     63    argument.
     64        solve_IP may also be called with a list bx of intvecs instead
     65        of a single intvec.
     66
     67
    6868";
    6969
    7070///////////////////////////////////////////////////////////////////////////////
    7171
    72 
    73 
    7472static proc solve_IP_1(intmat A, intvec bx, intvec c, string alg)
    75 {       
     73{
    7674  intvec v;
    7775  // to be returned
    7876
    7977  // check arguments as far as necessary
    80   // other inconsistencies are detected by the external program 
     78  // other inconsistencies are detected by the external program
    8179  if(size(c)!=ncols(A))
    8280  {
    8381    "ERROR: number of matrix columns must equal size of cost vector";
    8482    return(v);
    85   }     
     83  }
    8684
    8785  // create first temporary file with that the external program is
    88   // called 
     86  // called
    8987
    9088  int process=system("pid");
    91   string matrixfile="temp_MATRIX"+string(process);     
     89  string matrixfile="temp_MATRIX"+string(process);
    9290  link MATRIX=":w "+matrixfile;
    9391  open(MATRIX);
    … …  
    107105    }
    108106  }
    109  
     107
    110108  // search for positive row space vector, if required by the
    111   // algorithm   
     109  // algorithm
    112110  int found=0;
    113111  if((alg=="blr") || (alg=="hs"))
    114   { 
     112  {
    115113    for(i=1;i<=nrows(A);i++)
    116114    {
    … …  
    130128    if(found==0)
    131129    {
    132       "ERROR: algorithm needs positive vector in the row space of the matrix";     
     130      "ERROR: algorithm needs positive vector in the row space of the matrix";
    133131      close(MATRIX);
    134132      system("sh","rm -f "+matrixfile);
    135133      return(v);
    136     } 
     134    }
    137135    write(MATRIX,"positive row space vector:");
    138136    for(j=1;j<=ncols(A);j++)
    139     { 
     137    {
    140138      write(MATRIX,A[found,j]);
    141139    }
    … …  
    145143  // create second temporary file for the external program
    146144
    147   string problemfile="temp_PROBLEM"+string(process);   
     145  string problemfile="temp_PROBLEM"+string(process);
    148146  link PROBLEM=":w "+problemfile;
    149147  open(PROBLEM);
    150148
    151   write(PROBLEM,"PROBLEM","vector size:",size(bx),"number of instances:",1,"right hand or initial solution vectors:"); 
     149  write(PROBLEM,"PROBLEM","vector size:",size(bx),"number of instances:",1,"right hand or initial solution vectors:");
    152150  for(i=1;i<=size(bx);i++)
    153151  {
    … …  
    165163  string s;
    166164  if(alg=="ct" || alg=="pct")
    167   { 
     165  {
    168166    pos=find(solution,"NO");
    169167    if(pos!=0)
    … …  
    193191  }
    194192  else
    195   { 
     193  {
    196194    pos=find(solution,"optimal");
    197195    pos=find(solution,":",pos);
    … …  
    212210    }
    213211  }
    214      
     212
    215213  // delete all created files
    216214  dummy=system("sh","rm -f "+matrixfile);
    … …  
    222220}
    223221
    224 
    225 
    226222static proc solve_IP_2(intmat A, list bx, intvec c, string alg)
    227 {       
     223{
    228224  list l;;
    229225  // to be returned
    230226
    231227  // check arguments as far as necessary
    232   // other inconsistencies are detected by the external program 
     228  // other inconsistencies are detected by the external program
    233229  if(size(c)!=ncols(A))
    234230  {
    235231    "ERROR: number of matrix columns must equal size of cost vector";
    236232    return(l);
    237   }     
     233  }
    238234
    239235  int k;
    … …  
    248244
    249245  // create first temporary file with that the external program is
    250   // called 
     246  // called
    251247
    252248  int process=system("pid");
    253   string matrixfile="temp_MATRIX"+string(process);     
     249  string matrixfile="temp_MATRIX"+string(process);
    254250  link MATRIX=":w "+matrixfile;
    255251  open(MATRIX);
    … …  
    269265    }
    270266  }
    271  
     267
    272268  // search for positive row space vector, if required by the
    273   // algorithm   
     269  // algorithm
    274270  int found=0;
    275271  if((alg=="blr") || (alg=="hs"))
    276   { 
     272  {
    277273    for(i=1;i<=nrows(A);i++)
    278274    {
    … …  
    292288    if(found==0)
    293289    {
    294       "ERROR: algorithm needs positive vector in the row space of the matrix";     
     290      "ERROR: algorithm needs positive vector in the row space of the matrix";
    295291      close(MATRIX);
    296292      system("sh","rm -f "+matrixfile);
    297293      return(l);
    298     } 
     294    }
    299295    write(MATRIX,"positive row space vector:");
    300296    for(j=1;j<=ncols(A);j++)
    301     { 
     297    {
    302298      write(MATRIX,A[found,j]);
    303299    }
    … …  
    307303  // create second temporary file for the external program
    308304
    309   string problemfile="temp_PROBLEM"+string(process);   
     305  string problemfile="temp_PROBLEM"+string(process);
    310306  link PROBLEM=":w "+problemfile;
    311307  open(PROBLEM);
    312308
    313   write(PROBLEM,"PROBLEM","vector size:",size(bx[1]),"number of instances:",size(bx),"right hand or initial solution vectors:"); 
     309  write(PROBLEM,"PROBLEM","vector size:",size(bx[1]),"number of instances:",size(bx),"right hand or initial solution vectors:");
    314310  for(k=1;k<=size(bx);k++)
    315311  {
    … …  
    331327  string s;
    332328  if(alg=="ct" || alg=="pct")
    333   { 
     329  {
    334330    pos=1;
    335331    for(k=1;k<=size(bx);k++)
    336     {     
     332    {
    337333      pos1=find(solution,"NO",pos);
    338334      pos2=find(solution,"YES",pos);
    … …  
    359355            s=s+solution[pos];
    360356            pos++;
    361           } 
     357          }
    362358          execute("v[j]="+s+";");
    363359        }
    … …  
    367363  }
    368364  else
    369   { 
     365  {
    370366    pos=1;
    371367    for(k=1;k<=size(bx);k++)
    … …  
    385381          s=s+solution[pos];
    386382          pos++;
    387         } 
     383        }
    388384        execute("v[j]="+s+";");
    389385      }
    … …  
    391387    }
    392388  }
    393      
     389
    394390  // delete all created files
    395391  dummy=system("sh","rm -f "+matrixfile);
    … …  
    401397}
    402398
    403 
    404 
    405399static proc solve_IP_3(intmat A, intvec bx, intvec c, string alg, intvec prsv)
    406 {       
     400{
    407401  intvec v;
    408402  // to be returned
    409403
    410404  // check arguments as far as necessary
    411   // other inconsistencies are detected by the external program 
     405  // other inconsistencies are detected by the external program
    412406  if(size(c)!=ncols(A))
    413407  {
    414408    "ERROR: number of matrix columns must equal size of cost vector";
    415409    return(v);
    416   }     
     410  }
    417411
    418412  if(size(prsv)!=ncols(A))
    … …  
    420414    "ERROR: number of matrix columns must equal size of positive row space vector";
    421415    return(v);
    422   }     
     416  }
    423417
    424418  // create first temporary file with that the external program is
    425   // called 
     419  // called
    426420
    427421  int process=system("pid");
    428   string matrixfile="temp_MATRIX"+string(process);     
     422  string matrixfile="temp_MATRIX"+string(process);
    429423  link MATRIX=":w "+matrixfile;
    430424  open(MATRIX);
    … …  
    444438    }
    445439  }
    446  
     440
    447441  // enter positive row space vector, if required by the algorithm
    448442  if((alg=="blr") || (alg=="hs"))
    449   { 
     443  {
    450444    write(MATRIX,"positive row space vector:");
    451445    for(j=1;j<=ncols(A);j++)
    452     { 
     446    {
    453447      write(MATRIX,prsv[j]);
    454448    }
    … …  
    458452  // create second temporary file for the external program
    459453
    460   string problemfile="temp_PROBLEM"+string(process);   
     454  string problemfile="temp_PROBLEM"+string(process);
    461455  link PROBLEM=":w "+problemfile;
    462456  open(PROBLEM);
    463457
    464   write(PROBLEM,"PROBLEM","vector size:",size(bx),"number of instances:",1,"right hand or initial solution vectors:"); 
     458  write(PROBLEM,"PROBLEM","vector size:",size(bx),"number of instances:",1,"right hand or initial solution vectors:");
    465459  for(i=1;i<=size(bx);i++)
    466460  {
    … …  
    478472  string s;
    479473  if(alg=="ct" || alg=="pct")
    480   { 
     474  {
    481475    pos=find(solution,"NO");
    482476    if(pos!=0)
    … …  
    500494          s=s+solution[pos];
    501495          pos++;
    502         } 
     496        }
    503497        execute("v[j]="+s+";");
    504498      }
    … …  
    506500  }
    507501  else
    508   { 
     502  {
    509503    pos=find(solution,"optimal");
    510504    pos=find(solution,":",pos);
    … …  
    521515        s=s+solution[pos];
    522516        pos++;
    523       } 
     517      }
    524518      execute("v[j]="+s+";");
    525519    }
    526520  }
    527      
     521
    528522  // delete all created files
    529523  dummy=system("sh","rm -f "+matrixfile);
    … …  
    535529}
    536530
    537 
    538 
    539531static proc solve_IP_4(intmat A, list bx, intvec c, string alg, intvec prsv)
    540 {       
     532{
    541533  list l;
    542534  // to be returned
    543535
    544536  // check arguments as far as necessary
    545   // other inconsistencies are detected by the external program 
     537  // other inconsistencies are detected by the external program
    546538  if(size(c)!=ncols(A))
    547539  {
    548540    "ERROR: number of matrix columns must equal size of cost vector";
    549541    return(l);
    550   }     
     542  }
    551543
    552544  if(size(prsv)!=ncols(A))
    … …  
    554546    "ERROR: number of matrix columns must equal size of positive row space vector";
    555547    return(v);
    556   }     
     548  }
    557549
    558550  int k;
    … …  
    567559
    568560  // create first temporary file with that the external program is
    569   // called 
     561  // called
    570562
    571563  int process=system("pid");
    572   string matrixfile="temp_MATRIX"+string(process);     
     564  string matrixfile="temp_MATRIX"+string(process);
    573565  link MATRIX=":w "+matrixfile;
    574566  open(MATRIX);
    … …  
    588580    }
    589581  }
    590  
     582
    591583  // enter positive row space vector if required by the algorithm
    592584  if((alg=="blr") || (alg=="hs"))
    593   { 
     585  {
    594586    write(MATRIX,"positive row space vector:");
    595587    for(j=1;j<=ncols(A);j++)
    596     { 
     588    {
    597589      write(MATRIX,prsv[j]);
    598590    }
    … …  
    602594  // create second temporary file for the external program
    603595
    604   string problemfile="temp_PROBLEM"+string(process);   
     596  string problemfile="temp_PROBLEM"+string(process);
    605597  link PROBLEM=":w "+problemfile;
    606598  open(PROBLEM);
    607599
    608   write(PROBLEM,"PROBLEM","vector size:",size(bx[1]),"number of instances:",size(bx),"right hand or initial solution vectors:"); 
     600  write(PROBLEM,"PROBLEM","vector size:",size(bx[1]),"number of instances:",size(bx),"right hand or initial solution vectors:");
    609601  for(k=1;k<=size(bx);k++)
    610602  {
    … …  
    626618  string s;
    627619  if(alg=="ct" || alg=="pct")
    628   { 
     620  {
    629621    pos=1;
    630622    for(k=1;k<=size(bx);k++)
    631     {     
     623    {
    632624      pos1=find(solution,"NO",pos);
    633625      pos2=find(solution,"YES",pos);
    … …  
    654646            s=s+solution[pos];
    655647            pos++;
    656           } 
     648          }
    657649          execute("v[j]="+s+";");
    658650        }
    … …  
    662654  }
    663655  else
    664   { 
     656  {
    665657    pos=1;
    666658    for(k=1;k<=size(bx);k++)
    … …  
    686678    }
    687679  }
    688      
     680
    689681  // delete all created files
    690682  dummy=system("sh","rm -f "+matrixfile);
    … …  
    696688}
    697689
    698 
    699 
    700 
    701 
    702 
    703690proc solve_IP
    704 "USAGE:   
     691"USAGE:
    705692solve_IP(A,bx,c,alg);       A intmat, bx intvec, c intvec, alg string
    706 solve_IP(A,bx,c,alg);       A intmat, bx list of intvec, c intvec, alg string 
     693solve_IP(A,bx,c,alg);       A intmat, bx list of intvec, c intvec, alg string
    707694solve_IP(A,bx,c,alg,prsv);  A intmat, bx intvec, c intvec, alg string,
    708                             prsv intvec 
     695                            prsv intvec
    709696solve_IP(A,bx,c,alg,prsv);  A intmat, bx list of intvec, c intvec, alg string,
    710                             prsv intvec 
    711 RETURN:  solution of the associated integer programming problem as explained 
     697                            prsv intvec
     698RETURN:  solution of the associated integer programming problem as explained
    712699         in IP.lib
    713          return type = type of bx 
     700         return type = type of bx
    714701EXAMPLE: example solve_IP;  shows an example"
    715702{
    … …  
    737724  }
    738725}
    739 
    740 
    741 
    742726example
    743727{
    744 "EXAMPLE"; echo=2;
    745 
    746 // call with single right hand vector
    747 intmat A[2][3]=1,1,0,0,1,1;
    748 A;
    749 intvec b1=1,1;
    750 b1;
    751 intvec c=2,2,1;
    752 c;
    753 intvec solution_vector=solve_IP(A,b1,c,"pct");
    754 solution_vector;
    755  
    756 // call with list of right hand vectors
    757 intvec b2=-1,1;
    758 list l=b1,b2;
    759 l;
    760 list solution_list=solve_IP(A,l,c,"ct");
    761 solution_list;                 
    762 
    763 // call with single initial solution vector
    764 A=2,1,-1,-1,1,2;
    765 A;
    766 b1=3,4,5;
    767 solution_vector=solve_IP(A,b1,c,"du");
    768 
    769 // call with single initial solution vector and algorithm needing a positive
    770 // row space vector
    771 solution_vector=solve_IP(A,b1,c,"hs");
    772 
    773 // call with single initial solution vector and positive row space vector
    774 intvec prsv=1,2,1;
    775 prsv;
    776 solution_vector=solve_IP(A,b1,c,"hs",prsv);
    777 solution_vector;
    778  
    779 // call with list of initial solution vectors and positive row space vector
    780 b2=7,8,0;
    781 l=b1,b2;
    782 l;
    783 solution_list=solve_IP(A,l,c,"blr",prsv);
    784 solution_list;
     728  "EXAMPLE"; echo=2;
     729
     730  // call with single right hand vector
     731  intmat A[2][3]=1,1,0,0,1,1;
     732  A;
     733  intvec b1=1,1;
     734  b1;
     735  intvec c=2,2,1;
     736  c;
     737  intvec solution_vector=solve_IP(A,b1,c,"pct");
     738  solution_vector;
     739
     740  // call with list of right hand vectors
     741  intvec b2=-1,1;
     742  list l=b1,b2;
     743  l;
     744  list solution_list=solve_IP(A,l,c,"ct");
     745  solution_list;
     746
     747  // call with single initial solution vector
     748  A=2,1,-1,-1,1,2;
     749  A;
     750  b1=3,4,5;
     751  solution_vector=solve_IP(A,b1,c,"du");
     752
     753  // call with single initial solution vector and algorithm needing a positive
     754  // row space vector
     755  solution_vector=solve_IP(A,b1,c,"hs");
     756
     757  // call with single initial solution vector and positive row space vector
     758  intvec prsv=1,2,1;
     759  prsv;
     760  solution_vector=solve_IP(A,b1,c,"hs",prsv);
     761  solution_vector;
     762
     763  // call with list of initial solution vectors and positive row space vector
     764  b2=7,8,0;
     765  l=b1,b2;
     766  l;
     767  solution_list=solve_IP(A,l,c,"blr",prsv);
     768  solution_list;
    785769}
    786 
    787 
    788 
Note: See TracChangeset for help on using the changeset viewer.