If one is a deontologist then one needs to solve a series of constraint-satisfaction problems with hard constraints (i.e. they cannot be violated).

If all you require is to not violate any constraints, and you have no preference between worlds where equal numbers of constraints are violated, and you can regularly achieve worlds in which no constraints are violated, then perhaps constraint-satisfaction is qualitatively different.

In the real world, linear programming typically involves a combination of hard constraints and penalized constraints. If I say the hard-constraint solver isn't utilitarian, then what term would I use to describe the mixed-case problem?

The critical thing to me is that both are formalizing the problem and trying to find the best solution they can. The objections commonly made to utilitarianism would apply equally to moral absolutism phrased as a hard constraint problem.

There's the additional, complicating problem that non-utilitarian approaches may simply not be intelligible. A moral absolutist needs a language in which to specify the morals; the language is so context-dependent that the morals can't be absolute. Non-utilitarian approaches break down when the agents are not restricted to a single species; they break down more when "agent" means something like "set".