1. An apparatus for solving a mixed integer programming problem comprising: a generating section configured to generate a relaxed mixed integer programming problem by relaxing each of a part of integer variables of the mixed integer programming problem to a continuous variable; a solver configured to solve the relaxed mixed integer programming problem; and a determining section configured to determine, using a processor, a feasible solution of the mixed integer programming problem based on a solution of the relaxed mixed integer programming problem.