Merge branch 'solver3' into 'main'

Get 3.0 solver mostly in shape

See merge request apt-team/apt!451

51 files changed, 500 insertions, 428 deletions

diff --git a/apt-pkg/algorithms.cc b/apt-pkg/algorithms.cc
index 790ea4778..309d65977 100644
--- a/apt-pkg/algorithms.cc
+++ b/apt-pkg/algorithms.cc
@@ -1273,7 +1273,7 @@ bool pkgProblemResolver::KeepPhasedUpdates()
 bool pkgProblemResolver::ResolveByKeep(OpProgress * const Progress)
 {
    std::string const solver = _config->Find("APT::Solver", "internal");
-   constexpr auto flags = EDSP::Request::UPGRADE_ALL | EDSP::Request::FORBID_NEW_INSTALL | EDSP::Request::FORBID_REMOVE;
+   constexpr auto flags = EDSP::Request::FORBID_NEW_INSTALL | EDSP::Request::FORBID_REMOVE;
    auto const ret = EDSP::ResolveExternal(solver.c_str(), Cache, flags, Progress);
    if (solver != "internal")
       return ret;
diff --git a/apt-pkg/cacheiterators.h b/apt-pkg/cacheiterators.h
index 31ce1b295..38b4b8635 100644
--- a/apt-pkg/cacheiterators.h
+++ b/apt-pkg/cacheiterators.h
@@ -330,6 +330,7 @@ class APT_PUBLIC pkgCache::DepIterator : public Iterator<Dependency, DepIterator
 	   but change architecture nonetheless as a Conflicts: foo does applies for all archs */
 	bool IsImplicit() const APT_PURE;
 
+	bool IsSatisfied(PkgIterator const &Pkg) const APT_PURE;
 	bool IsSatisfied(VerIterator const &Ver) const APT_PURE;
 	bool IsSatisfied(PrvIterator const &Prv) const APT_PURE;
 	void GlobOr(DepIterator &Start,DepIterator &End);
diff --git a/apt-pkg/depcache.cc b/apt-pkg/depcache.cc
index ef93a54bb..b66f2bc66 100644
--- a/apt-pkg/depcache.cc
+++ b/apt-pkg/depcache.cc
@@ -2496,7 +2496,7 @@ static bool MarkPackage(pkgCache::PkgIterator const &Pkg,
 // pkgDepCache::MarkRequired - the main mark algorithm			/*{{{*/
 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
 {
-   if (_config->Find("APT::Solver", "internal") != "internal")
+   if (_config->Find("APT::Solver", "internal") != "internal" && _config->Find("APT::Solver") != "3.0")
       return true;
 
    // init the states
diff --git a/apt-pkg/edsp.cc b/apt-pkg/edsp.cc
index 88f572f18..bf96dd35c 100644
--- a/apt-pkg/edsp.cc
+++ b/apt-pkg/edsp.cc
@@ -754,13 +754,13 @@ static bool CreateDumpFile(char const * const id, char const * const type, FileF
 // EDSP::ResolveExternal - resolve problems by asking external for help	{{{*/
 bool EDSP::ResolveExternal(const char* const solver, pkgDepCache &Cache,
 			 unsigned int const flags, OpProgress *Progress) {
-   if (strcmp(solver, "3.0") == 0)
+   if (strstr(solver, "3.") == solver)
    {
-      APT::Solver s(Cache.GetCache(), Cache.GetPolicy());
+      APT::Solver s(Cache.GetCache(), Cache.GetPolicy(), (EDSP::Request::Flags) flags);
       FileFd output;
       bool res = true;
       if (Progress != NULL)
-	 Progress->OverallProgress(0, 100, 1, _config->FindB("APT::Solver::Upgrade") ? _("Calculating upgrade") : _("Solving dependencies"));
+	 Progress->OverallProgress(0, 100, 1, (flags & EDSP::Request::UPGRADE_ALL) ? _("Calculating upgrade") : _("Solving dependencies"));
       if (res && not s.FromDepCache(Cache))
 	 res = false;
       if (Progress != NULL)
diff --git a/apt-pkg/pkgcache.cc b/apt-pkg/pkgcache.cc
index bccd7798f..1f1aadf59 100644
--- a/apt-pkg/pkgcache.cc
+++ b/apt-pkg/pkgcache.cc
@@ -776,6 +776,13 @@ bool pkgCache::DepIterator::IsIgnorable(PrvIterator const &Prv) const
 }
 									/*}}}*/
 // DepIterator::IsSatisfied - check if a version satisfied the dependency /*{{{*/
+bool pkgCache::DepIterator::IsSatisfied(PkgIterator const &Pkg) const
+{
+   for (auto ver = Pkg.VersionList(); not ver.end(); ++ver)
+      if (not IsSatisfied(ver))
+	 return false;
+   return not Pkg.VersionList().end();
+}
 bool pkgCache::DepIterator::IsSatisfied(VerIterator const &Ver) const
 {
    return Owner->VS->CheckDep(Ver.VerStr(),S2->CompareOp,TargetVer());
diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index ed9beb828..c4fb567e1 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -32,8 +32,9 @@
 #include <apt-pkg/solver3.h>
 #include <apt-pkg/version.h>
 
-#include <algorithm>
 #include <cassert>
+#include <chrono>
+#include <ctime>
 #include <sstream>
 
 // FIXME: Helpers stolen from DepCache, please give them back.
@@ -194,7 +195,7 @@ class DefaultRootSetFunc2 : public pkgDepCache::DefaultRootSetFunc
 }; // FIXME: DEDUP with pkgDepCache.
 /*}}}*/
 
-APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy)
+APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy, EDSP::Request::Flags requestFlags)
     : cache(cache),
       policy(policy),
       rootState(new State),
@@ -202,7 +203,8 @@ APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy)
       verStates(cache),
       pkgObsolete(cache),
       priorities(cache),
-      candidates(cache)
+      candidates(cache),
+      requestFlags(requestFlags)
 {
    // Ensure trivially
    static_assert(std::is_trivially_destructible_v<Work>);
@@ -254,18 +256,28 @@ std::string APT::Solver::Work::toString(pkgCache &cache) const
    return out.str();
 }
 
+inline APT::Solver::Var APT::Solver::bestReason(APT::Solver::Clause const *clause, APT::Solver::Var var) const
+{
+   if (not clause)
+      return Var{};
+   if (clause->reason == var)
+      for (auto choice : clause->solutions)
+	 if ((*this)[choice].decision != Decision::NONE)
+	    return choice;
+   return clause->reason;
+}
+
 // Prints an implication graph part of the form A -> B -> C, possibly with "not"
 std::string APT::Solver::WhyStr(Var reason) const
 {
    std::vector<std::string> out;
-
    while (not reason.empty())
    {
       if ((*this)[reason].decision == Decision::MUSTNOT)
 	 out.push_back(std::string("not ") + reason.toString(cache));
       else
 	 out.push_back(reason.toString(cache));
-      reason = (*this)[reason].reason;
+      reason = bestReason((*this)[reason].reason, reason);
    }
 
    std::string outstr;
@@ -335,13 +347,13 @@ bool APT::Solver::Obsolete(pkgCache::PkgIterator pkg) const
    pkgObsolete[pkg] = 2;
    return true;
 }
-bool APT::Solver::Assume(Var var, bool decision, Var reason)
+bool APT::Solver::Assume(Var var, bool decision, const Clause *reason)
 {
    choices.push_back(solved.size());
    return Enqueue(var, decision, std::move(reason));
 }
 
-bool APT::Solver::Enqueue(Var var, bool decision, Var reason)
+bool APT::Solver::Enqueue(Var var, bool decision, const Clause *reason)
 {
    auto &state = (*this)[var];
    auto decisionCast = decision ? Decision::MUST : Decision::MUSTNOT;
@@ -349,7 +361,7 @@ bool APT::Solver::Enqueue(Var var, bool decision, Var reason)
    if (state.decision != Decision::NONE)
    {
       if (state.decision != decisionCast)
-	 return _error->Error("Conflict: %s -> %s%s but %s", WhyStr(reason).c_str(), decision ? "" : "not ", var.toString(cache).c_str(), WhyStr(var).c_str());
+	 return _error->Error("Conflict: %s -> %s%s but %s", WhyStr(bestReason(reason, var)).c_str(), decision ? "" : "not ", var.toString(cache).c_str(), WhyStr(var).c_str());
       return true;
    }
 
@@ -358,14 +370,11 @@ bool APT::Solver::Enqueue(Var var, bool decision, Var reason)
    state.reason = reason;
 
    if (unlikely(debug >= 1))
-      std::cerr << "[" << depth() << "] " << (decision ? "Install" : "Reject") << ":" << var.toString(cache) << " (" << WhyStr(state.reason) << ")\n";
+      std::cerr << "[" << depth() << "] " << (decision ? "Install" : "Reject") << ":" << var.toString(cache) << " (" << WhyStr(bestReason(reason, var)) << ")\n";
 
    solved.push_back(Solved{var, std::nullopt});
    propQ.push(var);
 
-   if (not decision)
-      needsRescore = true;
-
    return true;
 }
 
@@ -381,9 +390,57 @@ bool APT::Solver::Propagate()
 	 for (auto &clause : (*this)[var].clauses)
 	    if (not AddWork(Work{clause.get(), depth()}))
 	       return false;
+	 for (auto rclause : (*this)[var].rclauses)
+	 {
+	    if (not rclause->negative || rclause->optional || rclause->reason.empty())
+	       continue;
+	    if (unlikely(debug >= 3))
+	       std::cerr << "Propagate " << var.toString(cache) << " to NOT " << rclause->reason.toString(cache) << " for dep " << const_cast<Clause *>(rclause)->toString(cache) << std::endl;
+	    if (not Enqueue(rclause->reason, false, rclause))
+	       return false;
+	 }
+      }
+      else if ((*this)[var].decision == Decision::MUSTNOT)
+      {
+	 for (auto rclause : (*this)[var].rclauses)
+	 {
+	    if (rclause->negative || rclause->reason.empty())
+	       continue;
+	    if ((*this)[rclause->reason].decision == Decision::MUSTNOT)
+	       continue;
+
+	    auto count = std::count_if(rclause->solutions.begin(), rclause->solutions.end(), [this](auto var)
+				       { return (*this)[var].decision != Decision::MUSTNOT; });
+
+	    if (count == 1 && (*this)[rclause->reason].decision == Decision::MUST)
+	    {
+	       if (unlikely(debug >= 3))
+		  std::cerr << "Propagate NOT " << var.toString(cache) << " to unit clause " << rclause->toString(cache);
+	       if (rclause->optional)
+	       {
+		  // Enqueue duplicated item, this will ensure we see it at the correct time
+		  if (not AddWork(Work{rclause, depth()}))
+		     return false;
+	       }
+	       else
+	       {
+		  // Find the variable that must be chosen and enqueue it as a fact
+		  for (auto sol : rclause->solutions)
+		     if ((*this)[sol].decision == Decision::NONE && not Enqueue(sol, true, rclause))
+			return false;
+	       }
+	       continue;
+	    }
+	    if (count >= 1 || rclause->optional)
+	       continue;
+
+	    if (unlikely(debug >= 3))
+	       std::cerr << "Propagate NOT " << var.toString(cache) << " to " << rclause->reason.toString(cache) << " for dep " << const_cast<Clause *>(rclause)->toString(cache) << std::endl;
+
+	    if (not Enqueue(rclause->reason, false, rclause)) // Last version invalidated
+	       return false;
+	 }
       }
-      else if ((*this)[var].decision == Decision::MUSTNOT && not PropagateReject(var))
-	 return false;
    }
    return true;
 }
@@ -392,93 +449,84 @@ void APT::Solver::RegisterClause(Clause &&clause)
 {
    auto &clauses = (*this)[clause.reason].clauses;
    clauses.push_back(std::make_unique<Clause>(std::move(clause)));
+   auto const &inserted = clauses.back();
+   for (auto var : inserted->solutions)
+      (*this)[var].rclauses.push_back(inserted.get());
 }
 
 void APT::Solver::Discover(Var var)
 {
-   auto &state = (*this)[var];
+   assert(discoverQ.empty());
+   discoverQ.push(var);
 
-   if (state.flags.discovered)
-      return;
+   while (not discoverQ.empty())
+   {
+      var = discoverQ.front();
+      discoverQ.pop();
 
-   state.flags.discovered = true;
+      // Package needs to be discovered before the version to be able to dedup shared dependencies
+      if (auto Ver = var.Ver(cache); not Ver.end() && not(*this)[Ver.ParentPkg()].flags.discovered)
+	 var = Var(Ver.ParentPkg());
 
-   if (auto Pkg = var.Pkg(cache); not Pkg.end())
-   {
-      Clause clause{Var(Pkg), Group::SelectVersion};
-      for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
-	 clause.solutions.push_back(Var(ver));
+      auto &state = (*this)[var];
 
-      std::stable_sort(clause.solutions.begin(), clause.solutions.end(), CompareProviders3{cache, policy, Pkg, *this});
-      RegisterClause(std::move(clause));
+      if (state.flags.discovered)
+	 continue;
 
-      RegisterCommonDependencies(Pkg);
-   }
-   else if (auto Ver = var.Ver(cache); not Ver.end())
-   {
-      Clause clause{Var(Ver), Group::SelectVersion};
-      clause.solutions = {Var(Ver.ParentPkg())};
-      RegisterClause(std::move(clause));
+      state.flags.discovered = true;
 
-      for (auto OV = Ver.ParentPkg().VersionList(); not OV.end(); ++OV)
+      if (auto Pkg = var.Pkg(cache); not Pkg.end())
       {
-	 if (OV == Ver)
-	    continue;
+	 Clause clause{Var(Pkg), Group::SelectVersion};
+	 for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
+	    clause.solutions.push_back(Var(ver));
 
-	 Clause clause{Var(Ver), Group::SelectVersion, false, true /* negative */};
-	 clause.solutions = {Var(OV)};
+	 std::stable_sort(clause.solutions.begin(), clause.solutions.end(), CompareProviders3{cache, policy, Pkg, *this});
 	 RegisterClause(std::move(clause));
-      }
 
-      for (auto dep = Ver.DependsList(); not dep.end();)
+	 RegisterCommonDependencies(Pkg);
+      }
+      else if (auto Ver = var.Ver(cache); not Ver.end())
       {
-	 // Compute a single dependency element (glob or)
-	 pkgCache::DepIterator start;
-	 pkgCache::DepIterator end;
-	 dep.GlobOr(start, end); // advances dep
+	 Clause clause{Var(Ver), Group::SelectVersion};
+	 clause.solutions = {Var(Ver.ParentPkg())};
+	 RegisterClause(std::move(clause));
 
-	 auto clause = TranslateOrGroup(start, end, Var(Ver));
+	 for (auto OV = Ver.ParentPkg().VersionList(); not OV.end(); ++OV)
+	 {
+	    if (OV == Ver)
+	       continue;
 
-	 RegisterClause(std::move(clause));
-      }
-   }
-}
+	    Clause clause{Var(Ver), Group::SelectVersion, false, true /* negative */};
+	    clause.solutions = {Var(OV)};
+	    RegisterClause(std::move(clause));
+	 }
 
