Method and apparatus for solving a mixed integer programming problem

Abstract

A method, apparatus and computer program product for solving a mixed integer programming problem. The apparatus includes a generating section configured to generate a relaxed mixed integer programming problem by relaxing each of only 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.

What is claimed is: 
     
         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 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 determining section configured to determine, 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.   
     
     
         2 . The apparatus of  claim 1 , wherein the generating section is further configured to keep a predetermined number of the integer variables of the mixed integer programming problem not relaxed and relax at least one integer variable of the mixed integer programming problem to at least one continuous variable. 
     
     
         3 . The apparatus of  claim 2 , wherein the generating section is further configured to keep less than four integer variables of the mixed integer programming problem not relaxed. 
     
     
         4 . The apparatus of  claim 3 , wherein the generating section is further configured to keep one integer variable of the mixed integer programming problem not relaxed and relax other integer variables to continuous variables. 
     
     
         5 . The apparatus of  claim 1 , wherein the solver is further configured to solve the relaxed mixed integer programming problem as a mixed discrete convex programming problem to require discrete convexity for each of at least one integer variables. 
     
     
         6 . The apparatus of  claim 1 , wherein the determining section is further configured to determine that the solution of the relaxed mixed integer programming problem is a feasible solution of the mixed integer programming problem if each of at least one continuous variable relaxed from each of at least one integer variable is calculated to be an integer value in the solution of the relaxed mixed integer programming problem. 
     
     
         7 . The apparatus of  claim 1 , wherein:
 the generating section is further configured to generate a sub-problem of the relaxed mixed integer programming problem which has fixed integer values for at least one integer variable relaxed to the continuous variable based on a value of a corresponding relaxed continuous variable in the solution of the relaxed mixed integer programming problem;   the solver is further configured to solve the sub-problem; and   the determining section is further configured to determine the feasible solution based on a solution of the sub-problem.   
     
     
         8 . The apparatus of  claim 7 , wherein the generating section is further configured to generate the sub-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. 
     
     
         9 . A method for solving a mixed integer programming problem comprising:
 generating 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;   reducing 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   determining, 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.   
     
     
         10 . The method of  claim 9 , wherein the generating further comprises keeping a predetermined number of the integer variables of the mixed integer programming problem not relaxed and relax at least one integer variable of the mixed integer programming problem to at least one continuous variable. 
     
     
         11 . The method of  claim 10 , wherein the generating further comprises keeping less than four integer variables of the mixed integer programming problem not relaxed. 
     
     
         12 . The method of  claim 11 , wherein the generating further comprises keeping one integer variable of the mixed integer programming problem not relaxed and relax other integer variables to continuous variables. 
     
     
         13 . The method of  claim 9 , wherein the solving further comprises solving the relaxed mixed integer programming problem as a mixed discrete convex programming problem to require discrete convexity for each of at least one integer variables. 
     
     
         14 . The method of  claim 9 , wherein the determining further comprises determining that the solution of the relaxed mixed integer programming problem is a feasible solution of the mixed integer programming problem if each of at least one continuous variable relaxed from each of at least one integer variable is calculated to be an integer value in the solution of the relaxed mixed integer programming problem. 
     
     
         15 . The method of  claim 9 , wherein:
 the generating further comprises generating a sub-problem of the relaxed mixed integer programming problem which has fixed integer values for at least one integer variable relaxed to the continuous variable based on a value of a corresponding relaxed continuous variable in the solution of the relaxed mixed integer programming problem;   the solving further comprises solving the sub-problem; and   the determining further comprises determining a feasible solution based on a solution of the sub-problem.   
     
     
         16 . The method of  claim 15 , wherein the generating further comprises generating the sub-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. 
     
     
         17 . A computer program product comprising a non-transitory computer readable storage medium having program instructions embodied therewith, the program instructions executable by a computer to cause the computer to perform operations comprising:
 generating 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;   reducing 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   determining, 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.   
     
     
         18 . The computer program product of  claim 17 , wherein the generating further comprises a predetermined number of the integer variables of the mixed integer programming problem not relaxed and relax at least one integer variable of the mixed integer programming problem to at least one continuous variable. 
     
     
         19 . The computer program product of  claim 18 , wherein the generating further comprises keeping less than four integer variables of the mixed integer programming problem not relaxed. 
     
     
         20 . The computer program product of  claim 19 , wherein the generating further comprises keeping one integer variable of the mixed integer programming problem not relaxed and relax other integer variables to continuous variables.