In this paper we introduce an evolutionary algorithm for the solution of mixed integer programs. The strategy is based on the separation of the set of variables into the integer subset and the continuous subset. The main idea is that if the integer variables are fixed by the evolutionary system, the continuous ones can be determined in function of them by a linear program, which simultaneously provides an evaluation of those variables. We extend this idea to the case were some of the integer variables are fixed by the evolutionary system and the remaining ones, as well as the continuous ones, are determined in function of them. Branch-and-bound and a specialised version of the relax-and-fixed heuristic are used to solve the mixed-integer subproblems. When a particular assignment of the integer variables set by the evolutionary system leads to a feasible solution, its evaluation is determined directly by the objective function. If the variables correspond to an infeasible solution, the evaluation is measured by the number of variables that could not be fixed, due to infeasibility in the subproblem; solutions with more variables fixed are preferred. We report results obtained for some standard benchmark instances, and compare them with those obtained by time limited branch-and-bound. For a set of difficult instances, the evolutionary algorithm could almost always improve the solution obtained by branch-and-bound on the same amount of CPU time.