Remediating vulnerabilities in open-source software (OSS) dependencies is vital to maintaining software supply chain security. However, current automated approaches almost exclusively rely on dependency upgrades, which is limited by the nature of upgrades, i.e., the availability of secure versions, version pinning, and API incompatibilities. To address the limitation, this paper presents Remedius, an agent-based remediation framework for Maven projects that unifies dependency upgrading and patch porting within a holistic optimization workflow. Remedius dynamically clusters dependencies by usage, gathers project-specific evidence through autonomous LLM-driven agents, and formulates a cost-aware remediation optimization problem solved via Satisfiability Modulo Theory (SMT). The agents translate complex contextual factors—such as compatibility, reachability, and patch difficulty—into solver-ready constraints, enabling flexible and scalable decision-making beyond what static rules or LLM reasoning alone can achieve. By redefining optimization at the vulnerability level rather than the dependency level, Remedius maximizes vulnerability coverage while preserving build correctness and runtime compatibility. An evaluation of 301 real-world Maven projects demonstrates that Remedius outperforms state-of-the-art baselines, achieving the highest number of vulnerabilities fixed and the
fewest build or test failures. These results highlight a new direction for automated OSS remediation beyond upgrade-only solutions toward adaptive, agent-driven vulnerability management.