Menu
▾
▴
Re: [Choco-users] solveAll() bug?
|
From: Guillaume R. <Gui...@em...> - 2006-11-18 02:53:44
|
Hi,
Yes, it seems there are errors if you use sparse domains and constraints=20
defined in extension. We will correct this problem...
Thank you for your help :)
-Guillaume
Varun Jain a =E9crit :
>
> Hi again,
>
> I thought I should give you my test code so that you can run it=20
> yourself. I have included the code at the bottom. Note that the CSP=20
> problem I was experimenting with has changed a bit (however, the=20
> strange behaviour still remains) Heres the new CSP problem:
>
> Variables:
> Variable0, Domain: {4, 2}
> Variable1, Domain: {5, 1, 4}
> Variable2, Domain: {3, 4, 6}
> Variable3, Domain: {1, 2}
> Variable4, Domain: {7, 8, 6, 1}
> Constraints:
> Constraint0, on variables 3 , Allowed tuples:
> 1
> Constraint1, on variables 2, 4 , Allowed tuples:
> 6, 7
> Constraint2, on variables 2 , Allowed tuples:
> 3
> 4
> Constraint3, on variables 4, 1 , Allowed tuples:
> 7, 1
> 8, 1
> 6, 5
> 1, 5
>
> Heres the output of running the program given below:
>
> Choco Solutions
> 2, 1, 3, 1, 8,
> 4, 1, 3, 1, 8,
>
> As you can see, none of the solutions satisfy constraint1. Still choco=20
> returns these solutions.
> Heres my code (BTW, Thanks for taking time out to help me.. I really=20
> appreciate it :-)):
>
> import choco.Problem;
> import choco.Constraint;
> import choco.integer.IntDomainVar;
> import choco.integer.IntVar;
> import java.util.ArrayList;
>
> /**
> * @author Varun Jain (vj)
> * @version $Revision$, $Date$
> * @created Nov 17, 2006
> */
> public class ChocoTest {
> public static void main(String args[]) {
> Problem chocoCSP =3D new Problem();
> IntDomainVar[] vars =3D new IntDomainVar[5];
> Constraint[] cons =3D new Constraint[4];
> //-----Construct all variables
> int id =3D 0;
> vars[id] =3D chocoCSP.makeEnumIntVar("v" + id++, new int[]{4, 2});
> vars[id] =3D chocoCSP.makeEnumIntVar("v" + id++, new int[]{5, 1, 4}=
);
> vars[id] =3D chocoCSP.makeEnumIntVar("v" + id++, new int[]{3, 4, 6}=
);
> vars[id] =3D chocoCSP.makeEnumIntVar("v" + id++, new int[]{1, 2});
> vars[id] =3D chocoCSP.makeEnumIntVar("v" + id++, new int[]{7, 8, 6,=
1});
> id =3D 0;
> ArrayList<int[]> tuples;
>
> //-----Now construct all constraints
> //-----Constraint0
> tuples =3D new ArrayList<int[]>();
> tuples.add(new int[]{1});
> cons[id] =3D chocoCSP.makeTupleFC(new IntVar[]{vars[3]}, tuples, tr=
ue);
> chocoCSP.post(cons[id++]);
>
> //-----Constraint1
> tuples =3D new ArrayList<int[]>();
> tuples.add(new int[]{6, 7});
> cons[id] =3D chocoCSP.makeTupleFC(new IntVar[]{vars[2], vars[4]},=20
> tuples, true);
> chocoCSP.post(cons[id++]);
>
> //-----Constraint2
> tuples =3D new ArrayList<int[]>();
> tuples.add(new int[]{3});
> tuples.add(new int[]{4});
> cons[id] =3D chocoCSP.makeTupleFC(new IntVar[]{vars[2]}, tuples, tr=
ue);
> chocoCSP.post(cons[id++]);
>
> //-----Constraint3
> tuples =3D new ArrayList<int[]>();
> tuples.add(new int[]{7, 1});
> tuples.add(new int[]{8, 1});
> tuples.add(new int[]{6, 5});
> tuples.add(new int[]{1, 5});
> cons[id] =3D chocoCSP.makeTupleFC(new IntVar[]{vars[4], vars[1]},=20
> tuples, true);
> chocoCSP.post(cons[id++]);
>
> //-----Now get solutions
> System.out.println("Choco Solutions");
> if(chocoCSP.solve() =3D=3D Boolean.TRUE) {
> do {
> for(int i =3D 0; i < chocoCSP.getNbIntVars(); i ++) {
> =20
> System.out.print(((IntDomainVar)chocoCSP.getIntVar(i)).getVal() + ", ")=
;
> }
> System.out.println();
> } while(chocoCSP.nextSolution() =3D=3D Boolean.TRUE);
> }
> }
> }
>
>
>
>
>
>
> > Date: Sat, 18 Nov 2006 00:28:23 +0100
> > From: Gui...@em...
> > To: cho...@li...
> > Subject: Re: [Choco-users] solveAll() bug?
> >
> > Hi,
> >
> > This strange behavior is due to the fact that you use SolveAll() befo=
re
> > Solve(). SolveAll() and Solve()+nextSolution()'s loop are equivalents
> > (in other words you search for all the solutions twice), so usually w=
e
> > don't do that :) What do you want to do ?
> >
> > -Guillaume
> >
> > Varun Jain a =E9crit :
> > > Hi,
> > >
> > > Thank you very much for your quick reply. I guess the real question=
I
> > > wanted to ask was that if choco could return results even when the
> > > problem is infeasible. I did my experiment with the following probl=
em:
> > >
> > > ------------------------------------------------
> > > Variables:
> > > Variable0, Domain: {3, 1, 4}
> > > Variable1, Domain: {2, 4, 6}
> > > Variable2, Domain: {2, 1}
> > > Variable3, Domain: {3, 1}
> > > Variable4, Domain: {6, 2, 5}
> > >
> > > Constraints:
> > > Constraint0, on variables 2 , Allowed values:
> > > 2
> > > Constraint1, on variables 2, 4 , Allowed values:
> > > 1, 6
> > > 2, 2
> > > Constraint2, on variables 4, 2 , Allowed values:
> > > 5, 2
> > > Constraint3, on variables 1, 3 , Allowed values:
> > > 2, 3
> > > ------------------------------------------------------
> > >
> > > All the constraints were created using Problem.makeTupleFC(IntVar[]
> > > varList, ArrayList tuples, boolean feasible). For example, the firs=
t
> > > constraint can be created as follows:
> > >
> > > ------------------------------------------
> > > Problem chocoCSP;
> > > /**
> > > * Set up the variables using chocoCSP.makeEnumIntVar()
> > > */
> > > IntVar[] varList =3D new IntVar[1];
> > > varList[0] =3D variables[2];
> > > ArrayList<int[]> tuples =3D new ArrayList<int[]>();
> > > tuples.add(new int[]{2});
> > > chocoCSP.makeTupleFC(varList, tuples, true);
> > > -------------------------------------------------
> > >
> > > To obtain solutions, I did the following:
> > >
> > > -----------------------------------------------
> > > System.out.println("SolveAll says: " + chocoCSP.solveAll());
> > > System.out.println("isFeasible says: " + chocoCSP.isFeasible());
> > > System.out.println("Choco Solutions");
> > > if(chocoCSP.solve() =3D=3D Boolean.TRUE) {
> > > do {
> > > for(int i =3D 0; i < chocoCSP.getNbIntVars(); i ++) {
> > > System.out.print(((IntDomainVar)
> > > chocoCSP.getIntVar(i)).getVal() + ", ");
> > > }
> > > System.out.println();
> > > } while(chocoCSP.nextSolution() =3D=3D Boolean.TRUE);
> > > }
> > > -----------------------------------------------
> > >
> > > Here is the output:
> > >
> > > SolveAll says: true
> > > isFeasible says: false
> > > Choco Solutions
> > > 1,2,2,3,5,
> > > 3,2,2,3,5,
> > > 4,2,2,3,5,
> > >
> > >
> > > Clearly, the solutions do not satisfy all the constraints. For
> > > instance, none of the solutions satisfy Constraint1. Is this expect=
ed
> > > behaviour??
> > >
> > > Thanks again,
> > > -Varun.
> > >
> > >
> > >
> > >
> > >=20
> -----------------------------------------------------------------------=
-
> > > > Date: Fri, 17 Nov 2006 11:31:40 +0100
> > > > From: Gui...@em...
> > > > To: jai...@ho...
> > > > Subject: Re: [Choco-users] solveAll() bug?
> > > >
> > > > Hi,
> > > >
> > > > I am not sure to understand what you try to do but i have some
> > > answers :)
> > > > -SolveAll still return true (it is hardcoded) but you can modify =
the
> > > > function solveAll() in choco.Problem
> > > >
> > > > In choco.Problem:
> > > > public Boolean solveAll() {
> > > > solver.firstSolution =3D false;
> > > > solver.generateSearchSolver(this);
> > > > solver.launch();
> > > > return Boolean.TRUE;
> > > > }
> > > >
> > > > -What kind of error do you have ? How do you implement the
> > > > nextSolution() loop ?
> > > > BTW, if you use nextSolution() to display solutions, you can use
> > > instead:
> > > >
> > > > "Solver.setVerbosity(Solver.SOLUTION);" before to begin to solve
> > > > and "Solver.flushLogs();" to print solutions
> > > >
> > > > else:
> > > >
> > > > if (pb.solve() =3D=3D Boolean.TRUE) {
> > > >
> > > > do {
> > > > //Code
> > > > }
> > > > } while(pb.nextSolution() =3D=3D Boolean.TRUE);
> > > > }
> > > >
> > > >
> > > > I hope it helps you... :)
> > > > -Guillaume
> > > >
> > > > Varun Jain a =E9crit :
> > > > > Hi..
> > > > > Is there any reason why the solveAll() method will return true
> > > even if
> > > > > there is no solution that satisfies all constraints. I was gett=
ing
> > > > > this behaviour so I did a little experiment: I set up a simple
> > > problem
> > > > > and executed the following:
> > > > >
> > > > > Problem chocoCSP;
> > > > > //...............
> > > > > //-----Set up the problem
> > > > > //...............
> > > > > System.out.println("SolveAll says: " + chocoCSP.solveAll());
> > > > > System.out.println("isFeasible says: " + chocoCSP.isFeasible())=
;
> > > > >
> > > > > The following was the output
> > > > >
> > > > > SolveAll says: true
> > > > > isFeasible says: false
> > > > >
> > > > > I thought solveAll() returns false if no solution exists.=20
> Also, for
> > > > > this problem, the solutions I get from the nextSolution()=20
> method do
> > > > > not satisfy all constraints. Any explainations would be really
> > > helpful?
> > > > >
> > > > > Thanks,
> > > > > -Varun.
> > > >
> > >=20
> -----------------------------------------------------------------------=
-
> > > Be one of the first to try Windows Live Mail.
> > >=20
> <http://ideas.live.com/programpage.aspx?versionId=3D5d21c51a-b161-4314-=
9b0e-4911fb2b2e6d>=20
>
> > >
> > >=20
> -----------------------------------------------------------------------=
-
> > >
> > >=20
> -----------------------------------------------------------------------=
--
> > > Take Surveys. Earn Cash. Influence the Future of IT
> > > Join SourceForge.net's Techsay panel and you'll get the chance to=20
> share your
> > > opinions on IT & business topics through brief surveys - and earn c=
ash
> > >=20
> http://www.techsay.com/default.php?page=3Djoin.php&p=3Dsourceforge&CID=3D=
DEVDEV
> > >=20
> -----------------------------------------------------------------------=
-
> > >
> > > _______________________________________________
> > > Choco-users mailing list
> > > Cho...@li...
> > > https://lists.sourceforge.net/lists/listinfo/choco-users
> > >
> >
> >
> >=20
> -----------------------------------------------------------------------=
--
> > Take Surveys. Earn Cash. Influence the Future of IT
> > Join SourceForge.net's Techsay panel and you'll get the chance to=20
> share your
> > opinions on IT & business topics through brief surveys - and earn cas=
h
> >=20
> http://www.techsay.com/default.php?page=3Djoin.php&p=3Dsourceforge&CID=3D=
DEVDEV
> > _______________________________________________
> > Choco-users mailing list
> > Cho...@li...
> > https://lists.sourceforge.net/lists/listinfo/choco-users
>
> -----------------------------------------------------------------------=
-
> Be one of the first to try Windows Live Mail.=20
> <http://ideas.live.com/programpage.aspx?versionId=3D5d21c51a-b161-4314-=
9b0e-4911fb2b2e6d>=20
>
> -----------------------------------------------------------------------=
-
>
> -----------------------------------------------------------------------=
--
> Take Surveys. Earn Cash. Influence the Future of IT
> Join SourceForge.net's Techsay panel and you'll get the chance to share=
your
> opinions on IT & business topics through brief surveys - and earn cash
> http://www.techsay.com/default.php?page=3Djoin.php&p=3Dsourceforge&CID=3D=
DEVDEV
> -----------------------------------------------------------------------=
-
>
> _______________________________________________
> Choco-users mailing list
> Cho...@li...
> https://lists.sourceforge.net/lists/listinfo/choco-users
> =20
|
