choco-users Mailing List for choco

There is a bug in choco/integer/constraints/IntLinComb.java
constructor IntLinComb (choco-1_0b002),
which shows up when using the construct scalar with some
coefficients equal to zero.
Here is the correct version :

  /**
    * Constructs the constraint with the specified variables and constant.
    *
    */
   public IntLinComb(choco.integer.IntVar[] lvars, int[] lcoeffs, int c, int linOperator) {
     // create the appropriate data structure
     super(countNonNull(lcoeffs));

     int nbVars = getNbVars(); // vars with non null coeff
     int i = 0;
     int j = 0;
     coeffs = new int[nbVars];
     // fill it up with the coefficients and variables in the right order
     //for (i = 0; i < nbVars; i++) {        <<<<<<<<<<<<<<<< bug
     for (i = 0; i < lvars.length; i++) {
       if (lcoeffs[i] > 0) {
         vars[j] = lvars[i];
         coeffs[j] = lcoeffs[i];
         j++;
       }
     }
     nbPosVars = j;

     //for (i = 0; i < nbVars; i++) {        <<<<<<<<<<<<<<<< bug
     for (i = 0; i < lvars.length; i++) {
       if (lcoeffs[i] < 0) {
         vars[j] = lvars[i];
         coeffs[j] = lcoeffs[i];
         j++;
       }
     }
     op = linOperator;
     cste = c;
   }


Michel

this is our implementation, overriding the default one
we suppose that the method has to return a constraint that is true when the 
starting constraint is false, and vice versa 


 public AbstractConstraint opposite()
  {
    return new BinDisjunction(new BinConjunction(const0, const1.opposite()), 
new BinConjunction(const0.opposite(), const1)); 

    /*
            "a <==> b"
     is equivalent to
            "a ==> b AND b ==> a"
     that is equivalent to
            "(NOT(a) OR b) AND (NOT(b) OR a)"
     with DeMorgan (applied two times) we get
            "(a AND not(b)) OR (b AND not(a))" 

     */ 


  } 


if you want you can send any comment, suggestion, (insult) directly to: 
igorkey _at_ softhome.net 

In the current version of chocosamples (chocosamples-0_9.jar)
the demo 'U2planning.java' was not correctly translated from
the Claire version. A correct and updated version of this demo
can be downloaded here :

http://www.cert.fr/dcsd/cd/MEMBRES/lemaitre/Choco/U2planning.java

Incidentally, I discovered that Problem.feasible may remain null
even if the problem is not feasible (see for example the execution
of u2(3) in the demo). Is it a bug or a feature ?


Michel Lema=EEtre
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D
ONERA/DCSD/CD Centre de Toulouse
2 avenue Edouard Belin - B.P. 4025 - 31055 Toulouse Cedex 4, FRANCE
Tel : +33 (0)5 62 25 26 60    Fax : +33 (0)5 62 25 25 64
Michel . Lemaitre @ cert . fr     http://www.cert.fr/dcsd/cd/lemaitre

Hello,

You are right, that's a bug in the storage of binary tuples when the doma=
in
of the two variables have different sizes and you
give the smallest variable first when you post the constraint (It should =
not
happen on large constraints and the AC constraints are
correct).  I have corrected it on cvs. Let me know if you want the new .j=
ar

Thanks for your help

Hadrien

----- Original Message -----=20
From: "Eric Bensana" <Eri...@ce...>
To: <cho...@li...>
Sent: Monday, July 04, 2005 4:02 PM
Subject: [Choco-users] using feasPairAC constraint


