Method and apparatus for solving a mixed integer programming problem
AssigneeInternational Business Machines Corporation
InventorHiroki Yanagisawa
Life of this patent
Estimating the term…
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.
Claims20
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.
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.
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.
Dependencies are inferred from the claim text.