Consequences of non-linearities in specific fuel consumption (SFC) of a heavy truck combustion engine are studied with focus on such small road gradients that a constant speed is optimal if the engine torque has an affine relation to fuelling. A quasi-static analysis gives valuable insights into the intrinsic properties of minimization of fuel consumption. Two objective functions are shown to give different optimal velocity trajectories on a constant road gradient, when the non-linearity in SFC is significant, a notation which is quantified. For a significant non-linearity, when a constraint is set to keep a final time, switching between two characteristic speeds is optimal. Alternatively, if consumed time, in addition to fuel consumption, is part of the objective function, then keeping to one constant speed is optimal also for significant non-linearities. However, the different optimal solutions still show similarities, since for a certain significant non-linearity a specific speed range determined by the characteristic velocities is shown to be unobtainable for both optimality criteria. Similar results are obtained for a full dynamic model including a realistic fuel map and other realistic constraints.