> I m trying to use the feasPairAC constraint to implement
> a simple version of product of two IntVars (V1, V2 val)
>
> Here is a small program
>
> ------
>
> import choco.integer.IntVar;
> import choco.util.*;
> import choco.*;
> import choco.search.*;
>
> import java.lang.Math.*;
> import java.util.List;
> import java.io.*;
>
> public class ex1
> {
>
>  public static  boolean[][] eqProduct(IntVar v1, IntVar v2, int k)
> //implements v1*v2 =3D k
>  {
>   int x1, k1;
>   int x2, k2;
>   int n1 =3D v1.getDomainSize();
>   int n2 =3D v2.getDomainSize();
>   boolean[][] b =3D new boolean[n1][n2];
>
>   k1 =3D 0;
>   for (IntIterator i1 =3D v1.getDomain().getIterator(); i1.hasNext(); k=
1++)
>       {
>        x1 =3D i1.next();
>        k2 =3D 0;
>        for (IntIterator i2 =3D v2.getDomain().getIterator(); i2.hasNext=
();
k2++)
>            {
>             x2 =3D i2.next();
>             b[k1][k2] =3D (x1*x2 =3D=3D k);
> //System.out.println(x1+"("+k1+") * "+x2+"("+k2+") =3D "+b[k1][k2]);
>             }
>        }
>   return b;
>   }
>
>  public static void main(String[] args)
>  {
>   int val =3D Integer.parseInt(args[0]);
>   Problem pb =3D new Problem();
>   IntVar x =3D pb.makeEnumIntVar("X", 0, 2);
>   IntVar y =3D pb.makeEnumIntVar("Y", 0, 4);
>   pb.post(pb.feasPairAC(x, y, eqProduct(x, y, val)));
>
>        if (pb.solveAll())
>           {
>            int n =3D pb.getSolver().getNbSolutions();
>            AbstractSolver s =3D ((AbstractSolver)
> pb.getSolver().getSearchSolver());
>            for (int k =3D 0; k < n; k++)
>                {
>                 Solution sk =3D (Solution) s.solutions.get(k);
>                 int nbVars =3D pb.getNbIntVars();
>                 System.out.println((k+1)+"th solution found");
>                 for (int iv =3D 0; iv < nbVars; iv++)
> System.out.println(pb.getIntVar(iv)+" =3D "+sk.getValue(iv));
>                 }
>            }
>           else
>           {
>            System.out.println("solve failed");
>            }
>   }
>  }
>
>
> --------------------
>
>
>
>
> when I try it for val =3D 1 (java ex1 1)
>
> i got two solutions : the expected one V1 =3D 1 V2 =3D 1
> and V1 =3D 0 V2 =3D 4 ??
>
> what is wrong : is it a bug or do i misuse the feasPairAC constraint ??
>
>
>
>
>
>
> Eric Bensana
>
> ***********************************************************************=
**
> ONERA : Office National d'Etudes et de Recherches Aerospatiales
> DCSD  : Departement Commande des Systemes et Dynamique du vol
>
> CERT  : Centre d'Etudes et de Recherche de Toulouse
> 2 avenue Edouard Belin, BP 4025, 31055 Toulouse Cedex, France
> Tel : +33 (0)5 62 25 29 01, Fax : +33 (0)5 62 25 25 64
>
> M=E9l : Eri...@ce... ou Eri...@on...
> Page Web : http://www.cert.fr/dcsd/cd/MEMBRES/bensana/index.html
> ***********************************************************************=
**
>
>
>
>
> -------------------------------------------------------
> SF.Net email is sponsored by: Discover Easy Linux Migration Strategies
> from IBM. Find simple to follow Roadmaps, straightforward articles,
> informative Webcasts and more! Get everything you need to get up to
> speed, fast. http://ads.osdn.com/?ad_idt77&alloc_id=16492&op=CCk
> _______________________________________________
> Choco-users mailing list
> Cho...@li...
> https://lists.sourceforge.net/lists/listinfo/choco-users
>

I m trying to use the feasPairAC constraint to implement
a simple version of product of two IntVars (V1, V2 val)

Here is a small program

------

import choco.integer.IntVar;
import choco.util.*;
import choco.*;
import choco.search.*;

import java.lang.Math.*;
import java.util.List;
import java.io.*;

public class ex1
{

 public static  boolean[][] eqProduct(IntVar v1, IntVar v2, int k)
//implements v1*v2 =3D k
 {
  int x1, k1;
  int x2, k2;
  int n1 =3D v1.getDomainSize();
  int n2 =3D v2.getDomainSize();
  boolean[][] b =3D new boolean[n1][n2]; =20

  k1 =3D 0;
  for (IntIterator i1 =3D v1.getDomain().getIterator(); i1.hasNext(); k1++)
      {
       x1 =3D i1.next();
       k2 =3D 0;
       for (IntIterator i2 =3D v2.getDomain().getIterator(); i2.hasNext(); =
k2++)
           {
            x2 =3D i2.next();
            b[k1][k2] =3D (x1*x2 =3D=3D k);
//System.out.println(x1+"("+k1+") * "+x2+"("+k2+") =3D "+b[k1][k2]);
            }
       }
  return b;
  }

