Timeout for Z3 Optimize

Question

How do you set a timeout for the z3 optimizer such that it will give you the best known solution when it runs out of time?

from z3 import *
s = Optimize()
# Hard Problem
print(s.check())
print(s.model())

Follow-up question, can you set z3 to randomized hill climbing or does it always perform a complete search?

Answer 1

Long answer short, you can't. That's simply not how the optimizer works. That is, it doesn't find a solution and then try to improve it. If you interrupt it or set a time-out, when the timer expires it may not even have a satisfying solution, let alone an "improved" one by any means. You should look at the optimization paper for details: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/nbjorner-nuz.pdf

It is true, however, that z3 does keep track of bounds of variables, for numerical quantities. You might be able to extract these, though in general, you'll have no means of knowing what values out of those intervals you'd need to pick to get a satisfying solution for the overall problem. See this answer for a discussion: Is it possible to get a legit range info when using a SMT constraint with Z3

This sort of "hill-climbing" questions come up often in this forum. And the answer is simply that's not how z3's optimizer works. Some prior questions in this manner:

• Z3 Time Restricted Optimization
• z3 minimization and timeout

There are few other questions along these lines in stack-overflow. Search for "optimize" and "timeout".

Your best bet

That's the theory side of it. In practice, I believe the best approach to deal with a problem of this sort is not to use the optimizer at all. Instead do the following:

1. State your problem
2. Ask for a model. If there's no model, respond unsat. Quit.
3. Hold on to the current model as "best-so-far"
4. Out of time? Return the model you have as "best-so-far". You are done.

5. Still have time?

   5a. Compute the "cost" of this model. i.e., the metric you are trying to minimize or maximize. If you store the cost as a variable in your model, you can simply query its value from the model.

   5b. Assert a new constraint saying the cost should be lower than the cost of the current model. (Or higher if you are maximizing.) Depending on how fancy you want to get, you might want to "double" the cost function, or implement some sort of binary-search to converge on a value faster. But all that is really dependent on the exact details of the problem.

   5c. Ask for a new model. If unsat, return the last model you got as "optimal." Otherwise, repeat from step 3.

