Decision Optimization

Decision Optimization

Delivers prescriptive analytics capabilities and decision intelligence to improve decision-making.

 View Only
  • 1.  File type conversion from dimacs-cnf to MPS

    Posted Sat July 28, 2018 08:19 AM

    Originally posted by: srinit34


    Hi

    There are several cnf format files on SAT library  http://www.cs.ubc.ca/~hoos/SATLIB/benchm.html

    It seems they may be converted into an MPS format using CPLEX API CPXNETwriteprob().

    Is there a Java API ? Any pointers on how to do this ?

    https://fairmut3x.wordpress.com/2011/07/29/cnf-conjunctive-normal-form-dimacs-format-explained/

    I am attaching a sample file.

     


    #CPLEXOptimizers
    #DecisionOptimization


  • 2.  Re: File type conversion from dimacs-cnf to MPS

    Posted Sun July 29, 2018 04:56 PM

    Hi,

    if you remove the header and use uf250.txt then you could write in OPL

     

        tuple t
        {
        int a;
        int b;
        int c;
        int d;
        }

        {t} s={};

        execute
        {
        var f=new IloOplInputFile("uf250.txt");
        while (!f.eof)
        {
        var str=f.readline();
        //writeln(str);
        var ar=str.split(" ");
        if (ar.length==4) s.add(ar[0],ar[1],ar[2],ar[3]);
        }
        f.close();
        }

        execute
        {
        writeln(s);
        }
        
        assert forall(i in s) i.d==0; // No OR
        
    int nbX=max(i in s) ftoi(maxl(abs(i.a),abs(i.b),abs(i.c))) ;  

    execute
    {
    writeln("nbX = ",nbX);
    writeln("nbConstraints = ",s.size);
    }

    dvar boolean x[1..nbX];

    subject to
    {

    forall(i in s)
    (i.a>=0)*x[ftoi(abs(i.a))]+(i.a<=0)*(1-x[ftoi(abs(i.a))])+
    (i.b>=0)*x[ftoi(abs(i.b))]+(i.b<=0)*(1-x[ftoi(abs(i.b))])+
    (i.c>=0)*x[ftoi(abs(i.c))]+(i.c<=0)*(1-x[ftoi(abs(i.c))])
    >=1;
    }

     

    that will generate a cnfreader.mps and also give you the result

     

    x = [0
             0 0 1 1 1 1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 1 1 0 1 1 0 0
             1 1 1 0 1 1 1 0 1 1 1 0 1 1 0 0 0 1 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1
             0 0 0 1 0 0 1 0 1 0 0 1 1 1 1 0 1 0 1 0 1 1 0 1 1 0 0 0 0 0 1 0 1
             0 1 0 1 1 1 1 1 1 0 1 1 1 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 1 1
             1 1 1 1 1 1 1 0 1 0 1 1 0 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 1 1 1 1 1
             0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1
             1 0 1 0 0 1 1 1 0 1 0 1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 0 0 1 0 1 1 0
             0 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 0 0];

     

    NB: if in the .mod you write using CP; then you will call CP Optimizer : https://www.ibm.com/analytics/cplex-cp-optimizer

     

    regards

     


    #CPLEXOptimizers
    #DecisionOptimization


  • 3.  Re: File type conversion from dimacs-cnf to MPS

    Posted Mon July 30, 2018 01:44 AM

    If you look up the spec for CNF files then you will find that this is a pretty simple text format. Here is an (untested) Java code that parses a CNF file and translates it to a CPLEX model or LP file.

    import ilog.cplex.IloCplex;
    import ilog.concert.IloException;
    import ilog.concert.IloIntVar;
    import ilog.concert.IloLinearNumExpr;
    
    import java.io.IOException;
    
    import java.nio.charset.Charset;
    import java.nio.file.Files;
    import java.nio.file.Paths;
    
    public final class ReadCnf {
       public static void main(String[] args) throws IloException, IOException {
          IloCplex cplex = new IloCplex();
          try {
             int vars = -1, clauses = -1;
             IloIntVar[] x = null;
             for (String line : Files.readAllLines(Paths.get(args[0]), Charset.forName("utf-8"))) {
                if ( line.startsWith("c") )
                   // ignore comments
                   continue;
                else if ( line.startsWith("p") ) {
                   // parse header
                   if ( vars >= 0 )
                      throw new IOException("Multiple headers");
                   String[] fields = line.split("\\s+");
                   if ( fields.length != 4 )
                      throw new IOException("Invalid header");
                   if ( !fields[1].equals("cnf") )
                      throw new IOException("Invalid format");
                   vars = Integer.parseInt(fields[2]);
                   clauses = Integer.parseInt(fields[3]);
                   x = cplex.boolVarArray(vars);
                   for (int i = 0; i < vars; ++i)
                      x[i].setName("x" + (i + 1));
                }
                else if ( line.startsWith("%") ) {
                   // Not sure what that means, just stop
                   break;
                }
                else {
                   // parse a clause
                   // note that in the file variables indices are 1-based while
                   // here they are 0-based.
                   IloLinearNumExpr expr = cplex.linearNumExpr();
                   double rhs = 1.0;
                   for (final String s : line.trim().split("\\s+")) {
                      int var = Integer.parseInt(s);
                      if ( var > 0 ) {
                         expr.addTerm(1.0, x[var - 1]);
                      }
                      else if ( var < 0 ) {
                         // complemented variable, add (1-x) to the left-hand
                         // side
                         expr.addTerm(-1, x[-var - 1]);
                         rhs -= 1.0;
                      }
                      else {
                         // 0 terminates a clause
                         break;
                      }
                   }
                   cplex.addGe(expr, rhs);
                }
             }
             cplex.exportModel(args[1]);
             //cplex.solve();
          }
          finally {
             cplex.end();
          }
       }
    }
    

    Note that this is more flexible than what Alex suggested since it directly consumes the CNF file (including comments and header) and also is not limited to clauses of length 3.


    #CPLEXOptimizers
    #DecisionOptimization


  • 4.  Re: File type conversion from dimacs-cnf to MPS

    Posted Mon July 30, 2018 02:17 PM

    Originally posted by: srinit34


    thank you for the sample code.

    I was looking for a ready-made parser and converter. It appears that none exists.

    Useful tutorial at https://fairmut3x.wordpress.com/2011/07/29/cnf-conjunctive-normal-form-dimacs-format-explained/


    #CPLEXOptimizers
    #DecisionOptimization


  • 5.  Re: File type conversion from dimacs-cnf to MPS

    Posted Wed August 01, 2018 03:42 AM

    This tutorial is exactly what I used to base my parser on. And I would say that my code is even more than a ready-made parser and converter :-) Modulo bugs, of course.


    #CPLEXOptimizers
    #DecisionOptimization


  • 6.  Re: File type conversion from dimacs-cnf to MPS

    Posted Wed August 01, 2018 03:59 AM

    Then let me turn mine into something more generic that will work with comments and any size.

    Plus it could work with CPO!

    //using CP;

    tuple t
    {
    int line;
    int value;
    }

    {t} s;

     


    execute
        {
        var line=0;    
        
        
        var f=new IloOplInputFile("uf250-01.cnf");
        
        while (!f.eof)
        {
        var str=f.readline();
        
        var firstchar=str.substring(0,1);
        if (firstchar=="c") continue;
        if (firstchar=="p") continue;
        if (firstchar=="%") continue;
        
        line++;
        
        writeln(str);
        var ar=str.split(" ");
        
        if (0==ar.length) continue;
        
        
        for(var i=0;i<ar.length-1;i++) if (ar[i]!="") s.add(line,ar[i]);
        if (ar[ar.length-1]!=0) fail();
        }
        f.close();
        }
        
        
    int nbConstraints = max(i in s) i.line;
    {int} trueVariables[i in 1..nbConstraints]={j.value | j in s : j.line==i && j.value>0};
    {int} falseVariables[i in 1..nbConstraints]={-j.value | j in s : j.line==i && j .value <0};

    int nbVariables=max(i in 1..nbConstraints)
        maxl(max(j in trueVariables[i]) j,max(j in falseVariables[i])j);
        
    dvar boolean x[1..nbVariables];

    subject to
    {    
    forall(i in 1..nbConstraints)
    1<=sum(j in trueVariables[i]) x[j]+sum(j in falseVariables[i]) (1-x[j]);

    // If you want to use Constraint Programming
    //or(j in trueVariables[i]) (x[j]==1)
    //||
    //or(j in falseVariables[i]) (x[j]==0);
    }    

    main
    {
    thisOplModel.generate();
    cplex.exportModel("cnf.mps");
    cplex.solve();
    }
     

    regards


    #CPLEXOptimizers
    #DecisionOptimization