0

I would like to add starting values to the Z3 solver for some of my variables, which were previously found by some heuristic. I'd hope for a faster convergence with them. I don't want to add them as constraints, I just want to provide an initial starting point, a help so to say. Like a MIP start for ILP.

Is this possible for Z3, and if so how? I haven't been able to find anything on the topic. (And btw I'm using the .NET API)

Thanks!

var myVar = ctx.MkIntConst("myVar");
// myVar.Start(5); or something like that

Code to which I want to apply the start:

using (var ctx = new Context())
        {
            using (var slv = ctx.MkSolver())
            //using (var slv = ctx.MkTactic("lia").Solver)
            {
                var srcArticlePos = new IntExpr[_articles.Count(), 3];
                for (int i = 0; i < _articles.Count(); i++)
                {
                    srcArticlePos[i, 0] = ctx.MkIntConst($"x[{i}]");
                    srcArticlePos[i, 1] = ctx.MkIntConst($"y[{i}]");
                    srcArticlePos[i, 2] = ctx.MkIntConst($"z[{i}]");

                    var a = _articles.ElementAt(i);
                    slv.Assert(srcArticlePos[i, 0] >= 0 & srcArticlePos[i, 0] < (int)(_box.Width - a.Width+1));
                    slv.Assert(srcArticlePos[i, 1] >= 0 & srcArticlePos[i, 1] < (int)(_box.Height - a.Height+1));
                    slv.Assert(srcArticlePos[i, 2] >= 0 & srcArticlePos[i, 2] < (int)(_box.Length - a.Length+1));
                }

                // Heuristic start
                /*var lbp = new LAFFBinPacker();
                var laffFits = lbp.FitsInABox(_articles, _box);
                // get pack positions and clone
                var pos = lbp.packedArticlePositions.ToDictionary(d => d.Key, d => d.Value.ToList());
                // mip start
                for (int i = 0; i < _articles.Count(); i++)
                {
                    var a = _articles.ElementAt(i);
                    // take the first available position for this item and remove it from the list
                    if (pos.ContainsKey(a) && pos[a].Count > 0)
                    {
                        var p = pos[a][0];
                        pos[a].Remove(p);
                        var t = srcArticlePos[i, 0];
                        var test = srcArticlePos[i, 0].Args[0].;
                        srcArticlePos[i, 0].Args[0].
                        srcArticlePos[i, 0].Update(new Microsoft.Z3.IntExpr[] { new IntExpr(0) });
                        //varArticlePos[i, 0].Set(GRB.DoubleAttr.Start, p[1]);
                        //varArticlePos[i, 1].Set(GRB.DoubleAttr.Start, p[2]);
                        //varArticlePos[i, 2].Set(GRB.DoubleAttr.Start, p[0]);
                    }
                }*/

                for (int i = 0; i < _articles.Count(); i++)
                {
                    var a1 = _articles.ElementAt(i);
                    var sX1 = srcArticlePos[i, 0];
                    var eX1 = srcArticlePos[i, 0] + (int)(a1.Width-1);
                    var sY1 = srcArticlePos[i, 1];
                    var eY1 = srcArticlePos[i, 1] + (int)(a1.Height-1);
                    var sZ1 = srcArticlePos[i, 2];
                    var eZ1 = srcArticlePos[i, 2] + (int)(a1.Length-1);
                    for (int j = i + 1; j < _articles.Count(); j++)
                    {
                        var a2 = _articles.ElementAt(j);
                        var sX2 = srcArticlePos[j, 0];
                        var eX2 = srcArticlePos[j, 0] + (int)(a2.Width-1);
                        var sY2 = srcArticlePos[j, 1];
                        var eY2 = srcArticlePos[j, 1] + (int)(a2.Height-1);
                        var sZ2 = srcArticlePos[j, 2];
                        var eZ2 = srcArticlePos[j, 2] + (int)(a2.Length-1);

                        slv.Assert(sX1 > eX2 | eX1 < sX2 | sY1 > eY2 | eY1 < sY2 | sZ1 > eZ2 | eZ1 < sZ2);

                        // no article with lower weight class must be above a higher one
                        if (a2.WeightClass > a1.WeightClass)
                            slv.Assert(sY1 < sY2);
                        else if (a2.WeightClass < a1.WeightClass)
                            slv.Assert(sY1 > sY2);
                    }
                }



                switch (slv.Check())
                {
                    case Status.SATISFIABLE:
                        return true;
                    case Status.UNSATISFIABLE:
                        return false;
                    default:
                        throw new Exception();
                }
            }
        }
Doidel
  • 319
  • 8
  • 23
  • what kind of problem are you trying to solve? in what sense do you want to help *z3*? Do values correspond to a known satisfiable solution? Are you doing optimization? – Patrick Trentin Jun 08 '16 at 09:05
  • You're saying whether it's possible depends on the case? I slv.Check() whether a 3d bin packing formulation is feasible / satisfiable. The start values correspond to an infeasible solution, but no constraints are violated. I'll edit the question to add the relevant code, maybe this helps then. – Doidel Jun 08 '16 at 09:26
  • If I understand it correctly you want something similar to this: http://mathsat.fbk.eu/apireference.html#aacfd2a633787d5ff92f78692d036ae04 , where you extend your input problem with `B_i -> (= var_i value_i)` and add every `B_i` as preferred_for_branching with initial truth value `TRUE`. I don't know whether **z3** has something similar, but it is very likely. – Patrick Trentin Jun 08 '16 at 09:30
  • A possible alternative is to encode the initial values as *soft-clauses* in *z3*, but as far as I know about *z3* that would not give you any guarantee on whether or not the solver will assume those equality constraints being true *first*, only that it will do it at some point. – Patrick Trentin Jun 08 '16 at 09:53
  • Alright, thanks for all the input - it will keep me busy for a while. I'll figure out whether any of the methods apply to what I'm trying to achieve (and if not I can still formulate a new and more elaborate question when I learned more background info). Thanks for your time! – Doidel Jun 08 '16 at 09:58

0 Answers0