I believe this is the most practical approach for time-constraint optimization in z3. It gives you the full control on how many times to iterate, and guide the search in any way you want. (For instance, you can query for various variables at each model, and direct the search by saying "find me a bigger x, or a smaller y, etc., instead of looking at just one metric.) Hope that makes sense.

Summary

Note that an SMT solver can work like you're describing, i.e., give you an optimal-so-far solution when the time-out goes off. It's just that z3's optimizer does not work that way. For z3, I found the iterative loop described as above to be the most practical solution to this sort of timeout based optimization.

You can also look at OptiMathSAT (http://optimathsat.disi.unitn.it/) which might offer better facilities in this regard. @Patrick Trentin, who reads this forum often, is an expert on that and he might opine separately regarding its usage.

Answer 2

In general, @alias is right when he states that an OMT solver does not provide any guarantee of a solution being available at the end of the optimization search when this is interrupted by a timeout signal.

An OMT solver can look for an optimal solution in one of two ways:

• by starting from an initial Model of the formula and trying to improve the value of the objective function; This is the case of the standard OMT approach, which enumerates a number of partially optimized solutions until it finds the optimal one.

• by starting from more-than-optimal, unsatisfiable, assignment and progressively relaxing such assignment until it yields an optimal solution; AFAIK, this is only the case of the Maximum Resolution engine for dealing with MaxSMT problems.

When the OMT solver uses an optimization technique that falls in the first category, then it is possible to retrieve the best known solution when it runs out of time, provided that the OMT solver stores it in a safe place during the optimization search. This is not the case with the second MaxRes engine (see this Q/A).

A possible workaround. (CAVEAT: I haven't tested this) z3 keeps track of the lower and upper bound of the objective function along the optimization search. When minimizing, the upper bound corresponds to the value of the objective function in the most recent partial solution found by the OMT solver (dual for maximization). After a timeout signal occurred when minimizing (resp. maximizing) an obj instance obtained from minimize() (resp. maximize()), one should be able to retrieve the latest approximation v of the optimal value of obj by calling obj.upper() (resp. obj.lower()). Assuming that such value v is different from +oo (resp. -oo), one can incrementally learn a constraint of the form cost = v and perform an incremental SMT check of satisfiability to reconstruct the model corresponding to the sub-optimal solution that was hit by z3.

---

OptiMathSAT is one OMT solver that stores in a safe place the latest solution it encounters during the optimization search. This makes it easy to achieve what you want to do.

There are two types of timeout signals in OptiMathSAT:

• hard timeout: as soon as the timeout fires, the optimization search is stopped immediately; if the OMT solver found any solution, the result of the optimization search (accessible via msat_objective_result(env, obj)) is MSAT_OPT_SAT_PARTIAL and the Model corresponding to the latest sub-optimal solution can be extracted and printed; if instead the OMT solver didn't find any solution, the result of the optimization search is MSAT_UNKNOWN and no Model is available.

• soft timeout: if a timeout fires after the OMT solver found any solution, then the search is stopped immediately as in the case of a hard timeout. Otherwise, the timeout is ignored until the OMT solver finds one solution.

The type of timeout signal can be set using the option opt.soft_timeout=[true|false].

Example: The following example is the timeout.py unit-test contained in my omt_python_examples github repository that features a number of examples of how to use the Python API interface of OptiMathSAT.

"""
timeout unit-test.
"""

###
### SETUP PATHS
###

import os
import sys

BASE_DIR = os.path.dirname(os.path.abspath(__file__))
INCLUDE_DIR = os.path.join(BASE_DIR, '..', 'include')
LIB_DIR = os.path.join(BASE_DIR, '..', 'lib')
sys.path.append(INCLUDE_DIR)
sys.path.append(LIB_DIR)

from wrapper import * # pylint: disable=unused-wildcard-import,wildcard-import

###
### DATA
###

OPTIONS = {
    "model_generation" : "true",      # !IMPORTANT!
    "opt.soft_timeout" : "false",
    "opt.verbose"      : "true",
}

###
### TIMEOUT UNIT-TEST
###

with create_config(OPTIONS) as cfg:
    with create_env(cfg) as env:

        # Load Hard Problem from file
        with open(os.path.join(BASE_DIR, 'smt2', 'bacp-19.smt2'), 'r') as f:
            TERM = msat_from_smtlib2(env, f.read())
            assert not MSAT_ERROR_TERM(TERM)
            msat_assert_formula(env, TERM)

        # Impose a timeout of 3.0 seconds
        CALLBACK = Timer(3.0)
        msat_set_termination_test(env, CALLBACK)

        with create_minimize(env, "objective", lower="23", upper="100") as obj:
            assert_objective(env, obj)

            solve(env)                    # optimization search until timeout
            get_objectives_pretty(env)    # print latest range of optimization search

            load_model(env, obj)          # retrieve sub-optimal model
            dump_model(env)               # print sub-optimal model

This is the verbose output of the optimization search:

# obj(.cost_0) := objective
# obj(.cost_0) - search start: [ 23, 100 ]
# obj(.cost_0) - linear step: 1
# obj(.cost_0) -  new: 46
# obj(.cost_0) -  update upper: [ 23, 46 ]
# obj(.cost_0) - linear step: 2
# obj(.cost_0) -  new: 130/3
# obj(.cost_0) -  update upper: [ 23, 130/3 ]
# obj(.cost_0) - linear step: 3
# obj(.cost_0) -  new: 40
# obj(.cost_0) -  update upper: [ 23, 40 ]
# obj(.cost_0) - linear step: 4
# obj(.cost_0) -  new: 119/3
# obj(.cost_0) -  update upper: [ 23, 119/3 ]
# obj(.cost_0) - linear step: 5
# obj(.cost_0) -  new: 112/3
# obj(.cost_0) -  update upper: [ 23, 112/3 ]
# obj(.cost_0) - linear step: 6
# obj(.cost_0) -  new: 104/3
# obj(.cost_0) -  update upper: [ 23, 104/3 ]
# obj(.cost_0) - linear step: 7
# obj(.cost_0) -  new: 34
# obj(.cost_0) -  update upper: [ 23, 34 ]
# obj(.cost_0) - linear step: 8
# obj(.cost_0) -  new: 133/4
# obj(.cost_0) -  update upper: [ 23, 133/4 ]
# obj(.cost_0) - linear step: 9
# obj(.cost_0) -  new: 161/5
# obj(.cost_0) -  update upper: [ 23, 161/5 ]
# obj(.cost_0) - linear step: 10
# obj(.cost_0) -  new: 32
# obj(.cost_0) -  update upper: [ 23, 32 ]
# obj(.cost_0) - linear step: 11
# obj(.cost_0) -  new: 158/5
# obj(.cost_0) -  update upper: [ 23, 158/5 ]
# obj(.cost_0) - linear step: 12
# obj(.cost_0) -  new: 247/8
# obj(.cost_0) -  update upper: [ 23, 247/8 ]
# obj(.cost_0) - linear step: 13
# obj(.cost_0) -  new: 123/4
# obj(.cost_0) -  update upper: [ 23, 123/4 ]
# obj(.cost_0) - linear step: 14
# obj(.cost_0) -  new: 61/2
# obj(.cost_0) -  update upper: [ 23, 61/2 ]
# obj(.cost_0) - linear step: 15
unknown                                       ;; <== Timeout!
(objectives
  (objective 61/2), partial search, range: [ 23, 61/2 ]
)                                             ;; sub-optimal value, latest search interval

  course_load__ARRAY__1 : 9                   ;; and the corresponding sub-optimal model
  course_load__ARRAY__2 : 1
  course_load__ARRAY__3 : 2
  course_load__ARRAY__4 : 10
  course_load__ARRAY__5 : 3
  course_load__ARRAY__6 : 4
  course_load__ARRAY__7 : 1
  course_load__ARRAY__8 : 10
  course_load__ARRAY__9 : 4
  course_load__ARRAY__10 : 1
  course_load__ARRAY__11 : 1
  course_load__ARRAY__12 : 5
  course_load__ARRAY__13 : 10
  course_load__ARRAY__14 : 9
  course_load__ARRAY__15 : 1
  ...
  ;; the sub-optimal model is pretty long, it has been cut to fit this answer!
  ...