Patent Document ID: 10061569
Application ID: 14812213
Patent Flag: 1

Claim One:
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 only a portion of integer variables of the mixed integer programming problem to a continuous variable, wherein the generating section is further configured to generate a sub-problem of the relaxed mixed integer programming problem if a predicted range of an objective function of the sub-problem overlaps a required range of an objective function of the mixed integer programming problem; a solver configured to reduce solving time for the relaxed mixed integer programming problem by branching only relaxed portions of the integer variables using a branch-and-bound procedure; and a searching section configured to search, using a processor, an optimum solution of the mixed integer programming problem, using branches for only a portion of the integer variables, based on a solution of the relaxed mixed integer programming problem, and to determine an upper bound and a lower bound for each of one or more sub-problems, and to discard a sub-problem from the one or more sub-problems if a lower bound of the sub-problem is greater than an upper bound of other sub-problems from the one or more sub-problems.