YES(?, 2*a + 2)

Initial complexity problem:
1:	T:
		(?, 1)    eval(a) -> eval(0) [ 2*b >= 0 /\ 0 >= 2*b /\ a = 1 ]
		(?, 1)    eval(a) -> eval(2*b) [ 2*b >= 0 /\ 2*b + 2 >= 0 /\ a = 2*b + 1 ]
		(?, 1)    eval(a) -> eval(b) [ 1 >= 2*c /\ 2*c >= 0 /\ 2*d >= 1 /\ 1 >= 2*d /\ 1 >= 2*e /\ 3*e >= 2 /\ b >= e /\ 1 >= 2*f /\ 3*f >= 2 /\ f >= b /\ a = 1 ]
		(?, 1)    eval(a) -> eval(b) [ 2*d >= 1 /\ 2*d + 1 >= 0 /\ 2*d >= 2*c /\ 2*c + 1 >= 2*d /\ 2*d >= 2*e /\ 3*e >= 2*d + 1 /\ b >= e /\ 2*d >= 2*f /\ 3*f >= 2*d + 1 /\ f >= b /\ a = 2*d ]
		(1, 1)    start(a) -> eval(a)
	start location:	start
	leaf cost:	0

Testing for unsatisfiable constraints removes the following transition from problem 1:
	eval(a) -> eval(b) [ 1 >= 2*c /\ 2*c >= 0 /\ 2*d >= 1 /\ 1 >= 2*d /\ 1 >= 2*e /\ 3*e >= 2 /\ b >= e /\ 1 >= 2*f /\ 3*f >= 2 /\ f >= b /\ a = 1 ]
We thus obtain the following problem:
2:	T:
		(?, 1)    eval(a) -> eval(0) [ 2*b >= 0 /\ 0 >= 2*b /\ a = 1 ]
		(?, 1)    eval(a) -> eval(2*b) [ 2*b >= 0 /\ 2*b + 2 >= 0 /\ a = 2*b + 1 ]
		(?, 1)    eval(a) -> eval(b) [ 2*d >= 1 /\ 2*d + 1 >= 0 /\ 2*d >= 2*c /\ 2*c + 1 >= 2*d /\ 2*d >= 2*e /\ 3*e >= 2*d + 1 /\ b >= e /\ 2*d >= 2*f /\ 3*f >= 2*d + 1 /\ f >= b /\ a = 2*d ]
		(1, 1)    start(a) -> eval(a)
	start location:	start
	leaf cost:	0

Repeatedly removing leaves of the complexity graph in problem 2 produces the following problem:
3:	T:
		(?, 1)    eval(a) -> eval(2*b) [ 2*b >= 0 /\ 2*b + 2 >= 0 /\ a = 2*b + 1 ]
		(?, 1)    eval(a) -> eval(b) [ 2*d >= 1 /\ 2*d + 1 >= 0 /\ 2*d >= 2*c /\ 2*c + 1 >= 2*d /\ 2*d >= 2*e /\ 3*e >= 2*d + 1 /\ b >= e /\ 2*d >= 2*f /\ 3*f >= 2*d + 1 /\ f >= b /\ a = 2*d ]
		(1, 1)    start(a) -> eval(a)
	start location:	start
	leaf cost:	1

A polynomial rank function with
	Pol(eval) = V_1
	Pol(start) = V_1
orients all transitions weakly and the transitions
	eval(a) -> eval(2*b) [ 2*b >= 0 /\ 2*b + 2 >= 0 /\ a = 2*b + 1 ]
	eval(a) -> eval(b) [ 2*d >= 1 /\ 2*d + 1 >= 0 /\ 2*d >= 2*c /\ 2*c + 1 >= 2*d /\ 2*d >= 2*e /\ 3*e >= 2*d + 1 /\ b >= e /\ 2*d >= 2*f /\ 3*f >= 2*d + 1 /\ f >= b /\ a = 2*d ]
strictly and produces the following problem:
4:	T:
		(a, 1)    eval(a) -> eval(2*b) [ 2*b >= 0 /\ 2*b + 2 >= 0 /\ a = 2*b + 1 ]
		(a, 1)    eval(a) -> eval(b) [ 2*d >= 1 /\ 2*d + 1 >= 0 /\ 2*d >= 2*c /\ 2*c + 1 >= 2*d /\ 2*d >= 2*e /\ 3*e >= 2*d + 1 /\ b >= e /\ 2*d >= 2*f /\ 3*f >= 2*d + 1 /\ f >= b /\ a = 2*d ]
		(1, 1)    start(a) -> eval(a)
	start location:	start
	leaf cost:	1

Complexity upper bound 2*a + 2

Time: 0.098 sec (SMT: 0.091 sec)