 public static void main(String[] args)
 {
  int val =3D Integer.parseInt(args[0]);
  Problem pb =3D new Problem();
  IntVar x =3D pb.makeEnumIntVar("X", 0, 2);
  IntVar y =3D pb.makeEnumIntVar("Y", 0, 4);
  pb.post(pb.feasPairAC(x, y, eqProduct(x, y, val)));

       if (pb.solveAll())
          {
           int n =3D pb.getSolver().getNbSolutions();
           AbstractSolver s =3D ((AbstractSolver)=20
pb.getSolver().getSearchSolver());
           for (int k =3D 0; k < n; k++)
               {
                Solution sk =3D (Solution) s.solutions.get(k);
                int nbVars =3D pb.getNbIntVars();
                System.out.println((k+1)+"th solution found");
                for (int iv =3D 0; iv < nbVars; iv++)=20
System.out.println(pb.getIntVar(iv)+" =3D "+sk.getValue(iv));
                }
           }
          else
          {
           System.out.println("solve failed");
           }
  }
 }
=20
=20
--------------------




when I try it for val =3D 1 (java ex1 1)

i got two solutions : the expected one V1 =3D 1 V2 =3D 1
and V1 =3D 0 V2 =3D 4 ??

what is wrong : is it a bug or do i misuse the feasPairAC constraint ??






Eric Bensana

*************************************************************************
ONERA : Office National d'Etudes et de Recherches Aerospatiales
DCSD  : Departement Commande des Systemes et Dynamique du vol

CERT  : Centre d'Etudes et de Recherche de Toulouse
2 avenue Edouard Belin, BP 4025, 31055 Toulouse Cedex, France
Tel : +33 (0)5 62 25 29 01, Fax : +33 (0)5 62 25 25 64

M=E9l : Eri...@ce... ou Eri...@on...
Page Web : http://www.cert.fr/dcsd/cd/MEMBRES/bensana/index.html
*************************************************************************

You are right, the definition of the opposite method is the key to your bug.
However, the piece of code you mention is the default behavior in the
abstract class AbstractConstraint, opposite needs to be redefine at the
constraint level (you can see one example in the BinDisjunction class).
Unfortunately, it has not been written in the Equiv class (the class used
when posting an IfOnlyIf relation). It will be done in the next release of
Choco but in the meantime you can do it and propose it the choco community.

	Best regards, 

		Narendra Jussien


> we have looked into the sources of the libraries, finding 
> that the method "opposite" in class AbstractConstraint is 
> defined in this way: 
> 
> public AbstractConstraint opposite() {
>    throw new UnsupportedOperationException();  } 
> 
> so it's logic that every invocation of the method rises the 
> exception... 
> 
> now come the questions: 
> 
> why is it implemented in this way?
> what should it do? 
> 
> could you give any guidelines to help implementing the method? 
> 
> 
> thanks in advance
> 
> 
> -------------------------------------------------------
> SF.Net email is sponsored by: Discover Easy Linux Migration 
> Strategies from IBM. Find simple to follow Roadmaps, 
> straightforward articles, informative Webcasts and more! Get 
> everything you need to get up to speed, fast. 
> http://ads.osdn.com/?ad_id=7477&alloc_id=16492&op=click
> _______________________________________________
> Choco-users mailing list
> Cho...@li...
> https://lists.sourceforge.net/lists/listinfo/choco-users
> 
> 
> 

we have looked into the sources of the libraries, finding that the method 
"opposite" in class AbstractConstraint is defined in this way: 

public AbstractConstraint opposite() {
   throw new UnsupportedOperationException();
 } 

so it's logic that every invocation of the method rises the exception... 

now come the questions: 

why is it implemented in this way?
what should it do? 

could you give any guidelines to help implementing the method? 


thanks in advance