-bool APT::Solver::PropagateReject(Var var)
-{
-   if (auto Pkg = var.Pkg(cache); not Pkg.end())
-   {
-      for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
-	 if (not Enqueue(Var(ver), false, Var(Pkg)))
-	    return false;
-   }
-   else if (auto Ver = var.Ver(cache); not Ver.end())
-   {
-      if (auto pkg = Ver.ParentPkg(); (*this)[pkg].decision != Decision::MUSTNOT)
-      {
-	 bool anyInstallable = false;
-	 for (auto otherVer = pkg.VersionList(); not otherVer.end(); otherVer++)
-	    if (otherVer->ID != Ver->ID && (*this)[otherVer].decision != Decision::MUSTNOT)
-	       anyInstallable = true;
-
-	 if (anyInstallable)
-	    ;
-	 else if ((*this)[pkg].decision == Decision::MUST) // Must install, but none available
+	 for (auto dep = Ver.DependsList(); not dep.end();)
 	 {
-	    _error->Error("Conflict: %s but no versions are installable",
-			  WhyStr(Var(pkg)).c_str());
-	    for (auto otherVer = pkg.VersionList(); not otherVer.end(); otherVer++)
-	       if ((*this)[otherVer].decision == Decision::MUSTNOT)
-		  _error->Error("Uninstallable version: %s", WhyStr(Var(otherVer)).c_str());
-	    return _error->Error("Uninstallable version: %s", WhyStr(Var(Ver)).c_str());
+	    // Compute a single dependency element (glob or)
+	    pkgCache::DepIterator start;
+	    pkgCache::DepIterator end;
+	    dep.GlobOr(start, end); // advances dep
+
+	    // This dependency is shared across all versions, skip it.
+	    if (auto &pkgClauses = (*this)[Ver.ParentPkg()].clauses;
+		std::any_of(pkgClauses.begin(), pkgClauses.end(), [start](auto &c)
+			    { return c->dep && c->dep->DependencyData == start->DependencyData; }))
+	       continue;
+
+	    auto clause = TranslateOrGroup(start, end, Var(Ver));
+
+	    RegisterClause(std::move(clause));
 	 }
-	 else if (not Enqueue(Var(Ver.ParentPkg()), false, Var(Ver))) // Last version invalidated
-	    return false;
       }
-      if (not RejectReverseDependencies(Ver))
-	 return false;
+
+      // Recursively discover everything else that is not already FALSE by fact (MUSTNOT at depth 0)
+      for (auto const &clause : state.clauses)
+	 for (auto const &var : clause->solutions)
+	    if ((*this)[var].decision != Decision::MUSTNOT || (*this)[var].depth > 0)
+	       discoverQ.push(var);
    }
-   return true;
 }
 
 void APT::Solver::RegisterCommonDependencies(pkgCache::PkgIterator Pkg)
@@ -527,30 +575,42 @@ APT::Solver::Clause APT::Solver::TranslateOrGroup(pkgCache::DepIterator start, p
    do
    {
       auto begin = clause.solutions.size();
-      auto all = start.AllTargets();
 
-      for (auto tgt = all; *tgt; ++tgt)
+      if (DeferVersionSelection && not start.IsNegative() && start.TargetPkg().ProvidesList().end() && start.IsSatisfied(start.TargetPkg()))
       {
-	 pkgCache::VerIterator tgti(cache, *tgt);
-	 if (unlikely(debug >= 3))
-	    std::cerr << "Adding work to  item " << reason.toString(cache) << " -> " << tgti.ParentPkg().FullName() << "=" << tgti.VerStr() << (clause.negative ? " (negative)" : "") << "\n";
-	 clause.solutions.push_back(Var(pkgCache::VerIterator(cache, *tgt)));
+	 clause.solutions.push_back(Var(start.TargetPkg()));
       }
-      delete[] all;
+      else
+      {
+	 auto all = start.AllTargets();
 
-      // If we are fixing the policy, we need to sort each alternative in an or group separately
-      // FIXME: This is not really true, though, we should fix the CompareProviders to ignore the
-      // installed state
-      if (FixPolicyBroken)
-	 std::stable_sort(clause.solutions.begin() + begin, clause.solutions.end(), CompareProviders3{cache, policy, TgtPkg, *this});
+	 for (auto tgt = all; *tgt; ++tgt)
+	 {
+	    pkgCache::VerIterator tgti(cache, *tgt);
+
+	    if (unlikely(debug >= 3))
+	       std::cerr << "Adding work to  item " << reason.toString(cache) << " -> " << tgti.ParentPkg().FullName() << "=" << tgti.VerStr() << (clause.negative ? " (negative)" : "") << "\n";
+	    clause.solutions.push_back(Var(pkgCache::VerIterator(cache, *tgt)));
+	 }
+	 delete[] all;
 
+	 std::stable_sort(clause.solutions.begin() + begin, clause.solutions.end(), CompareProviders3{cache, policy, TgtPkg, *this});
+      }
       if (start == end)
 	 break;
       ++start;
    } while (1);
 
+   // Move obsolete packages to the end, and (non-obsolete) installed packages to the front
    if (not FixPolicyBroken)
-      std::stable_sort(clause.solutions.begin(), clause.solutions.end(), CompareProviders3{cache, policy, TgtPkg, *this});
+      std::stable_sort(clause.solutions.begin(), clause.solutions.end(), [this](Var a, Var b)
+		       {
+	    if (IsUpgrade)
+	       if (auto obsoleteA = Obsolete(a.CastPkg(cache)), obsoleteB = Obsolete(b.CastPkg(cache)); obsoleteA != obsoleteB)
+		  return obsoleteB;
+	    if ((a.CastPkg(cache)->CurrentVer == 0 || b.CastPkg(cache)->CurrentVer == 0) && a.CastPkg(cache)->CurrentVer != b.CastPkg(cache)->CurrentVer)
+	       return a.CastPkg(cache)->CurrentVer != 0;
+	    return false; });
 
    if (std::all_of(clause.solutions.begin(), clause.solutions.end(), [this](auto var) -> auto
 		   { return var.CastPkg(cache)->CurrentVer == 0; }))
@@ -583,6 +643,18 @@ APT::Solver::Clause APT::Solver::TranslateOrGroup(pkgCache::DepIterator start, p
 	    std::cerr << "Promoting satisfied Suggests to Recommends: " << clause.toString(cache) << std::endl;
 	 important = true;
       }
+      else if (satisfied && important && wasImportant && clause.solutions.size() > 0)
+      {
+	 if (unlikely(debug >= 3))
+	    std::cerr << "Promoting existing Recommends " << clause.toString(cache) << " to depends in upgrade" << std::endl;
+	 clause.optional = false;
+      }
+      else if (newOptional && important && reason.Ver() && clause.solutions.size() > 0 && reason.Ver(cache) != reason.CastPkg(cache).CurrentVer() && IsUpgrade)
+      {
+	 if (unlikely(debug >= 3))
+	    std::cerr << "Promoting new Recommends " << clause.toString(cache) << " to depends in upgrade" << std::endl;
+	 clause.optional = false;
+      }
       else if (not important)
       {
 	 if (unlikely(debug >= 3))
@@ -594,73 +666,6 @@ APT::Solver::Clause APT::Solver::TranslateOrGroup(pkgCache::DepIterator start, p
    return clause;
 }
 
-// \brief Find the or group containing the given dependency.
-static void FindOrGroup(pkgCache::DepIterator const &D, pkgCache::DepIterator &start, pkgCache::DepIterator &end)
-{
-   for (auto dep = D.ParentVer().DependsList(); not dep.end();)
-   {
-      dep.GlobOr(start, end); // advances dep
-
-      for (auto member = start;;)
-      {
-	 if (member == D)
-	    return;
-	 if (member == end)
-	    break;
-	 member++;
-      }
-   }
-
-   _error->Fatal("Found a dependency that does not exist in its parent version");
-   abort();
-}
-
-// This is the opposite of EnqueueOrDependencies, it rejects the reverse dependencies of the
-// given version iterator.
-bool APT::Solver::RejectReverseDependencies(pkgCache::VerIterator Ver)
-{
-   // This checks whether an or group is still satisfiable.
-   auto stillPossible = [this](pkgCache::DepIterator start, pkgCache::DepIterator end)
-   {
-      while (1)
-      {
-	 std::unique_ptr<pkgCache::Version *[]> Ts{start.AllTargets()};
-	 for (size_t i = 0; Ts[i] != nullptr; ++i)
-	    if ((*this)[Ts[i]].decision != Decision::MUSTNOT)
-	       return true;
-
-	 if (start == end)
-	    return false;
-
-	 start++;
-      }
-   };
-
-   for (auto RD = Ver.ParentPkg().RevDependsList(); not RD.end(); ++RD)
-   {
-      auto RDV = RD.ParentVer();
-      if (RD.IsNegative() || not RD.IsCritical() || not RD.IsSatisfied(Ver))
-	 continue;
-
-      if ((*this)[RDV].decision == Decision::MUSTNOT)
-	 continue;
-
-      pkgCache::DepIterator start;
-      pkgCache::DepIterator end;
-      FindOrGroup(RD, start, end);
-
-      if (stillPossible(start, end))
-	 continue;
-
-      if (unlikely(debug >= 3))
-	 std::cerr << "Propagate NOT " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " to " << RDV.ParentPkg().FullName() << "=" << RDV.VerStr() << " for dependency group starting with" << start.TargetPkg().FullName() << std::endl;
-
-      if (not Enqueue(Var(RDV), false, Var(Ver)))
-	 return false;
-   }
-   return true;
-}
-
 void APT::Solver::Push(Work work)
 {
    if (unlikely(debug >= 2))
@@ -682,15 +687,10 @@ void APT::Solver::UndoOne()
    if (not solvedItem.assigned.empty())
    {
       if (unlikely(debug >= 4))
-      {
-	 if (auto P = solvedItem.assigned.Pkg(cache); not P.end())
-	    std::cerr << "Unassign " << P.FullName() << "\n";
-	 if (auto V = solvedItem.assigned.Ver(cache); not V.end())
-	    std::cerr << "Unassign " << V.ParentPkg().FullName() << "=" << V.VerStr() << "\n";
-      }
+	 std::cerr << "Unassign " << solvedItem.assigned.toString(cache) << "\n";
       auto &state = (*this)[solvedItem.assigned];
       state.decision = Decision::NONE;
-      state.reason = Var();
+      state.reason = nullptr;
       state.depth = 0;
    }
 
@@ -717,6 +717,10 @@ bool APT::Solver::Pop()
       for (std::string msg; _error->PopMessage(msg);)
 	 std::cerr << "Branch failed: " << msg << std::endl;
 
+   time_t now = time(nullptr);
+   if (now - startTime >= Timeout)
+      return _error->Error("Solver timed out.");
+
    _error->RevertToStack();
 
    assert(choices.back() < solved.size());
@@ -753,7 +757,7 @@ bool APT::Solver::AddWork(Work &&w)
    if (w.clause->negative)
    {
       for (auto var : w.clause->solutions)
-	 if (not Enqueue(var, false, w.clause->reason))
+	 if (not Enqueue(var, false, w.clause))
 	    return false;
    }
    else if (not w.clause->solutions.empty())
@@ -761,7 +765,7 @@ bool APT::Solver::AddWork(Work &&w)
       if (unlikely(debug >= 3 && w.clause->optional))
 	 std::cerr << "Enqueuing Recommends " << w.clause->toString(cache) << std::endl;
       if (w.clause->solutions.size() == 1 && not w.clause->optional)
-	 return Enqueue(w.clause->solutions[0], true, w.clause->reason);
+	 return Enqueue(w.clause->solutions[0], true, w.clause);
 
       w.size = std::count_if(w.clause->solutions.begin(), w.clause->solutions.end(), [this](auto V)
 			     { return (*this)[V].decision != Decision::MUSTNOT; });
@@ -775,42 +779,9 @@ bool APT::Solver::AddWork(Work &&w)
    return true;
 }
 
-void APT::Solver::RescoreWorkIfNeeded()
-{
-   if (not needsRescore)
-      return;
-
-   needsRescore = false;
-   std::vector<Work> resized;
-   for (auto &w : work)
-   {
-      if (w.erased)
-	 continue;
-      size_t newSize = std::count_if(w.clause->solutions.begin(), w.clause->solutions.end(), [this](auto V)
-				     { return (*this)[V].decision != Decision::MUSTNOT; });
-
-      // Notably we only insert the work into the queue if it got smaller. Work that got larger
-      // we just move around when we get to it too early in Solve(). This reduces memory usage
-      // at the expense of counting each item we see in Solve().
-      if (newSize < w.size)
-      {
-	 Work newWork(w);
-	 newWork.size = newSize;
-	 resized.push_back(std::move(newWork));
-	 w.erased = true;
-      }
-   }
-   if (unlikely(debug >= 2))
-      std::cerr << "Rescored: " << resized.size() << "items\n";
-   for (auto &w : resized)
-   {
-      work.push_back(std::move(w));
-      std::push_heap(work.begin(), work.end());
-   }
-}
-
 bool APT::Solver::Solve()
 {
+   startTime = time(nullptr);
    while (true)
    {
       while (not Propagate())
@@ -822,8 +793,6 @@ bool APT::Solver::Solve()
       if (work.empty())
 	 break;
 
-      // Rescore the work if we need to
-      RescoreWorkIfNeeded();
       // *NOW* we can pop the item.
       std::pop_heap(work.begin(), work.end());
 
@@ -833,19 +802,6 @@ bool APT::Solver::Solve()
 	 work.pop_back();
 	 continue;
       }
-
-      // If our size increased, queue again.
-      size_t newSize = std::count_if(work.back().clause->solutions.begin(), work.back().clause->solutions.end(), [this](auto V)
-				     { return (*this)[V].decision != Decision::MUSTNOT; });
-
-      if (newSize > work.back().size)
-      {
-	 work.back().size = newSize;
-	 std::push_heap(work.begin(), work.end());
-	 continue;
-      }
-      assert(newSize == work.back().size);
-
       auto item = std::move(work.back());
       work.pop_back();
       solved.push_back(Solved{Var(), item});
@@ -879,7 +835,7 @@ bool APT::Solver::Solve()
 	 }
 	 if (unlikely(debug >= 3))
 	    std::cerr << "(try it: " << sol.toString(cache) << ")\n";
-	 if (not Enqueue(sol, true, item.clause->reason) && not Pop())
+	 if (not Enqueue(sol, true, item.clause) && not Pop())
 	    return false;
 	 foundSolution = true;
 	 break;
@@ -913,8 +869,10 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
    {
       for (auto P = cache.PkgBegin(); not P.end(); P++)
       {
+	 bool isForced = depcache[P].Protect() && depcache[P].Install();
+	 bool isPhasing = IsUpgrade && depcache.PhasingApplied(P) && not isForced;
 	 for (auto V = P.VersionList(); not V.end(); ++V)
-	    if (P.CurrentVer() != V && depcache.GetCandidateVersion(P) != V)
+	    if (P.CurrentVer() != V && (depcache.GetCandidateVersion(P) != V || isPhasing))
 	       if (not Enqueue(Var(V), false, {}))
 		  return false;
       }
@@ -930,7 +888,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
       {
 	 if (unlikely(debug >= 1))
 	    std::cerr << "Hold " << P.FullName() << "\n";
-	 if (P->CurrentVer ? not Enqueue(Var(P.CurrentVer()), true, {}) : not Enqueue(Var(P), false, Var()))
+	 if (P->CurrentVer ? not Enqueue(Var(P.CurrentVer()), true) : not Enqueue(Var(P), false))
 	    return false;
       }
       else if (state.Delete()						  // Normal delete request.
@@ -940,7 +898,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
       {
 	 if (unlikely(debug >= 1))
 	    std::cerr << "Delete " << P.FullName() << "\n";
-	 if (not Enqueue(Var(P), false, Var()))
+	 if (not Enqueue(Var(P), false))
 	    return false;
       }
       else if (state.Install() || (state.Keep() && P->CurrentVer))
@@ -967,7 +925,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
 	 if (not isOptional)
 	 {
 	    // Pre-empt the non-optional requests, as we don't want to queue them, we can just "unit propagate" here.
-	    if (depcache[P].Keep() ? not Enqueue(Var(P), true, {}) : not Enqueue(Var(depcache.GetCandidateVersion(P)), true, {}))
+	    if (depcache[P].Keep() ? not Enqueue(Var(P), true) : not Enqueue(Var(depcache.GetCandidateVersion(P)), true))
 	       return false;
 	 }
 	 else
@@ -990,8 +948,26 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
 	    RegisterClause(std::move(shortcircuit));
 	    if (not AddWork(Work{rootState->clauses.back().get(), depth()}))
 	       return false;
+
+	    // Discovery here is needed so the shortcircuit clause can actually become unit.
+	    if (P.VersionList() && P.VersionList()->NextVer)
+	       Discover(Var(P));
 	 }
       }
+      else if (IsUpgrade && AllowRemove && AllowInstall && (P->Flags & pkgCache::Flag::Essential))
+      {
+	 Clause w{Var(), Group::InstallManual, false};
+	 auto G = P.Group();
+	 for (auto P = G.PackageList(); not P.end(); P = G.NextPkg(P))
+	    if (P->Flags & pkgCache::Flag::Essential)
+	       w.solutions.push_back(Var(P));
+	 std::stable_sort(w.solutions.begin(), w.solutions.end(), CompareProviders3{cache, policy, P, *this});
+	 if (unlikely(debug >= 1))
+	    std::cerr << "Install essential package " << P << std::endl;
+	 RegisterClause(std::move(w));
+	 if (not AddWork(Work{rootState->clauses.back().get(), depth()}))
+	    return false;
+      }
    }
 
    return Propagate();
@@ -1006,27 +982,32 @@ bool APT::Solver::ToDepCache(pkgDepCache &depcache) const
       depcache[P].Garbage = 0;
       if ((*this)[P].decision == Decision::MUST)
       {
-	 for (auto V = P.VersionList(); not V.end(); V++)
-	 {
+	 pkgCache::VerIterator cand;
+	 for (auto V = P.VersionList(); cand.end() && not V.end(); V++)
 	    if ((*this)[V].decision == Decision::MUST)
-	    {
-	       depcache.SetCandidateVersion(V);
-	       break;
-	    }
-	 }
-	 auto reason = (*this)[depcache.GetCandidateVersion(P)].reason;
+	       cand = V;
+
+	 auto reasonClause = (*this)[cand].reason;
+	 auto reason = reasonClause ? reasonClause->reason : Var();
 	 if (auto RP = reason.Pkg(); RP == P.MapPointer())
-	    reason = (*this)[P].reason;
+	    reason = (*this)[P].reason ? (*this)[P].reason->reason : Var();
+
+	 if (cand != P.CurrentVer())
+	 {
+	    depcache.SetCandidateVersion(cand);
+	    depcache.MarkInstall(P, false, 0, reason.empty() && not(depcache[P].Flags & pkgCache::Flag::Auto));
+	    if (not P->CurrentVer)
+	       depcache.MarkAuto(P, not reason.empty());
+	 }
+	 else
+	    depcache.MarkKeep(P, false, reason.empty() && not(depcache[P].Flags & pkgCache::Flag::Auto));
 
-	 depcache.MarkInstall(P, false, 0, reason.empty());
-	 if (not P->CurrentVer)
-	    depcache.MarkAuto(P, not reason.empty());
 	 depcache[P].Marked = 1;
 	 depcache[P].Garbage = 0;
       }
       else if (P->CurrentVer || depcache[P].Install())
       {
-	 depcache.MarkDelete(P, false, 0, (*this)[P].reason.empty());
+	 depcache.MarkDelete(P, false, 0, not(*this)[P].reason);
 	 depcache[P].Marked = 0;
 	 depcache[P].Garbage = 1;
       }
diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
index 65cd9f017..65a201222 100644
--- a/apt-pkg/solver3.h
+++ b/apt-pkg/solver3.h
@@ -14,6 +14,7 @@
 
 #include <apt-pkg/configuration.h>
 #include <apt-pkg/depcache.h>
+#include <apt-pkg/edsp.h>
 #include <apt-pkg/pkgcache.h>
 #include <apt-pkg/policy.h>
 
@@ -192,8 +193,6 @@ class Solver
    // be able to iterate over the queued work and see if a choice would
    // invalidate any work.
    heap<Work> work{};
-   // \brief Whether RescoreWork() actually needs to rescore the work.
-   bool needsRescore{false};
 
    // \brief Backlog of solved work.
    //
@@ -205,51 +204,62 @@ class Solver
 
    // \brief Propagation queue
    std::queue<Var> propQ;
+   // \brief Discover variables
+   std::queue<Var> discoverQ;
 
    // \brief Current decision level.
    //
    // This is an index into the solved vector.
    std::vector<depth_type> choices{};
 
+   // \brief The time we called Solve()
+   time_t startTime;
+
+   EDSP::Request::Flags requestFlags;
    /// Various configuration options
+   std::string version{_config->Find("APT::Solver", "3.0")};
    // \brief Debug level
    int debug{_config->FindI("Debug::APT::Solver")};
    // \brief If set, we try to keep automatically installed packages installed.
-   bool KeepAuto{not _config->FindB("APT::Get::AutomaticRemove")};
+   bool KeepAuto{version == "3.0" || not _config->FindB("APT::Get::AutomaticRemove")};
    // \brief Determines if we are in upgrade mode.
-   bool IsUpgrade{_config->FindB("APT::Solver::Upgrade", false)};
+   bool IsUpgrade{_config->FindB("APT::Solver::Upgrade", requestFlags &EDSP::Request::UPGRADE_ALL)};
    // \brief If set, removals are allowed.
-   bool AllowRemove{_config->FindB("APT::Solver::Remove", true)};
+   bool AllowRemove{_config->FindB("APT::Solver::Remove", not(requestFlags & EDSP::Request::FORBID_REMOVE))};
    // \brief If set, removal of manual packages is allowed.
    bool AllowRemoveManual{AllowRemove && _config->FindB("APT::Solver::RemoveManual", false)};
    // \brief If set, installs are allowed.
-   bool AllowInstall{_config->FindB("APT::Solver::Install", true)};
+   bool AllowInstall{_config->FindB("APT::Solver::Install", not(requestFlags & EDSP::Request::FORBID_NEW_INSTALL))};
    // \brief If set, we use strict pinning.
    bool StrictPinning{_config->FindB("APT::Solver::Strict-Pinning", true)};
    // \brief If set, we install missing recommends and pick new best packages.
    bool FixPolicyBroken{_config->FindB("APT::Get::Fix-Policy-Broken")};
+   // \brief If set, we use strict pinning.
+   bool DeferVersionSelection{_config->FindB("APT::Solver::Defer-Version-Selection", true)};
+   // \brief If set, we use strict pinning.
+   int Timeout{_config->FindI("APT::Solver::Timeout", 10)};
 
    // \brief Discover a variable, translating the underlying dependencies to the SAT presentation
+   //
+   // This does a breadth-first search of the entire dependency tree of var,
+   // utilizing the discoverQ above.
    void Discover(Var var);
    // \brief Link a clause into the watchers
    void RegisterClause(Clause &&clause);
    // \brief Enqueue dependencies shared by all versions of the package.
    void RegisterCommonDependencies(pkgCache::PkgIterator Pkg);
 
-   // \brief Reject reverse dependencies. Must call std::make_heap() after.
-   [[nodiscard]] bool RejectReverseDependencies(pkgCache::VerIterator Ver);
    // \brief Translate an or group into a clause object
    [[nodiscard]] Clause TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason);
    // \brief Propagate all pending propagations
    [[nodiscard]] bool Propagate();
