GOLOG is an agent programming language designed to represent complex actions and procedures in the situation calculus. In this paper we apply relaxation-based heuristics – often used in classical planning – to find (near) optimal executions of a GOLOG program. In doing so we present and utilise a theory of relaxed regression for the approximate interpretation of a GOLOG program. This relaxed interpreter is used to heuristically evaluate the available choices in the search for a program execution. We compare the performance of our heuristic interpreter (in terms of the quality of executions found) with a traditional depth-first search interpreter and one guided by a greedy heuristic without a look-ahead on three domains: spacecraft control, mine operations planning, and task scheduling.