-   // \brief Propagate a rejection of a variable
-   [[nodiscard]] bool PropagateReject(Var var);
 
    // \brief Return the current depth (choices.size() with casting)
    depth_type depth()
    {
       return static_cast<depth_type>(choices.size());
    }
+   inline Var bestReason(Clause const *clause, Var var) const;
 
    public:
    // \brief Create a new decision level.
@@ -260,16 +270,14 @@ class Solver
    void UndoOne();
    // \brief Add work to our work queue.
    [[nodiscard]] bool AddWork(Work &&work);
-   // \brief Rescore the work after a reject or a pop
-   void RescoreWorkIfNeeded();
 
    // \brief Basic solver initializer. This cannot fail.
-   Solver(pkgCache &Cache, pkgDepCache::Policy &Policy);
+   Solver(pkgCache &Cache, pkgDepCache::Policy &Policy, EDSP::Request::Flags requestFlags);
 
    // Assume that the variable is decided as specified.
-   [[nodiscard]] bool Assume(Var var, bool decision, Var reason);
+   [[nodiscard]] bool Assume(Var var, bool decision, const Clause *reason = nullptr);
    // Enqueue a decision fact
-   [[nodiscard]] bool Enqueue(Var var, bool decision, Var reason);
+   [[nodiscard]] bool Enqueue(Var var, bool decision, const Clause *reason = nullptr);
 
    // \brief Apply the selections from the dep cache to the solver
    [[nodiscard]] bool FromDepCache(pkgDepCache &depcache);
@@ -333,7 +341,7 @@ struct APT::Solver::Var
    {
       return IsVersion == 0 && MapPtr == 0;
    }
-   bool operator==(Var const other)
+   bool operator==(Var const other) const
    {
       return IsVersion == other.IsVersion && MapPtr == other.MapPtr;
    }
@@ -440,7 +448,7 @@ struct APT::Solver::State
    // doesn't increase to unwind.
    //
    // Vars < 0 are package ID, reasons > 0 are version IDs.
-   Var reason{};
+   const Clause *reason{};
 
    // \brief The depth at which the decision has been taken
    depth_type depth{0};
@@ -458,6 +466,8 @@ struct APT::Solver::State
 
    // \brief Clauses owned by this package/version
    std::vector<std::unique_ptr<Clause>> clauses;
+   // \brief Reverse clauses, that is dependencies (or conflicts) from other packages on this one
+   std::vector<const Clause *> rclauses;
 };
 
 /**
diff --git a/apt-pkg/upgrade.cc b/apt-pkg/upgrade.cc
index ac0b71cdf..fad47838c 100644
--- a/apt-pkg/upgrade.cc
+++ b/apt-pkg/upgrade.cc
@@ -312,11 +312,6 @@ bool pkgMinimizeUpgrade(pkgDepCache &Cache)
 // APT::Upgrade::Upgrade - Upgrade using a specific strategy		/*{{{*/
 bool APT::Upgrade::Upgrade(pkgDepCache &Cache, int mode, OpProgress * const Progress)
 {
-   _config->Set("APT::Solver::Upgrade", "true");
-   if (mode & FORBID_REMOVE_PACKAGES)
-      _config->Set("APT::Solver::Remove", "false");
-   if (mode & FORBID_INSTALL_NEW_PACKAGES)
-      _config->Set("APT::Solver::Install", "false");
    if (mode == ALLOW_EVERYTHING)
       return pkgDistUpgrade(Cache, Progress);
    else if ((mode & ~FORBID_REMOVE_PACKAGES) == 0)
diff --git a/doc/examples/configure-index b/doc/examples/configure-index
index ba51a9881..8476d733a 100644
--- a/doc/examples/configure-index
+++ b/doc/examples/configure-index
@@ -698,10 +698,12 @@ apt::list-cleanup "<BOOL>";
 apt::authentication::trustcdrom "<BOOL>";
 apt::solver::strict-pinning "<BOOL>";
 apt::solver::enqueue-common-dependencies "<BOOL>";
+apt::solver::defer-version-selection "<BOOL>";
 apt::solver::upgrade "<BOOL>";
 apt::solver::remove "<BOOL>";
 apt::solver::removemanual "<BOOL>";
 apt::solver::install "<BOOL>";
+apt::solver::timeout "<INT>";
 apt::keep-downloaded-packages "<BOOL>";
 apt::solver "<STRING>";
 apt::planner "<STRING>";
diff --git a/test/integration/run-tests b/test/integration/run-tests
index e52214e0a..9399f28e9 100755
--- a/test/integration/run-tests
+++ b/test/integration/run-tests
@@ -61,7 +61,7 @@ if [ -n "$TESTTORUN" ]; then
 	CURRENTTRAP="rm -f \"$OUTPUT\"; $CURRENTTRAP"
 	trap "$CURRENTTRAP" 0 HUP INT QUIT ILL ABRT FPE SEGV PIPE TERM
 	{
-		if [ "$APT_SKIP_TEST_FILE" ] && grep -qFx "${TESTTORUN##*/}" "$APT_SKIP_TEST_FILE"; then
+		if [ "$APT_SKIP_TEST_FILE" ] &&  sed 's/ *#.*//' "$APT_SKIP_TEST_FILE" | grep -qFx "${TESTTORUN##*/}"; then
 			if [ "$MSGLEVEL" -le 2 ]; then
 				printf "${CTEST}Skip Testcase ${CHIGH}${TESTTORUN##*/}${CRESET}"
 			else
@@ -117,7 +117,7 @@ FAILED_TESTS=""
 DIR="$(readlink -f "$(dirname "$0")")"
 cd "$DIR"
 if [ -e "$TESTLIST" ]; then
-	TESTLIST="$(sort < "$TESTLIST" | sed 's#^#./#')"
+	TESTLIST="$(sort < "$TESTLIST" | sed 's#^#./#;s/ *#.*//')"
 else
 	TESTLIST="$(find . -mindepth 1 -maxdepth 1 -regex '^\./test-[^/]*$' | sort)"
 fi
diff --git a/test/integration/solver3.broken b/test/integration/solver3.broken
index 2212c34ae..2ad00555b 100644
--- a/test/integration/solver3.broken
+++ b/test/integration/solver3.broken
@@ -1,31 +1,9 @@
-test-allow-scores-for-all-dependency-types
-test-apt-get-autoremove
-test-apt-get-autoremove-kernel-module-providers
-test-apt-get-upgrade-by-source
-test-apt-install-file-reltag
-test-apt-install-order-matters-a-bit
-test-apt-move-and-forget-manual-sections
-test-apt-patterns
-test-bug-470115-new-and-tighten-recommends
-test-bug-602412-dequote-redirect
-test-bug-611729-mark-as-manual
-test-bug-675449-essential-are-protected
-test-bug-745046-candidate-propagation-fails
-test-bug-753297-upgradable
-test-bug-767891-force-essential-important
-test-bug-961266-hold-means-hold
-test-dont-forget-conflicts-via-unknown-architectures
-test-explore-or-groups-in-markinstall
-test-external-dependency-solver-protocol
-test-method-mirror
-test-parse-all-archs-into-cache
-test-phased-updates-new-depends
-test-phased-updates-upgrade
-test-prevent-markinstall-multiarch-same-versionscrew
-test-release-candidate-switching
-test-resolve-by-keep-new-recommends
-test-resolve-by-keep-obsolete-removals
-test-ubuntu-bug-1304403-obsolete-priority-standard
-test-ubuntu-bug-1990586
-test-ubuntu-bug-2025462-phased-dist-upgrade
-test-ubuntu-bug-614993
+test-allow-scores-for-all-dependency-types                  # TBD: We are lacking single-sided conflicts preferences
+test-apt-get-upgrade-by-source                              # TBD: Upgrading by source is not supported yet, mostly same issue as above
+test-apt-install-order-matters-a-bit                        # Wontfix: Cannot fix, the order is not recorded in the depcache
+test-apt-move-and-forget-manual-sections                    # TBD: Moving the auto bit is not implemented
+test-bug-470115-new-and-tighten-recommends                  # TBD: Calculation of what is already satisfied Recommends is broken
+test-prevent-markinstall-multiarch-same-versionscrew        # TBD: We consider the skewed ones obsolete and remove them...
+test-resolve-by-keep-new-recommends                         # TBD: Fixing this seems to break test-bug-591882-conkeror, why?
+test-resolve-by-keep-obsolete-removals                      # TBD: ResolveByKeep() usage is badly aligned here
+test-ubuntu-bug-1304403-obsolete-priority-standard          # TBD: Solver3 here happily removes 10 deps to upgrade a package
diff --git a/test/integration/test-apt-get-autoremove-real-virtual-provider b/test/integration/test-apt-get-autoremove-real-virtual-provider
index d5438f8b3..7fda4d370 100755
--- a/test/integration/test-apt-get-autoremove-real-virtual-provider
+++ b/test/integration/test-apt-get-autoremove-real-virtual-provider
@@ -31,7 +31,7 @@ The following packages will be REMOVED:
   needs-provider1 needs-provider4
 0 upgraded, 0 newly installed, 2 to remove and 0 not upgraded.
 Remv needs-provider1 [1]
-Remv needs-provider4 [1]' aptget autoremove -s --solver 3.0
+Remv needs-provider4 [1]' aptget autoremove -s --solver 3.1
 
 testsuccessequal 'Reading package lists...
 Building dependency tree...
@@ -39,4 +39,4 @@ Reading state information...
 The following packages will be REMOVED:
   needs-provider4
 0 upgraded, 0 newly installed, 1 to remove and 0 not upgraded.
-Remv needs-provider4 [1]' aptget autoremove -s --solver internal
+Remv needs-provider4 [1]' aptget autoremove -s
diff --git a/test/integration/test-apt-get-build-dep-barbarian b/test/integration/test-apt-get-build-dep-barbarian
index b8ab1211b..48873c59b 100755
--- a/test/integration/test-apt-get-build-dep-barbarian
+++ b/test/integration/test-apt-get-build-dep-barbarian
@@ -83,7 +83,7 @@ testsuccessequal "$(installsfoosamey 'amd64' 'i386')" apt build-dep cool-foo -s
 testsuccessequal "$(installsfoosamey 'i386' 'i386')" apt build-dep bad-amd64-foo -s -a i386
 testsuccessequal "$(installsfoosamey 'amd64' 'i386')" apt build-dep bad-armel-foo -s -a i386
 testsuccessequal "$(installsfoosamey 'i386' 'i386')" apt build-dep bad-amd64-armel-foo -s -a i386
-testfailuremsg 'E: Conflict: builddeps:bad-amd64-i386-foo:i386=1 -> not foo:i386=1 -> not builddeps:bad-amd64-i386-foo:i386=1 but builddeps:bad-amd64-i386-foo:i386=1'  apt build-dep bad-amd64-i386-foo -s -a i386 --solver 3.0
+testfailuremsg 'E: Conflict: builddeps:bad-amd64-i386-foo:i386=1 -> builddeps:bad-amd64-i386-foo:i386 -> not foo:amd64=1 -> not builddeps:bad-amd64-i386-foo:i386 but builddeps:bad-amd64-i386-foo:i386=1 -> builddeps:bad-amd64-i386-foo:i386'  apt build-dep bad-amd64-i386-foo -s -a i386 --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -96,7 +96,7 @@ The following information may help to resolve the situation:
 The following packages have unmet dependencies:
  builddeps:bad-amd64-i386-foo:i386 : Depends: foo:i386
 E: Unable to correct problems, you have held broken packages.' apt build-dep bad-amd64-i386-foo -s -a i386 --solver internal
-testfailuremsg 'E: Conflict: builddeps:bad-amd64-i386-armel-foo:i386=1 -> not foo:i386=1 -> not builddeps:bad-amd64-i386-armel-foo:i386=1 but builddeps:bad-amd64-i386-armel-foo:i386=1' apt build-dep bad-amd64-i386-armel-foo -s -a i386 --solver 3.0
+testfailuremsg 'E: Conflict: builddeps:bad-amd64-i386-armel-foo:i386=1 -> builddeps:bad-amd64-i386-armel-foo:i386 -> not foo:amd64=1 -> not builddeps:bad-amd64-i386-armel-foo:i386 but builddeps:bad-amd64-i386-armel-foo:i386=1 -> builddeps:bad-amd64-i386-armel-foo:i386' apt build-dep bad-amd64-i386-armel-foo -s -a i386 --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -115,7 +115,7 @@ testsuccessequal "$(installsfoosamey 'i386' 'armel')" apt build-dep bad-amd64-fo
 testsuccessequal "$(installsfoosamey 'amd64' 'armel')" apt build-dep bad-armel-foo -s -a armel
 testsuccessequal "$(installsfoosamey 'i386' 'armel')" apt build-dep bad-amd64-armel-foo -s -a armel
 testsuccessequal "$(installsfoosamey 'armel' 'armel')" apt build-dep bad-amd64-i386-foo -s -a armel
-FAILUREMSG="E: Conflict: builddeps:bad-amd64-i386-armel-foo:armel=1 -> not foo:armel=1 -> not builddeps:bad-amd64-i386-armel-foo:armel=1 but builddeps:bad-amd64-i386-armel-foo:armel=1"
+FAILUREMSG="E: Conflict: builddeps:bad-amd64-i386-armel-foo:armel=1 -> builddeps:bad-amd64-i386-armel-foo:armel -> not foo:amd64=1 -> not builddeps:bad-amd64-i386-armel-foo:armel but builddeps:bad-amd64-i386-armel-foo:armel=1 -> builddeps:bad-amd64-i386-armel-foo:armel"
 FAILURE='Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
diff --git a/test/integration/test-apt-get-build-dep-file b/test/integration/test-apt-get-build-dep-file
index bd30cfcfd..8147bb0a3 100755
--- a/test/integration/test-apt-get-build-dep-file
+++ b/test/integration/test-apt-get-build-dep-file
@@ -160,7 +160,7 @@ cd ../..
 
 testfailureequal 'E: Must specify at least one package to check builddeps for' aptget build-dep
 testfailuremsg 'W: No architecture information available for armel. See apt.conf(5) APT::Architectures for setup
-E: Unsatisfiable dependency group builddeps:./foo-1.0:armel=1 -> debhelper:armel' aptget build-dep --simulate ./foo-1.0 -a armel --solver 3.0
+E: Unsatisfiable dependency group builddeps:./foo-1.0:armel -> debhelper:armel' aptget build-dep --simulate ./foo-1.0 -a armel --solver 3.0
 testfailureequal "Note, using directory './foo-1.0' to get the build dependencies
 Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-apt-get-install-deb b/test/integration/test-apt-get-install-deb
index 5599586fd..1540db272 100755
--- a/test/integration/test-apt-get-install-deb
+++ b/test/integration/test-apt-get-install-deb
@@ -32,7 +32,7 @@ done
 
 buildsimplenativepackage 'foo' 'i386,amd64' '1.0'
 
-testfailuremsg "E: Conflict: foo:i386=1.0 -> not foo:amd64=1.0 but foo:amd64=1.0" aptget install ./incoming/foo_1.0_i386.deb ./incoming/foo_1.0_amd64.deb -s --solver 3.0
+testfailuremsg "E: Conflict: foo:amd64=1.0 -> foo:amd64 but foo:i386=1.0 -> not foo:amd64" aptget install ./incoming/foo_1.0_i386.deb ./incoming/foo_1.0_amd64.deb -s --solver 3.0
 testfailureequal "Reading package lists...
 Building dependency tree...
 Note, selecting 'foo:i386' instead of './incoming/foo_1.0_i386.deb'
@@ -177,7 +177,7 @@ echo 'Package: /pkg-/
 Pin: release a=experimental
 Pin-Priority: 501' > rootdir/etc/apt/preferences.d/pinit
 
-testfailuremsg 'E: Unsatisfiable dependency group pkg-last-line-parse:amd64=0 -> pkg-as-it-should-be:amd64' aptget install -q=0 ./incoming/pkg-last-line-parse_0_all.deb --solver 3.0
+testfailuremsg 'E: Unsatisfiable dependency group pkg-last-line-parse:amd64 -> pkg-as-it-should-be:amd64' aptget install -q=0 ./incoming/pkg-last-line-parse_0_all.deb --solver 3.0
 testfailuremsg 'E: Unable to correct problems, you have held broken packages.' aptget install -q=0 ./incoming/pkg-last-line-parse_0_all.deb --solver internal
 testsuccess aptget install ./incoming/pkg-as-it-should-be_0_all.deb
 testsuccess aptget install ./incoming/pkg-last-line-parse_0_all.deb
diff --git a/test/integration/test-apt-get-satisfy b/test/integration/test-apt-get-satisfy
index fc7e8050e..02a444dff 100755
--- a/test/integration/test-apt-get-satisfy
+++ b/test/integration/test-apt-get-satisfy
@@ -80,7 +80,7 @@ testrun 'External' 'Reading package lists...
 Building dependency tree...
 Execute external solver...' --solver apt
 
-testfailuremsg "E: Unsatisfiable dependency group satisfy:command-line:i386=1 -> depends:i386" aptget satisfy --simulate "depends (>= 2)" "Conflicts: conflicts:i386 (>= 1) [i386], conflicts:amd64 (>= 1) [amd64]" --solver 3.0
+testfailuremsg "E: Unsatisfiable dependency group satisfy:command-line:i386 -> depends:i386" aptget satisfy --simulate "depends (>= 2)" "Conflicts: conflicts:i386 (>= 1) [i386], conflicts:amd64 (>= 1) [amd64]" --solver 3.0
 
 testfailureequal "Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-apt-get-source-only b/test/integration/test-apt-get-source-only
index b974146ff..882f82b33 100755
--- a/test/integration/test-apt-get-source-only
+++ b/test/integration/test-apt-get-source-only
@@ -40,7 +40,7 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  builddeps:foo : Depends: foo-bd but it is not installable
-E: Unsatisfiable dependency group builddeps:foo:amd64=1 -> foo-bd:amd64"
+E: Unsatisfiable dependency group builddeps:foo:amd64 -> foo-bd:amd64"
 
 BUILDDEPNOTFOO="Reading package lists...
 Building dependency tree...
@@ -52,7 +52,7 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  builddeps:not-foo : Depends: not-foo-bd but it is not installable
-E: Unsatisfiable dependency group builddeps:not-foo:amd64=1 -> not-foo-bd:amd64"
+E: Unsatisfiable dependency group builddeps:not-foo:amd64 -> not-foo-bd:amd64"
 else
 BUILDDEPFOO="Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-apt-install-file-reltag b/test/integration/test-apt-install-file-reltag
index afbf9bef9..0637c5472 100755
--- a/test/integration/test-apt-install-file-reltag
+++ b/test/integration/test-apt-install-file-reltag
@@ -29,15 +29,20 @@ Standards-Version: 4.1.3
 EOF
 buildsimplenativepackage 'foobar2' 'all' '1' 'unstable' 'Depends: foo (= 5), baz'
 
+testunsat() {
+    testfailure "$@"
+    testsuccess grep -E "^E: (Unable to correct problems,|Conflict:)" "${TMPWORKINGDIRECTORY}/rootdir/tmp/testfailure.output"
+}
+
 ln -s "$(readlink -f ./incoming/foobar2_1_all.deb)" foobar.deb
 mkdir -p foobar
-testfailuremsg 'E: Unable to correct problems, you have held broken packages.' apt build-dep "$(readlink -f ./foobar.dsc)" -s
-testfailuremsg 'E: Unable to correct problems, you have held broken packages.' apt install "$(readlink -f ./foobar.deb)" -s
-testfailuremsg 'E: Unable to correct problems, you have held broken packages.' apt build-dep ./foobar.dsc -s
-testfailuremsg 'E: Unable to correct problems, you have held broken packages.' apt install ./foobar.deb -s
+testunsat apt build-dep "$(readlink -f ./foobar.dsc)" -s
+testunsat apt install "$(readlink -f ./foobar.deb)" -s
+testunsat apt build-dep ./foobar.dsc -s
+testunsat apt install ./foobar.deb -s
 cd foobar
-testfailuremsg 'E: Unable to correct problems, you have held broken packages.' apt build-dep ../foobar.dsc -s
-testfailuremsg 'E: Unable to correct problems, you have held broken packages.' apt install ../foobar.deb -s
+testunsat apt build-dep ../foobar.dsc -s
+testunsat apt install ../foobar.deb -s
 cd ..
 
 SUCCESSDSC='The following NEW packages will be installed:
@@ -84,11 +89,11 @@ $SUCCESSDEB" apt install "../foobar.deb/experimental" -s
 cd ..
 
 msgmsg 'fail with' 'incorrect release'
-testfailuremsg 'E: Unable to correct problems, you have held broken packages.' apt build-dep "$(readlink -f ./foobar.dsc)/stable" -s
-testfailuremsg 'E: Unable to correct problems, you have held broken packages.' apt install "$(readlink -f ./foobar.deb)/stable" -s
-testfailuremsg 'E: Unable to correct problems, you have held broken packages.' apt build-dep ./foobar.dsc/stable -s
-testfailuremsg 'E: Unable to correct problems, you have held broken packages.' apt install ./foobar.deb/stable -s
+testunsat apt build-dep "$(readlink -f ./foobar.dsc)/stable" -s
+testunsat apt install "$(readlink -f ./foobar.deb)/stable" -s
+testunsat apt build-dep ./foobar.dsc/stable -s
+testunsat apt install ./foobar.deb/stable -s
 cd foobar
-testfailuremsg 'E: Unable to correct problems, you have held broken packages.' apt build-dep ../foobar.dsc/stable -s
-testfailuremsg 'E: Unable to correct problems, you have held broken packages.' apt install ../foobar.deb/stable -s
+testunsat apt build-dep ../foobar.dsc/stable -s
+testunsat apt install ../foobar.deb/stable -s
 cd ..
diff --git a/test/integration/test-apt-never-markauto-sections b/test/integration/test-apt-never-markauto-sections
index 33b790871..95ba47553 100755
--- a/test/integration/test-apt-never-markauto-sections
+++ b/test/integration/test-apt-never-markauto-sections
@@ -49,7 +49,7 @@ Remv foreignpkg:i386 [1]
 Remv nosection [1]
 Remv texteditor [1]' aptget autoremove mydesktop -s
 
-testfailuremsg 'E: Conflict: not texteditor:amd64 -> not texteditor:amd64=1 -> not mydesktop-core:amd64=1 but mydesktop:amd64 -> mydesktop-core:amd64=1' aptget autoremove texteditor -s --solver 3.0 #-o Debug::pkgDepCache::AutoInstall=1 -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1
+testfailuremsg 'E: Conflict: not texteditor:amd64 -> not bad-texteditor:amd64 but mydesktop:amd64 -> mydesktop-core:amd64 -> bad-texteditor:amd64' aptget autoremove texteditor -s --solver 3.0 #-o Debug::pkgDepCache::AutoInstall=1 -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1
 testsuccessequal 'Reading package lists...
 Building dependency tree...
 Reading state information...
diff --git a/test/integration/test-bug-549968-install-depends-of-not-installed b/test/integration/test-bug-549968-install-depends-of-not-installed
index ec730c7b2..8abc7c854 100755
--- a/test/integration/test-bug-549968-install-depends-of-not-installed
+++ b/test/integration/test-bug-549968-install-depends-of-not-installed
@@ -37,9 +37,7 @@ Solving dependencies...Install coolstuff:i386 ()
 Delete extracoolstuff:i386
 [0] Reject:extracoolstuff:i386 ()
 [0] Install:coolstuff:i386 (coolstuff:i386=1.0)
-[0] Reject:extracoolstuff:i386=1.0 (not extracoolstuff:i386)
-Optional Item (0@0) coolstuff:i386 ->  | extracoolstuff:i386=1.0
-Optional Item (0@0) coolstuff:i386=1.0 ->  | extracoolstuff:i386=1.0
+Optional Item (0@0) coolstuff:i386 ->  | extracoolstuff:i386
 
 Recommended packages:
   extracoolstuff
diff --git a/test/integration/test-bug-601961-install-info b/test/integration/test-bug-601961-install-info
index 809ebf3c3..6d68372b5 100755
--- a/test/integration/test-bug-601961-install-info
+++ b/test/integration/test-bug-601961-install-info
@@ -60,4 +60,4 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  findutils : Depends: essentialpkg but it is not going to be installed
-E: Conflict: findutils:i386 -> essentialpkg:i386=4.13a.dfsg.1-6 but not essentialpkg:i386 -> not essentialpkg:i386=4.13a.dfsg.1-6' aptget remove essentialpkg --trivial-only --solver 3.0
+E: Conflict: findutils:i386 -> essentialpkg:i386 but not essentialpkg:i386' aptget remove essentialpkg --trivial-only --solver 3.0
diff --git a/test/integration/test-bug-604222-new-and-autoremove b/test/integration/test-bug-604222-new-and-autoremove
index 1090e8b93..70dc4cac3 100755
--- a/test/integration/test-bug-604222-new-and-autoremove
+++ b/test/integration/test-bug-604222-new-and-autoremove
@@ -96,16 +96,15 @@ rm -f rootdir/var/lib/dpkg/status rootdir/var/lib/apt/extended_states
 if [ "$APT_SOLVER" = "3.0" ]; then
 CONFLICTING='Reading package lists...
 Building dependency tree...
-Solving dependencies...MANUAL dummy-archive:i386
+Solving dependencies...Install dummy-archive:i386 ()
 [0] Install:dummy-archive:i386=0.invalid.0 ()
 [0] Install:dummy-archive:i386 (dummy-archive:i386=0.invalid.0)
-[0] Install:libavcodec52:i386=4:0.5.2-6 (dummy-archive:i386=0.invalid.0)
-[0] Install:libavcodec52:i386 (dummy-archive:i386=0.invalid.0 -> libavcodec52:i386=4:0.5.2-6)
-[0] Reject:libvtk5-dev:i386=5.4.2-8 (dummy-archive:i386=0.invalid.0 -> libavcodec52:i386=4:0.5.2-6)
-[0] Reject:libvtk5-dev:i386 (dummy-archive:i386=0.invalid.0 -> libavcodec52:i386=4:0.5.2-6 -> not libvtk5-dev:i386=5.4.2-8)
-Item (1@0) dummy-archive:i386=0.invalid.0 ->  | libvtk5-dev:i386=5.4.2-8 | libopenal-dev:i386=1:1.12.854-2
-[0] Install:libopenal-dev:i386=1:1.12.854-2 (dummy-archive:i386=0.invalid.0)
-[0] Install:libopenal-dev:i386 (dummy-archive:i386=0.invalid.0 -> libopenal-dev:i386=1:1.12.854-2)
+[0] Install:libavcodec52:i386 (dummy-archive:i386=0.invalid.0 -> dummy-archive:i386)
+[0] Install:libavcodec52:i386=4:0.5.2-6 (dummy-archive:i386=0.invalid.0 -> dummy-archive:i386 -> libavcodec52:i386)
+[0] Reject:libvtk5-dev:i386=5.4.2-8 (dummy-archive:i386=0.invalid.0 -> dummy-archive:i386 -> libavcodec52:i386)
+[0] Reject:libvtk5-dev:i386 (dummy-archive:i386=0.invalid.0 -> dummy-archive:i386 -> libavcodec52:i386 -> not libvtk5-dev:i386=5.4.2-8)
+[0] Install:libopenal-dev:i386 (dummy-archive:i386=0.invalid.0 -> dummy-archive:i386)
+[0] Install:libopenal-dev:i386=1:1.12.854-2 (dummy-archive:i386=0.invalid.0 -> dummy-archive:i386 -> libopenal-dev:i386)
 
 The following additional packages will be installed:
   libavcodec52 libopenal-dev
diff --git a/test/integration/test-bug-611729-mark-as-manual b/test/integration/test-bug-611729-mark-as-manual
index bd9af32b6..026ede385 100755
--- a/test/integration/test-bug-611729-mark-as-manual
+++ b/test/integration/test-bug-611729-mark-as-manual
@@ -5,6 +5,7 @@ TESTDIR="$(readlink -f "$(dirname "$0")")"
 . "$TESTDIR/framework"
 setupenvironment
 configarchitecture "i386"
+allowremovemanual
 
 buildsimplenativepackage "peace-dpkg" "all" "1.0" "stable"
 
diff --git a/test/integration/test-bug-612557-garbage-upgrade b/test/integration/test-bug-612557-garbage-upgrade
index f695b499e..4ef241cad 100755
--- a/test/integration/test-bug-612557-garbage-upgrade
+++ b/test/integration/test-bug-612557-garbage-upgrade
@@ -18,7 +18,7 @@ testsuccess aptmark markauto python-uno openoffice.org-common
 testmarkedauto python-uno openoffice.org-common
 
 # The 3.0 solver does not remove openoffice.org-emailmerge because it is manually installed.
-testfailuremsg "E: Conflict: python-uno:i386=1:3.3.0-2 -> libreoffice-common:i386=1:3.3.0-2 -> not openoffice.org-common:i386=1:3.2.1-11+squeeze2 but openoffice.org-emailmerge:i386 -> openoffice.org-common:i386=1:3.2.1-11+squeeze2" aptget --trivial-only install python-uno --solver 3.0
+testfailuremsg "E: Conflict: openoffice.org-emailmerge:i386 -> openoffice.org-common:i386 -> openoffice.org-common:i386=1:3.2.1-11+squeeze2 but python-uno:i386=1:3.3.0-2 -> libreoffice-common:i386 -> not openoffice.org-common:i386=1:3.2.1-11+squeeze2" aptget --trivial-only install python-uno --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Reading state information...
diff --git a/test/integration/test-bug-618848-always-respect-user-requests b/test/integration/test-bug-618848-always-respect-user-requests
index 90965eb22..d59491af6 100755
--- a/test/integration/test-bug-618848-always-respect-user-requests
+++ b/test/integration/test-bug-618848-always-respect-user-requests
@@ -14,7 +14,7 @@ insertpackage 'unstable' 'exim4-daemon-heavy' 'all' '1.0' 'Depends: libdb4.8'
 setupaptarchive
 
 # This does not work in 3.0 solver: We do not remove manually installed packages.
-testfailuremsg "E: Conflict: exim4-daemon-light:i386 -> libdb4.8:i386=1.0 but not libdb4.8:i386 -> not libdb4.8:i386=1.0" aptget remove libdb4.8 --solver 3.0 -s
+testfailuremsg "E: Conflict: not libdb4.8:i386 -> not exim4-daemon-light:i386 but exim4-daemon-light:i386" aptget remove libdb4.8 --solver 3.0 -s
 allowremovemanual
 testsuccessequal "Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-632221-cross-dependency-satisfaction b/test/integration/test-bug-632221-cross-dependency-satisfaction
index 90cb8684f..d101bd1fa 100755
--- a/test/integration/test-bug-632221-cross-dependency-satisfaction
+++ b/test/integration/test-bug-632221-cross-dependency-satisfaction
@@ -35,7 +35,7 @@ insertsource 'unstable' 'source-specific-armel' 'armel' '1' 'Build-Depends: spec
 
 setupaptarchive
 
-testfailuremsg "E: Unsatisfiable dependency group builddeps:forbidden-no:armel=1 -> amdboot:any:any" aptget build-dep forbidden-no -s -a armel --solver 3.0
+testfailuremsg "E: Unsatisfiable dependency group builddeps:forbidden-no:armel -> amdboot:any:any" aptget build-dep forbidden-no -s -a armel --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -49,7 +49,7 @@ The following packages have unmet dependencies:
  builddeps:forbidden-no:armel : Depends: amdboot:any but it is not installable
 E: Unable to correct problems, you have held broken packages.' aptget build-dep forbidden-no -s -a armel --solver internal
 
-testfailuremsg "E: Unsatisfiable dependency group builddeps:forbidden-same:armel=1 -> libc6:any:any" aptget build-dep forbidden-same -s -a armel --solver 3.0
+testfailuremsg "E: Unsatisfiable dependency group builddeps:forbidden-same:armel -> libc6:any:any" aptget build-dep forbidden-same -s -a armel --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -63,7 +63,7 @@ The following packages have unmet dependencies:
  builddeps:forbidden-same:armel : Depends: libc6:any but it is not installable
 E: Unable to correct problems, you have held broken packages.' aptget build-dep forbidden-same -s -a armel --solver internal
 
-testfailuremsg 'E: Unsatisfiable dependency group builddeps:forbidden-foreign:armel=1 -> doxygen:any:any' aptget build-dep forbidden-foreign -s -a armel --solver 3.0
+testfailuremsg 'E: Unsatisfiable dependency group builddeps:forbidden-foreign:armel -> doxygen:any:any' aptget build-dep forbidden-foreign -s -a armel --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-64141-install-dependencies-for-on-hold b/test/integration/test-bug-64141-install-dependencies-for-on-hold
index 1ad1952f7..ddfad92af 100755
--- a/test/integration/test-bug-64141-install-dependencies-for-on-hold
+++ b/test/integration/test-bug-64141-install-dependencies-for-on-hold
@@ -34,7 +34,7 @@ After this operation, 0 B of additional disk space will be used.
 E: Trivial Only specified but this is not a trivial operation.' aptget dist-upgrade --trivial-only --solver 3.0
 
 testfailure aptget dist-upgrade --trivial-only --solver 3.0 -o debug::apt::solver=2
-testsuccess grep -Fx "Branch failed: Conflict: apt:$native -> apt:$native=0.8.10 -> not oldcrap:$native=1-1 but oldcrap:$native -> oldcrap:$native=1-1" rootdir/tmp/testfailure.output
+testsuccess grep -Fx "[0] Reject:apt:$native=0.8.10 (oldcrap:$native -> oldcrap:$native=1-1)" rootdir/tmp/testfailure.output
 
 allowremovemanual
 
diff --git a/test/integration/test-bug-675449-essential-are-protected b/test/integration/test-bug-675449-essential-are-protected
index e7460aeb7..36e7b645e 100755
--- a/test/integration/test-bug-675449-essential-are-protected
+++ b/test/integration/test-bug-675449-essential-are-protected
@@ -112,4 +112,17 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  foo : Depends: libfoo but it is not going to be installed
-E: Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.' aptget purge libfoo -s
+E: Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.' aptget purge libfoo -s --solver internal
+
+testequal 'Reading package lists...
+Building dependency tree...
+Solving dependencies...
+Some packages could not be installed. This may mean that you have
+requested an impossible situation or if you are using the unstable
+distribution that some required packages have not yet been created
+or been moved out of Incoming.
+The following information may help to resolve the situation:
+
+The following packages have unmet dependencies:
+ foo : Depends: libfoo but it is not going to be installed
+E: Conflict: foo:amd64 -> libfoo:amd64 but not libfoo:amd64' aptget purge libfoo -s --solver 3.0
diff --git a/test/integration/test-bug-683786-build-dep-on-virtual-packages b/test/integration/test-bug-683786-build-dep-on-virtual-packages
index 45e40e20e..75f0a9626 100755
--- a/test/integration/test-bug-683786-build-dep-on-virtual-packages
+++ b/test/integration/test-bug-683786-build-dep-on-virtual-packages
@@ -41,7 +41,7 @@ The following NEW packages will be installed:
 Inst po-debconf (1 unstable [all])
 Conf po-debconf (1 unstable [all])' aptget build-dep dash -s
 
-testfailuremsg 'E: Unsatisfiable dependency group builddeps:dash:armel=1 -> po-debconf:armel' aptget build-dep -aarmel dash -s --solver 3.0
+testfailuremsg 'E: Unsatisfiable dependency group builddeps:dash:armel -> po-debconf:armel' aptget build-dep -aarmel dash -s --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -55,7 +55,7 @@ The following packages have unmet dependencies:
  builddeps:dash:armel : Depends: po-debconf:armel but it is not installable
 E: Unable to correct problems, you have held broken packages.' aptget build-dep -aarmel dash -s --solver internal
 
-testfailuremsg 'E: Unsatisfiable dependency group builddeps:diffutils:armel=1 -> texi2html:armel' aptget build-dep -aarmel diffutils -s --solver 3.0
+testfailuremsg 'E: Unsatisfiable dependency group builddeps:diffutils:armel -> texi2html:armel' aptget build-dep -aarmel diffutils -s --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -78,7 +78,7 @@ The following NEW packages will be installed:
 Inst libselinux1-dev (1 unstable [amd64])
 Conf libselinux1-dev (1 unstable [amd64])" aptget build-dep sed -s
 
-testfailuremsg 'E: Unsatisfiable dependency group builddeps:sed:armel=1 -> libselinux-dev:armel' aptget build-dep -aarmel sed -s --solver 3.0
+testfailuremsg 'E: Unsatisfiable dependency group builddeps:sed:armel -> libselinux-dev:armel' aptget build-dep -aarmel sed -s --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-712116-dpkg-pre-install-pkgs-hook-multiarch b/test/integration/test-bug-712116-dpkg-pre-install-pkgs-hook-multiarch
index 3bad6174a..b9cda188f 100755
--- a/test/integration/test-bug-712116-dpkg-pre-install-pkgs-hook-multiarch
+++ b/test/integration/test-bug-712116-dpkg-pre-install-pkgs-hook-multiarch
@@ -90,8 +90,7 @@ stuff 2 amd64 none > - - none **REMOVE**'
 	testfileequal "${hook}-v2.list" 'libsame 2 > - **REMOVE**'
 	testfileequal "${hook}-v3.list" 'libsame 2 amd64 same > - - none **REMOVE**'
 
-	# FIXME: solver3: This should not require no-strict-pinning
-	observehook install stuff:i386/stable libsame:i386/stable toolkit/stable $(test "$APT_SOLVER" != "3.0" || printf '%s' '--no-strict-pinning')
+	observehook install stuff:i386/stable libsame:i386/stable toolkit/stable
 	testfileequal "${hook}-v2.list" 'libsame 2 > 1 **CONFIGURE**
 stuff 2 > 1 **CONFIGURE**
 toolkit 2 > 1 **CONFIGURE**'
diff --git a/test/integration/test-bug-723586-any-stripped-in-single-arch b/test/integration/test-bug-723586-any-stripped-in-single-arch
index 441bc29c2..17c3839d1 100755
--- a/test/integration/test-bug-723586-any-stripped-in-single-arch
+++ b/test/integration/test-bug-723586-any-stripped-in-single-arch
@@ -41,7 +41,7 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  python-mips : Depends: python3:mips but it is not installable
-E: Unsatisfiable dependency group python-mips:amd64=3 -> python3:mips:any'
+E: Unsatisfiable dependency group python-mips:amd64 -> python3:mips:any'
 else
 FAILLOG='Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-735967-lib32-to-i386-unavailable b/test/integration/test-bug-735967-lib32-to-i386-unavailable
index a44e58570..2eedf22ab 100755
--- a/test/integration/test-bug-735967-lib32-to-i386-unavailable
+++ b/test/integration/test-bug-735967-lib32-to-i386-unavailable
@@ -50,7 +50,7 @@ Remv lib32nss-mdns [0.9-1]
 Inst libnss-mdns [0.9-1] (0.10-6 unstable [amd64])
 Conf libnss-mdns (0.10-6 unstable [amd64])' aptget dist-upgrade -s --solver internal
 
-testfailuremsg 'E: Unsatisfiable dependency group libfoo:amd64=1 -> libfoo-bin:amd64' aptget install foo -s --solver 3.0
+testfailuremsg 'E: Unsatisfiable dependency group libfoo:amd64 -> libfoo-bin:amd64' aptget install foo -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
diff --git a/test/integration/test-bug-745046-candidate-propagation-fails b/test/integration/test-bug-745046-candidate-propagation-fails
index 64aaa6ac8..a8ee50124 100755
--- a/test/integration/test-bug-745046-candidate-propagation-fails
+++ b/test/integration/test-bug-745046-candidate-propagation-fails
@@ -25,7 +25,21 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  gedit : Depends: common (>= 2) but it is not installable
-E: Unable to correct problems, you have held broken packages." aptget install gedit/experimental -sq=0
+E: Unable to correct problems, you have held broken packages." aptget install gedit/experimental -sq=0 --solver internal
+
+testfailureequal "Reading package lists...
+Building dependency tree...
+Selected version '2' (experimental [amd64]) for 'gedit'
+Solving dependencies...
+Some packages could not be installed. This may mean that you have
+requested an impossible situation or if you are using the unstable
+distribution that some required packages have not yet been created
+or been moved out of Incoming.
+The following information may help to resolve the situation:
+
+The following packages have unmet dependencies:
+ gedit : Depends: common (>= 2) but it is not installable
+E: Unsatisfiable dependency group gedit:amd64=2 -> common:amd64" aptget install gedit/experimental -sq=0 --solver 3.0
 
 insertinstalledpackage 'common' 'amd64' '2'
 
diff --git a/test/integration/test-bug-960705-propagate-protected-to-satisfied-depends b/test/integration/test-bug-960705-propagate-protected-to-satisfied-depends
index e5a12986d..492958cb3 100755
--- a/test/integration/test-bug-960705-propagate-protected-to-satisfied-depends
+++ b/test/integration/test-bug-960705-propagate-protected-to-satisfied-depends
@@ -23,20 +23,16 @@ Building dependency tree...
 Solving dependencies...Install foobar:amd64 ()
 [0] Install:foobar:amd64=1 ()
 [0] Install:foobar:amd64 (foobar:amd64=1)
-[0] Install:requires-foo:amd64=1 (foobar:amd64=1)
-[0] Install:requires-foo:amd64 (foobar:amd64=1 -> requires-foo:amd64=1)
-[0] Install:foo:amd64=1 (foobar:amd64=1 -> requires-foo:amd64=1)
-[0] Install:foo:amd64 (foobar:amd64=1 -> requires-foo:amd64=1 -> foo:amd64=1)
-[0] Install:foo-depends:amd64=1 (foobar:amd64=1 -> requires-foo:amd64=1 -> foo:amd64=1)
-[0] Install:foo-depends:amd64 (foobar:amd64=1 -> requires-foo:amd64=1 -> foo:amd64=1 -> foo-depends:amd64=1)
-Item (2@0) foobar:amd64=1 ->  | conflicts-foo:amd64=1 | fine-foo:amd64=1
-[1] Install:conflicts-foo:amd64=1 (foobar:amd64=1)
-[1] Install:conflicts-foo:amd64 (foobar:amd64=1 -> conflicts-foo:amd64=1)
-[0] Reject:conflicts-foo:amd64=1 ()
-[0] Reject:conflicts-foo:amd64 (not conflicts-foo:amd64=1)
-Item (1@0) foobar:amd64=1 ->  | conflicts-foo:amd64=1 | fine-foo:amd64=1
-[0] Install:fine-foo:amd64=1 (foobar:amd64=1)
-[0] Install:fine-foo:amd64 (foobar:amd64=1 -> fine-foo:amd64=1)
+[0] Install:requires-foo:amd64 (foobar:amd64=1 -> foobar:amd64)
+[0] Install:requires-foo:amd64=1 (foobar:amd64=1 -> foobar:amd64 -> requires-foo:amd64)
+[0] Install:foo:amd64 (foobar:amd64=1 -> foobar:amd64 -> requires-foo:amd64)
+[0] Install:foo:amd64=1 (foobar:amd64=1 -> foobar:amd64 -> requires-foo:amd64 -> foo:amd64)
+[0] Install:foo-depends:amd64 (foobar:amd64=1 -> foobar:amd64 -> requires-foo:amd64 -> foo:amd64)
+[0] Reject:conflicts-foo:amd64 (foobar:amd64=1 -> foobar:amd64 -> requires-foo:amd64 -> foo:amd64 -> foo:amd64=1)
+[0] Install:foo-depends:amd64=1 (foobar:amd64=1 -> foobar:amd64 -> requires-foo:amd64 -> foo:amd64 -> foo-depends:amd64)
+[0] Install:fine-foo:amd64 (foobar:amd64=1 -> foobar:amd64)
+[0] Reject:conflicts-foo:amd64=1 (foobar:amd64=1 -> foobar:amd64 -> requires-foo:amd64 -> foo:amd64 -> foo:amd64=1 -> not conflicts-foo:amd64)
+[0] Install:fine-foo:amd64=1 (foobar:amd64=1 -> foobar:amd64 -> fine-foo:amd64)
 
 The following additional packages will be installed:
   fine-foo foo foo-depends requires-foo
diff --git a/test/integration/test-bug-961266-hold-means-hold b/test/integration/test-bug-961266-hold-means-hold
index 89c18ba85..8c18cd757 100755
--- a/test/integration/test-bug-961266-hold-means-hold
+++ b/test/integration/test-bug-961266-hold-means-hold
@@ -75,7 +75,21 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  git-ng : Depends: git (> 1:2.26.2)
-E: Unable to correct problems, you have held broken packages.' apt install git-ng -s
+E: Unable to correct problems, you have held broken packages.' apt install git-ng -s --solver internal
+
+
+testfailureequal 'Reading package lists...
+Building dependency tree...
+Solving dependencies...
+Some packages could not be installed. This may mean that you have
+requested an impossible situation or if you are using the unstable
+distribution that some required packages have not yet been created
+or been moved out of Incoming.
+The following information may help to resolve the situation:
+
+The following packages have unmet dependencies:
+ git-ng : Depends: git (> 1:2.26.2)
+E: Conflict: git:amd64=1:2.25.1-1 -> not git:amd64=1:2.26.2-1 -> not git-ng:amd64 but git-ng:amd64=1:2.26.2-1 -> git-ng:amd64' apt install git-ng -s --solver 3.0
 
 
 msgmsg 'Now mix it up by' 'holding git-cvs'
@@ -98,7 +112,21 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  git-cvs : Depends: git (< 1:2.25.1-.)
-E: Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.' apt install git-ng -s
+E: Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.' apt install git-ng -s --solver internal
+
+
+testfailureequal 'Reading package lists...
+Building dependency tree...
+Solving dependencies...
+Some packages could not be installed. This may mean that you have
+requested an impossible situation or if you are using the unstable
+distribution that some required packages have not yet been created
+or been moved out of Incoming.
+The following information may help to resolve the situation:
+
+The following packages have unmet dependencies:
+ git-ng : Depends: git (> 1:2.26.2)
+E: Conflict: git-cvs:amd64=1:2.25.1-1 -> git:amd64=1:2.25.1-1 -> not git:amd64=1:2.26.2-1 but git-ng:amd64=1:2.26.2-1 -> git-ng:amd64 -> git:amd64=1:2.26.2-1' apt install git-ng -s --solver 3.0
 
 
 msgmsg 'Now mix it up by' 'holding both'
@@ -121,4 +149,17 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  git-ng : Depends: git (> 1:2.26.2)
-E: Unable to correct problems, you have held broken packages.' apt install git-ng -s
+E: Unable to correct problems, you have held broken packages.' apt install git-ng -s --solver internal
+
+testfailureequal 'Reading package lists...
+Building dependency tree...
+Solving dependencies...
+Some packages could not be installed. This may mean that you have
+requested an impossible situation or if you are using the unstable
+distribution that some required packages have not yet been created
+or been moved out of Incoming.
+The following information may help to resolve the situation:
+
+The following packages have unmet dependencies:
+ git-ng : Depends: git (> 1:2.26.2)
+E: Conflict: git:amd64=1:2.25.1-1 -> not git:amd64=1:2.26.2-1 -> not git-ng:amd64 but git-ng:amd64=1:2.26.2-1 -> git-ng:amd64' apt install git-ng -s --solver 3.0
diff --git a/test/integration/test-dont-forget-conflicts-via-unknown-architectures b/test/integration/test-dont-forget-conflicts-via-unknown-architectures
index 07d5d8f84..f8b41c69a 100755
--- a/test/integration/test-dont-forget-conflicts-via-unknown-architectures
+++ b/test/integration/test-dont-forget-conflicts-via-unknown-architectures
@@ -6,6 +6,7 @@ TESTDIR="$(readlink -f "$(dirname "$0")")"
 setupenvironment
 configarchitecture 'arm64'
 configdpkgnoopchroot
+allowremovemanual
 
 buildsimplenativepackage 'pkga' 'arm64' '1' 'stable'
 buildsimplenativepackage 'pkgb' 'arm64' '1' 'stable'
@@ -38,6 +39,6 @@ testsuccess apt update
 
 #apt upgrade pkga -o Debug::pkgDpkgPm=1 -y -o Dpkg::use-pty=0
 rm -f rootdir/var/cache/apt/*.bin
-testsuccess apt upgrade pkga -y
+testsuccess apt install pkga -y
 testdpkginstalled 'pkga'
 testdpkgnotinstalled 'pkgb'
diff --git a/test/integration/test-explore-or-groups-in-markinstall b/test/integration/test-explore-or-groups-in-markinstall
index fe7e998be..4c67296d7 100755
--- a/test/integration/test-explore-or-groups-in-markinstall
+++ b/test/integration/test-explore-or-groups-in-markinstall
@@ -55,7 +55,11 @@ _testsuccessheadtailequal() {
 	msggroup
 }
 testsuccessheadequal() {
-	_testsuccessheadtailequal 'head' "$@"
+    msg="$1"
+    shift
+	testsuccess "$@"
+    cp "${TMPWORKINGDIRECTORY}/rootdir/tmp/testsuccess.output" "${TMPWORKINGDIRECTORY}/rootdir/tmp/testsuccess-no-sim-equal.output"
+    testsuccessequal "$msg" awk '{print} /not upgraded.$/ {exit}' "${TMPWORKINGDIRECTORY}/rootdir/tmp/testsuccess-no-sim-equal.output"
 }
 testsuccesstailequal() {
 	_testsuccessheadtailequal 'tail' "$@"
@@ -63,14 +67,14 @@ testsuccesstailequal() {
 checkfoos() {
 	msgmsg 'Install checks with foos dependency type' "$2"
 	for level in 0 1 2; do
-		testsuccessheadequal 7 "Reading package lists...
+		testsuccessheadequal "Reading package lists...
 Building dependency tree...
 The following additional packages will be installed:
   okay
 The following NEW packages will be installed:
   foo-${1}-level${level} okay
 0 upgraded, 2 newly installed, 0 to remove and 3 not upgraded." apt install foo-${1}-level${level} -s
-		testsuccessheadequal 9 "Reading package lists...
+		testsuccessheadequal "Reading package lists...
 Building dependency tree...
 The following additional packages will be installed:
   upgrade
@@ -81,7 +85,7 @@ The following packages will be upgraded:
 1 upgraded, 1 newly installed, 0 to remove and 2 not upgraded." apt install foo-${1}-upgrade-level${level} -s
 	done
 
-	testsuccessheadequal 7 "Reading package lists...
+	testsuccessheadequal "Reading package lists...
 Building dependency tree...
 The following additional packages will be installed:
   okay
@@ -90,7 +94,8 @@ The following NEW packages will be installed:
 0 upgraded, 2 newly installed, 0 to remove and 3 not upgraded." apt install foo-${1}-conflict -s
 }
 checkfoos 'd' 'Depends'
-checkfoos 'r' 'Recommends'
+# FIXME? The 3.0 solver solves Recommends after Depends, so they do not influence our decisions here.
+[ "$APT_SOLVER" = "3.0" ] || checkfoos 'r' 'Recommends'
 
 testsuccessequal 'Reading package lists...
 Building dependency tree...
@@ -124,9 +129,9 @@ if $TEST_WITH_APTITUDE; then
 Need to get 0 B/84 B of archives. After unpacking 86.0 kB will be used.
 Would download/install/remove packages.'
 	testsuccesstailequal 3 "$OKAYAPTITUDE" aptitude install foo-d-level2 -sy
-	testsuccesstailequal 3 "$OKAYAPTITUDE" aptitude install foo-r-level2 -sy
+	[ "$APT_SOLVER" = "3.0" ] || testsuccesstailequal 3 "$OKAYAPTITUDE" aptitude install foo-r-level2 -sy   # FIXME: See above for 3.0
 	testsuccesstailequal 3 "$OKAYAPTITUDE" aptitude install foo-d-conflict -sy
-	testsuccesstailequal 3 "$OKAYAPTITUDE" aptitude install foo-r-conflict -sy
+	[ "$APT_SOLVER" = "3.0" ] || testsuccesstailequal 3 "$OKAYAPTITUDE" aptitude install foo-r-conflict -sy # FIXME: See above for 3.0
 fi
 
 BADSOLVETEXT='Reading package lists...
@@ -137,17 +142,36 @@ distribution that some required packages have not yet been created
 or been moved out of Incoming.
 The following information may help to resolve the situation:
 '
+BADSOLVETEXT3='Reading package lists...
+Building dependency tree...
+Solving dependencies...
+Some packages could not be installed. This may mean that you have
+requested an impossible situation or if you are using the unstable
+distribution that some required packages have not yet been created
+or been moved out of Incoming.
+The following information may help to resolve the situation:
+'
 
 testfailureequal "$BADSOLVETEXT
 The following packages have unmet dependencies:
  bad-level0 : Depends: unknown but it is not installable
  bad-upgrade-level0 : Depends: unknown but it is not installable
-E: Unable to correct problems, you have held broken packages." apt install bad-upgrade-level1 -s
+E: Unable to correct problems, you have held broken packages." apt install bad-upgrade-level1 -s --solver internal
+testfailureequal "$BADSOLVETEXT3
+The following packages have unmet dependencies:
+ bad-upgrade-level1 : Depends: bad-upgrade-level0 (>= 2) but 1 is to be installed
+                      Depends: unneeded2 but it is not going to be installed
+E: Unsatisfiable dependency group bad-upgrade-level0:amd64=2 -> unknown:amd64" apt install bad-upgrade-level1 -s --solver 3.0
 testfailureequal "$BADSOLVETEXT
 The following packages have unmet dependencies:
  bad-conflict-level0 : Conflicts: bad-conflict-level2 but 1 is to be installed
  bad-level0 : Depends: unknown but it is not installable
-E: Unable to correct problems, you have held broken packages." apt install bad-conflict-level2 -s
+E: Unable to correct problems, you have held broken packages." apt install bad-conflict-level2 -s --solver internal
+testfailureequal "$BADSOLVETEXT3
+The following packages have unmet dependencies:
+ bad-conflict-level2 : Depends: bad-conflict-level1 but it is not going to be installed
+                       Depends: unneeded2 but it is not going to be installed
+E: Conflict: bad-conflict-level2:amd64=1 -> not bad-conflict-level0:amd64 -> not bad-conflict-level1:amd64 but bad-conflict-level2:amd64=1 -> bad-conflict-level2:amd64 -> bad-conflict-level1:amd64" apt install bad-conflict-level2 -s --solver 3.0
 
 if $TEST_WITH_APTITUDE; then
 	testsuccesstailequal 6 'The following packages have been kept back:
diff --git a/test/integration/test-external-dependency-solver-protocol b/test/integration/test-external-dependency-solver-protocol
index 75fc75b92..81204fc19 100755
--- a/test/integration/test-external-dependency-solver-protocol
+++ b/test/integration/test-external-dependency-solver-protocol
@@ -5,6 +5,7 @@ TESTDIR="$(readlink -f "$(dirname "$0")")"
 . "$TESTDIR/framework"
 setupenvironment
 configarchitecture 'amd64' 'i386'
+allowremovemanual
 
 insertinstalledpackage 'cool' 'all' '1'
 insertinstalledpackage 'stuff' 'all' '1'
diff --git a/test/integration/test-handling-broken-orgroups b/test/integration/test-handling-broken-orgroups
index 50b158752..f9c436f81 100755
--- a/test/integration/test-handling-broken-orgroups
+++ b/test/integration/test-handling-broken-orgroups
@@ -47,7 +47,7 @@ Inst coolstuff2 (1.0-1 unstable [all])
 Conf stuff (1.0-1 unstable [all])
 Conf coolstuff2 (1.0-1 unstable [all])' aptget install coolstuff2 -s
 
-testfailuremsg 'E: Unsatisfiable dependency group coolstuff-broken:i386=1.0-1 -> cool2:i386' aptget install coolstuff-broken --solver 3.0 -s
+testfailuremsg 'E: Unsatisfiable dependency group coolstuff-broken:i386 -> cool2:i386' aptget install coolstuff-broken --solver 3.0 -s
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -95,7 +95,7 @@ Inst coolstuff-provided (1.0-1 unstable [all])
 Conf extrastuff (1.0-1 unstable [all])
 Conf coolstuff-provided (1.0-1 unstable [all])' aptget install coolstuff-provided -s
 
-testfailuremsg 'E: Conflict: coolstuff-provided-broken:i386=1.0-1 -> extrastuff:i386=1.0-1 but not extrastuff:i386=1.0-1' aptget install coolstuff-provided-broken --solver 3.0 -s
+testfailuremsg 'E: Conflict: coolstuff-provided-broken:i386=1.0-1 -> coolstuff-provided-broken:i386 -> extrastuff:i386=1.0-1 but not extrastuff:i386=1.0-1' aptget install coolstuff-provided-broken --solver 3.0 -s
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
diff --git a/test/integration/test-ignore-provides-if-versioned-breaks b/test/integration/test-ignore-provides-if-versioned-breaks
index 0263e8567..27197e1e6 100755
--- a/test/integration/test-ignore-provides-if-versioned-breaks
+++ b/test/integration/test-ignore-provides-if-versioned-breaks
@@ -32,7 +32,7 @@ insertpackage 'unstable' 'foo-same-breaker-none' 'i386' '1.0' 'Breaks: foo-same'
 
 
 setupaptarchive
-testfailuremsg 'E: Conflict: foo-breaker-none:i386=1.0 -> not foo-provider:i386=1.0 but foo-provider:i386=1.0' aptget install foo-provider foo-breaker-none -s --solver 3.0
+testfailuremsg 'E: Conflict: foo-provider:i386=1.0 -> not foo-breaker-none:i386 but foo-breaker-none:i386=1.0 -> foo-breaker-none:i386' aptget install foo-provider foo-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -71,7 +71,7 @@ Conf foo (4.0 unstable [i386])
 Conf foo-breaker-3 (1.0 unstable [i386])
 Conf foo-provider (1.0 unstable [i386])' aptget install foo-provider foo-breaker-3 -s
 
-testfailuremsg 'E: Conflict: foo-foreign-breaker-none:i386=1.0 -> not foo-foreign-provider:i386=1.0 but foo-foreign-provider:i386=1.0' aptget install foo-foreign-provider foo-foreign-breaker-none -s --solver 3.0
+testfailuremsg 'E: Conflict: foo-foreign-breaker-none:i386=1.0 -> foo-foreign-breaker-none:i386 -> not foo-foreign-provider:i386=1.0 but foo-foreign-provider:i386=1.0' aptget install foo-foreign-provider foo-foreign-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -110,7 +110,7 @@ Conf foo-foreign:amd64 (4.0 unstable [amd64])
 Conf foo-foreign-breaker-3 (1.0 unstable [i386])
 Conf foo-foreign-provider (1.0 unstable [i386])' aptget install foo-foreign-provider foo-foreign-breaker-3 -s
 
-testfailuremsg 'E: Conflict: foo-same-breaker-none:i386=1.0 -> not foo-same-provider:i386=1.0 but foo-same-provider:i386=1.0' aptget install foo-same-provider foo-same-breaker-none -s --solver 3.0
+testfailuremsg 'E: Conflict: foo-same-provider:i386=1.0 -> not foo-same-breaker-none:i386 but foo-same-breaker-none:i386=1.0 -> foo-same-breaker-none:i386' aptget install foo-same-provider foo-same-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
diff --git a/test/integration/test-ignore-provides-if-versioned-conflicts b/test/integration/test-ignore-provides-if-versioned-conflicts
index 7f0c357fa..caff5e3b0 100755
--- a/test/integration/test-ignore-provides-if-versioned-conflicts
+++ b/test/integration/test-ignore-provides-if-versioned-conflicts
@@ -33,7 +33,7 @@ insertpackage 'unstable' 'foo-same-breaker-none' 'i386' '1.0' 'Conflicts: foo-sa
 
 setupaptarchive
 
-testfailuremsg 'E: Conflict: foo-breaker-none:i386=1.0 -> not foo-provider:i386=1.0 but foo-provider:i386=1.0' aptget install foo-provider foo-breaker-none -s --solver 3.0
+testfailuremsg 'E: Conflict: foo-provider:i386=1.0 -> not foo-breaker-none:i386 but foo-breaker-none:i386=1.0 -> foo-breaker-none:i386' aptget install foo-provider foo-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -72,7 +72,7 @@ Conf foo (4.0 unstable [i386])
 Conf foo-breaker-3 (1.0 unstable [i386])
 Conf foo-provider (1.0 unstable [i386])' aptget install foo-provider foo-breaker-3 -s
 
-testfailuremsg 'E: Conflict: foo-foreign-breaker-none:i386=1.0 -> not foo-foreign-provider:i386=1.0 but foo-foreign-provider:i386=1.0' aptget install foo-foreign-provider foo-foreign-breaker-none -s --solver 3.0
+testfailuremsg 'E: Conflict: foo-foreign-breaker-none:i386=1.0 -> foo-foreign-breaker-none:i386 -> not foo-foreign-provider:i386=1.0 but foo-foreign-provider:i386=1.0' aptget install foo-foreign-provider foo-foreign-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -111,7 +111,7 @@ Conf foo-foreign:amd64 (4.0 unstable [amd64])
 Conf foo-foreign-breaker-3 (1.0 unstable [i386])
 Conf foo-foreign-provider (1.0 unstable [i386])' aptget install foo-foreign-provider foo-foreign-breaker-3 -s
 
-testfailuremsg 'E: Conflict: foo-same-breaker-none:i386=1.0 -> not foo-same-provider:i386=1.0 but foo-same-provider:i386=1.0' aptget install foo-same-provider foo-same-breaker-none -s --solver 3.0
+testfailuremsg 'E: Conflict: foo-same-provider:i386=1.0 -> not foo-same-breaker-none:i386 but foo-same-breaker-none:i386=1.0 -> foo-same-breaker-none:i386' aptget install foo-same-provider foo-same-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
diff --git a/test/integration/test-multiarch-allowed b/test/integration/test-multiarch-allowed
index 4b795bd5e..9d8920e0f 100755
--- a/test/integration/test-multiarch-allowed
+++ b/test/integration/test-multiarch-allowed
@@ -64,18 +64,18 @@ Inst needsfoo:i386 (1 unstable [i386])
 Conf foo:i386 (1 unstable [i386])
 Conf needsfoo:i386 (1 unstable [i386])' aptget install needsfoo:i386 -s
 # FIXME: same problem, but two different unmet dependency messages depending on install order
-testfailuremsg "E: Conflict: needsfoo:i386=1 -> foo:i386=1 but foo:amd64=1 -> not foo:i386=1" aptget install needsfoo:i386 foo:amd64 -s --solver 3.0
+testfailuremsg "E: Conflict: foo:amd64=1 -> not foo:i386 -> not needsfoo:i386 but needsfoo:i386=1 -> needsfoo:i386" aptget install needsfoo:i386 foo:amd64 -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  foo : Conflicts: foo:i386 but 1 is to be installed
  foo:i386 : Conflicts: foo but 1 is to be installed
 E: Unable to correct problems, you have held broken packages." aptget install needsfoo:i386 foo:amd64 -s --solver internal
-testfailuremsg "E: Conflict: needsfoo:i386=1 -> foo:i386=1 but foo:amd64=1 -> not foo:i386=1" aptget install foo:amd64 needsfoo:i386 -s --solver 3.0
+testfailuremsg "E: Conflict: foo:amd64=1 -> not foo:i386 -> not needsfoo:i386 but needsfoo:i386=1 -> needsfoo:i386" aptget install foo:amd64 needsfoo:i386 -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  needsfoo:i386 : Depends: foo:i386 but it is not installable
 E: Unable to correct problems, you have held broken packages." aptget install foo:amd64 needsfoo:i386 -s --solver internal
-testfailuremsg "E: Conflict: needsfoo:amd64=1 -> foo:amd64=1 but foo:i386=1 -> not foo:amd64=1" aptget install needsfoo foo:i386 -s --solver 3.0
+testfailuremsg "E: Conflict: foo:i386=1 -> not foo:amd64 -> not needsfoo:amd64 but needsfoo:amd64=1 -> needsfoo:amd64" aptget install needsfoo foo:i386 -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  foo : Conflicts: foo:i386 but 1 is to be installed
@@ -135,11 +135,11 @@ if [ "$APT_SOLVER" = "3.0" ]; then
 NEEDSFOO2NATIVE="$BADPREFIX
 The following packages have unmet dependencies:
  needsfoover2 : Depends: foo:any (>= 2)
-E: Unsatisfiable dependency group needsfoover2:amd64=1 -> foo:any:any"
+E: Unsatisfiable dependency group needsfoover2:amd64 -> foo:any:any"
 NEEDSFOO2FOREIGN="$BADPREFIX
 The following packages have unmet dependencies:
  needsfoover2:i386 : Depends: foo:any (>= 2)
-E: Unsatisfiable dependency group needsfoover2:i386=1 -> foo:any:any"
+E: Unsatisfiable dependency group needsfoover2:i386 -> foo:any:any"
 else
 NEEDSFOO2NATIVE="$BADPREFIX
 The following packages have unmet dependencies:
@@ -156,9 +156,9 @@ testfailureequal "$NEEDSFOO2FOREIGN" aptget install needsfoover2:i386 foo:i386 -
 testfailureequal "$NEEDSFOO2NATIVE" aptget install needsfoover2 foo:i386 -s
 
 solveableinsinglearch2() {
-	testfailuremsg 'E: Conflict: hatesfoo:amd64=1 -> not foo:amd64=1 but foo:amd64=1' aptget install foo hatesfoo -s --solver 3.0
-	testfailuremsg 'E: Conflict: hatesfooany:amd64=1 -> not foo:amd64=1 but foo:amd64=1' aptget install foo hatesfooany -s --solver 3.0
-	testfailuremsg 'E: Conflict: hatesfoonative:amd64=1 -> not foo:amd64=1 but foo:amd64=1' aptget install foo hatesfoonative -s --solver 3.0
+	testfailuremsg 'E: Conflict: hatesfoo:amd64=1 -> hatesfoo:amd64 -> not foo:amd64=1 but foo:amd64=1' aptget install foo hatesfoo -s --solver 3.0
+	testfailuremsg 'E: Conflict: hatesfooany:amd64=1 -> hatesfooany:amd64 -> not foo:amd64=1 but foo:amd64=1' aptget install foo hatesfooany -s --solver 3.0
+	testfailuremsg 'E: Conflict: hatesfoonative:amd64=1 -> hatesfoonative:amd64 -> not foo:amd64=1 but foo:amd64=1' aptget install foo hatesfoonative -s --solver 3.0
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  hatesfoo : Conflicts: foo but 1 is to be installed
@@ -171,12 +171,12 @@ The following packages have unmet dependencies:
 E: Unable to correct problems, you have held broken packages." aptget install foo hatesfoonative -s --solver internal
 }
 solveableinsinglearch2
-testfailuremsg "E: Conflict: hatesfoo:amd64=1 -> not foo:i386=1 but foo:i386=1" aptget install foo:i386 hatesfoo -s --solver 3.0
+testfailuremsg "E: Conflict: hatesfoo:amd64=1 -> hatesfoo:amd64 -> not foo:i386=1 but foo:i386=1" aptget install foo:i386 hatesfoo -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  hatesfoo : Conflicts: foo:i386 but 1 is to be installed
 E: Unable to correct problems, you have held broken packages." aptget install foo:i386 hatesfoo -s --solver internal
-testfailuremsg "E: Conflict: hatesfooany:amd64=1 -> not foo:i386=1 but foo:i386=1" aptget install foo:i386 hatesfooany -s --solver 3.0
+testfailuremsg "E: Conflict: hatesfooany:amd64=1 -> hatesfooany:amd64 -> not foo:i386=1 but foo:i386=1" aptget install foo:i386 hatesfooany -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  hatesfooany : Conflicts: foo:any
@@ -191,7 +191,7 @@ Inst hatesfoonative (1 unstable [amd64])
 Conf foo:i386 (1 unstable [i386])
 Conf hatesfoonative (1 unstable [amd64])' aptget install foo:i386 hatesfoonative -s
 
-testfailuremsg "E: Unsatisfiable dependency group needscoolfoo:i386=1 -> coolfoo:i386" aptget install needscoolfoo:i386 -s --solver 3.0
+testfailuremsg "E: Unsatisfiable dependency group needscoolfoo:i386 -> coolfoo:i386" aptget install needscoolfoo:i386 -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  needscoolfoo:i386 : Depends: coolfoo:i386 but it is not installable
@@ -264,12 +264,12 @@ Inst needscoolfoover1 (1 unstable [amd64])
 Conf coolfoo (1 unstable [amd64])
 Conf coolfoover (1 unstable [amd64])
 Conf needscoolfoover1 (1 unstable [amd64])' aptget install needscoolfoover1 -s
-	testfailuremsg "E: Unsatisfiable dependency group needscoolfoover2:amd64=1 -> coolfoo:any:any" aptget install needscoolfoover2 -s --solver 3.0
+	testfailuremsg "E: Unsatisfiable dependency group needscoolfoover2:amd64 -> coolfoo:any:any" aptget install needscoolfoover2 -s --solver 3.0
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  needscoolfoover2 : Depends: coolfoo:any (>= 2)
 E: Unable to correct problems, you have held broken packages." aptget install needscoolfoover2 -s --solver internal
-	testfailuremsg "E: Unsatisfiable dependency group needscoolfoover3:amd64=1 -> coolfoo:any:any" aptget install needscoolfoover3 -s --solver 3.0
+	testfailuremsg "E: Unsatisfiable dependency group needscoolfoover3:amd64 -> coolfoo:any:any" aptget install needscoolfoover3 -s --solver 3.0
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  needscoolfoover3 : Depends: coolfoo:any (>= 2)
diff --git a/test/integration/test-multiarch-foreign b/test/integration/test-multiarch-foreign
index b356c64c7..5a7b1a3b7 100755
--- a/test/integration/test-multiarch-foreign
+++ b/test/integration/test-multiarch-foreign
@@ -179,14 +179,14 @@ distribution that some required packages have not yet been created
 or been moved out of Incoming.
 The following information may help to resolve the situation:
 '
-	testfailuremsg "E: Conflict: hates-foo:amd64=1.0 -> not ${1%:*}:$4=1.0 but ${1%:*}:$4=1.0"  aptget install $1 hates-foo -s --solver 3.0
+	testfailuremsg "E: Conflict: ${1%:*}:$4=1.0 -> not hates-foo:amd64 but hates-foo:amd64=1.0 -> hates-foo:amd64"  aptget install $1 hates-foo -s --solver 3.0
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  hates-foo : Conflicts: foo
              Conflicts: foo:i386
              Conflicts: foo:armel
 E: Unable to correct problems, you have held broken packages." aptget install $1 hates-foo -s --solver internal
-	testfailuremsg "E: Conflict: $2:amd64=1.0 -> not foo:$4=1.0 but foo:$4=1.0" aptget install $1 $2 -s --solver 3.0
+	testfailuremsg "E: Conflict: $2:amd64=1.0 -> $2:amd64 -> not foo:$4=1.0 but foo:$4=1.0" aptget install $1 $2 -s --solver 3.0
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  $2 : Conflicts: foo:$4
diff --git a/test/integration/test-parse-all-archs-into-cache b/test/integration/test-parse-all-archs-into-cache
index 7485431db..b1992e726 100755
--- a/test/integration/test-parse-all-archs-into-cache
+++ b/test/integration/test-parse-all-archs-into-cache
@@ -5,6 +5,7 @@ TESTDIR="$(readlink -f "$(dirname "$0")")"
 . "$TESTDIR/framework"
 setupenvironment
 configarchitecture 'i386'
+allowremovemanual
 
 insertpackage 'unstable' 'bar' 'i386' '1' 'Depends: foo'
 insertpackage 'unstable' 'foo' 'i386' '1' 'Multi-Arch: foreign
diff --git a/test/integration/test-phased-updates-upgrade b/test/integration/test-phased-updates-upgrade
index 4f415f22e..15464bd3b 100755
--- a/test/integration/test-phased-updates-upgrade
+++ b/test/integration/test-phased-updates-upgrade
@@ -237,7 +237,7 @@ Conf depends-phased-dep (3 unstable-updates [all])
 Conf phased-new (3 unstable-updates [all])
 Conf depends-phased-new (3 unstable-updates [all])
 Conf phased-security (3 unstable-updates [all])
-Conf phased-security-same (3 unstable-security, unstable-updates [all])" aptget $upgrade -s -q depends-phased-dep
+Conf phased-security-same (3 unstable-security, unstable-updates [all])" aptget $upgrade -s -q depends-phased-dep --solver internal # FIXME? 3.0 does not support overrides of the policy
 done
 
 testsuccessequal "Reading package lists...
@@ -257,7 +257,7 @@ Inst phased-security-same [1] (3 unstable-security, unstable-updates [all])
 Conf phased-dep (3 unstable-updates [all])
 Conf depends-phased-dep (3 unstable-updates [all])
 Conf phased-security (3 unstable-updates [all])
-Conf phased-security-same (3 unstable-security, unstable-updates [all])" aptget upgrade -s -q depends-phased-dep
+Conf phased-security-same (3 unstable-security, unstable-updates [all])" aptget upgrade -s -q depends-phased-dep --solver internal # FIXME? 3.0 does not support overrides of the policy
 
 # install does not respect phasing
 testsuccessequal "Reading package lists...
diff --git a/test/integration/test-prefer-higher-priority-providers b/test/integration/test-prefer-higher-priority-providers
index 5fed20a59..e16e98e23 100755
--- a/test/integration/test-prefer-higher-priority-providers
+++ b/test/integration/test-prefer-higher-priority-providers
@@ -91,10 +91,7 @@ Inst awesome (1 unstable [all])
 Conf baz (1 unstable [all])
 Conf awesome (1 unstable [all])" aptget install awesome foo- bar- -s
 
-testfailuremsg "E: Unsatisfiable dependency: awesome:$native=1 -> foo:$native=1 | bar:$native=1 | baz:$native=1
-E: Not considered: foo:$native=1: not foo:$native -> not foo:$native=1
-E: Not considered: bar:$native=1: not bar:$native -> not bar:$native=1
-E: Not considered: baz:$native=1: not baz:$native -> not baz:$native=1" aptget install awesome foo- bar- baz- -s --solver 3.0
+testfailuremsg "E: Conflict: awesome:$native=1 -> awesome:$native -> baz:$native=1 -> baz:$native but not baz:$native" aptget install awesome foo- bar- baz- -s --solver 3.0
 testfailureequal "Reading package lists...
 Building dependency tree...
 Package 'foo' is not installed, so not removed
diff --git a/test/integration/test-release-candidate-switching b/test/integration/test-release-candidate-switching
index 5233dec06..db7e29495 100755
--- a/test/integration/test-release-candidate-switching
+++ b/test/integration/test-release-candidate-switching
@@ -117,6 +117,8 @@ Need to get 0 B/252 B of archives.
 After this operation, 258 kB of additional disk space will be used.
 E: Trivial Only specified but this is not a trivial operation." aptget install amarok/experimental --trivial-only -V
 
+phonon_backend_default="phonon-backend-null (4:4.20.0+sid)"
+[ "$APT_SOLVER" != "3.0" ] || phonon_backend_default="phonon-backend-xine (4:4.6.0really4.4.2-1+sid)"
 testfailureequal "Reading package lists...
 Building dependency tree...
 Selected version '2.3.2-2+exp' (experimental [i386]) for 'amarok-null'
@@ -127,14 +129,14 @@ The following additional packages will be installed:
    amarok-utils (2.3.2-2+exp)
    libc6 (2.11.2-7+sid)
    libmtp8 (0.3.1+sid)
-   phonon-backend-null (4:4.20.0+sid)
+   $phonon_backend_default
 The following NEW packages will be installed:
    amarok-common (2.3.2-2+exp)
    amarok-null (2.3.2-2+exp)
    amarok-utils (2.3.2-2+exp)
    libc6 (2.11.2-7+sid)
    libmtp8 (0.3.1+sid)
-   phonon-backend-null (4:4.20.0+sid)
+   $phonon_backend_default
 0 upgraded, 6 newly installed, 0 to remove and 0 not upgraded.
 Need to get 0 B/252 B of archives.
 After this operation, 258 kB of additional disk space will be used.
@@ -431,7 +433,23 @@ The following information may help to resolve the situation:
 The following packages have unmet dependencies:
  uninstallablepkg : Depends: libmtp8 (>= 10:0.20.1) but it is not going to be installed
                     Depends: amarok-utils (= 2.3.2-2+exp) but 2.3.1-1+sid is to be installed
-E: Unable to correct problems, you have held broken packages." aptget install uninstallablepkg/experimental --trivial-only -V
+E: Unable to correct problems, you have held broken packages." aptget install uninstallablepkg/experimental --trivial-only -V --solver internal
+
+# if one depends doesn't work, we don't need to look deeper… (solver3 version)
+testfailureequal "Reading package lists...
+Building dependency tree...
+Selected version '1.0' (experimental [all]) for 'uninstallablepkg'
+Solving dependencies...
+Some packages could not be installed. This may mean that you have
+requested an impossible situation or if you are using the unstable
+distribution that some required packages have not yet been created
+or been moved out of Incoming.
+The following information may help to resolve the situation:
+
+The following packages have unmet dependencies:
+ uninstallablepkg : Depends: libmtp8 (>= 10:0.20.1) but it is not going to be installed
+                    Depends: amarok-utils (= 2.3.2-2+exp) but it is not going to be installed
+E: Unsatisfiable dependency group uninstallablepkg:i386 -> libmtp8:i386" aptget install uninstallablepkg/experimental --trivial-only -V --solver 3.0
 
 insertinstalledpackage 'libmtp8' 'i386'  '1'
 insertinstalledpackage 'amarok' 'i386' '3' 'Depends: amarok-common (= 3), libmtp8 (>= 1)'
diff --git a/test/integration/test-specific-architecture-dependencies b/test/integration/test-specific-architecture-dependencies
index ca39f18d8..be8ea4245 100755
--- a/test/integration/test-specific-architecture-dependencies
+++ b/test/integration/test-specific-architecture-dependencies
@@ -194,7 +194,7 @@ The following NEW packages will be installed:
 Inst foo-depender (1 unstable [amd64])
 Conf foo-depender (1 unstable [amd64])' aptget install foo-depender -s
 
-testfailuremsg 'E: Unsatisfiable dependency group foo-depender:i386=1 -> foo:i386' aptget install foo-depender:i386 -s --solver 3.0
+testfailuremsg 'E: Unsatisfiable dependency group foo-depender:i386 -> foo:i386' aptget install foo-depender:i386 -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -313,7 +313,7 @@ Remv libold [1]
 Inst breaker-x64 (1 unstable [amd64])
 Conf breaker-x64 (1 unstable [amd64])' aptget install breaker-x64:amd64 -s
 
-testfailuremsg 'E: Unsatisfiable dependency group depender-x32:amd64=1 -> libc6:i386:any' aptget install depender-x32 -s --solver 3.0
+testfailuremsg 'E: Unsatisfiable dependency group depender-x32:amd64 -> libc6:i386:any' aptget install depender-x32 -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
diff --git a/test/integration/test-ubuntu-bug-1304403-obsolete-priority-standard b/test/integration/test-ubuntu-bug-1304403-obsolete-priority-standard
index 82e1d61e8..20d4d0c29 100755
--- a/test/integration/test-ubuntu-bug-1304403-obsolete-priority-standard
+++ b/test/integration/test-ubuntu-bug-1304403-obsolete-priority-standard
@@ -6,6 +6,7 @@ TESTDIR="$(readlink -f "$(dirname "$0")")"
 
 setupenvironment
 configarchitecture 'i386'
+allowremovemanual
 
 # Regression test for LP: #1304403
 #
diff --git a/test/integration/test-ubuntu-bug-614993 b/test/integration/test-ubuntu-bug-614993
index fe830b499..564c5a860 100755
--- a/test/integration/test-ubuntu-bug-614993
+++ b/test/integration/test-ubuntu-bug-614993
@@ -6,14 +6,14 @@ TESTDIR="$(readlink -f "$(dirname "$0")")"
 setupenvironment
 configarchitecture "amd64"
 setupaptarchive
+allowremovemanual
 
 # test success
 UPGRADE="Reading package lists...
 Building dependency tree...
 The following additional packages will be installed:
-  libdrm-intel1 libdrm-nouveau1 libdrm-radeon1 libdrm2 libmtdev1
-  libutouch-grail1 libx11-xcb1 libxcb-aux0 libxcb-dri2-0 libxfont1
-  xserver-common xserver-xorg-core xserver-xorg-input-all
+  libdrm-intel1 libdrm-nouveau1 libmtdev1 libutouch-grail1 libx11-xcb1
+  libxcb-aux0 libxcb-dri2-0 libxfont1 xserver-common xserver-xorg-core
   xserver-xorg-input-evdev xserver-xorg-input-mouse
   xserver-xorg-input-synaptics xserver-xorg-input-vmmouse
   xserver-xorg-input-wacom xserver-xorg-video-all xserver-xorg-video-apm
@@ -33,9 +33,8 @@ The following packages will be REMOVED:
 The following NEW packages will be installed:
   libmtdev1 libutouch-grail1 libx11-xcb1 libxcb-aux0 libxcb-dri2-0
 The following packages will be upgraded:
-  libdrm-intel1 libdrm-nouveau1 libdrm-radeon1 libdrm2 libxfont1
-  xserver-common xserver-xorg xserver-xorg-core xserver-xorg-input-all
-  xserver-xorg-input-evdev xserver-xorg-input-mouse
+  libdrm-intel1 libdrm-nouveau1 libxfont1 xserver-common xserver-xorg
+  xserver-xorg-core xserver-xorg-input-evdev xserver-xorg-input-mouse
   xserver-xorg-input-synaptics xserver-xorg-input-vmmouse
   xserver-xorg-input-wacom xserver-xorg-video-all xserver-xorg-video-apm
   xserver-xorg-video-ark xserver-xorg-video-ati xserver-xorg-video-chips
@@ -49,9 +48,9 @@ The following packages will be upgraded:
   xserver-xorg-video-sisusb xserver-xorg-video-tdfx xserver-xorg-video-trident
   xserver-xorg-video-tseng xserver-xorg-video-vesa xserver-xorg-video-vmware
   xserver-xorg-video-voodoo
-44 upgraded, 5 newly installed, 1 to remove and 0 not upgraded.
-Need to get 0 B/5561 kB of archives.
-After this operation, 3027 kB disk space will be freed.
+41 upgraded, 5 newly installed, 1 to remove and 3 not upgraded.
+Need to get 0 B/5505 kB of archives.
+After this operation, 2294 kB disk space will be freed.
 E: Trivial Only specified but this is not a trivial operation."
-testfailureequal "$UPGRADE" aptget install xserver-xorg --trivial-only
+testfailureequal "$UPGRADE" aptget install xserver-xorg --trivial-only -o APT::Get::Upgrade-By-Source-Package=0
 
diff --git a/test/integration/test-unpack-different-version-unpacked b/test/integration/test-unpack-different-version-unpacked
index 810e2e953..c1063d950 100755
--- a/test/integration/test-unpack-different-version-unpacked
+++ b/test/integration/test-unpack-different-version-unpacked
@@ -21,17 +21,7 @@ Building dependency tree...
 0 upgraded, 0 newly installed, 0 to remove and 2 not upgraded.
 2 not fully installed or removed.
 Conf libqtcore4 (2 unstable [amd64])
-Conf libqtcore4:i386 (2 unstable [i386])' aptget install -s -f --solver internal
-
-# FIXED(3.0): the reported version is correct now
-testsuccessequal 'Reading package lists...
-Building dependency tree...
-Solving dependencies...
-0 upgraded, 0 newly installed, 0 to remove and 2 not upgraded.
-2 not fully installed or removed.
-Conf libqtcore4 (1  [amd64])
-Conf libqtcore4:i386 (1  [i386])' aptget install -s -f --solver 3.0
-
+Conf libqtcore4:i386 (2 unstable [i386])' aptget install -s -f
 
 cleanstatus
 insertinstalledpackage 'libqtcore4' 'amd64' '2' 'Multi-Arch: same' '' 'install ok unpacked'