Back to results
US 8,554,704 B2Granted
Cruncher—an MIP solver accelerator
AssigneeInternational Business Machines Corporation
InventorsValdimir Lipets, Yossi Shiloach
Life of this patent
Estimating the term…
Abstract
Methods and systems are provided for solving an optimization problem using a model expressed in a mixed integer programming (MIP) language. The problem is constrained within a space of valid solutions by a plurality of MIP variables. A skeleton set of the variables are designated as eligible for fixed value assignments. An initial solution for the problem is obtained, which forms the basis for refinement. New versions of the problem are prepared and solved iteratively by fixing a proportion of the skeleton set to their best known values, as found in a previous problem-solving iteration.
Claims16
An optimization method for problem solving comprising:
- with a processor and a memory in which computer program instructions are stored, wherein the instructions comprise distinct software modules, the software modules comprising a cruncher module and a solver module, the processor operative under control of the instructions to perform the steps of:
- accepting a model of a problem to be solved, the model being formatted in a mixed integer programming format and being constrained within a space of valid solutions by a plurality of variables, the variables comprising integer variables and non-integer variables;
- with the cruncher module accepting a definition of an objective function to evaluate a solution of the problem;
- generating an initial solution for a version of the problem;
- designating a set of the integer variables as skeleton variables that are eligible for fixed value assignments;
- choosing a fixing fraction as a proportion of the skeleton variables to be selected;
- randomly selecting a subset of the skeleton variables, a size of the subset being the fixing fraction of the skeleton variables;
- constraining the space of the valid solutions to a non-empty subspace of the valid solutions by assigning fixed values to members of the subset according to respective values thereof that were determined in a previous solution of the problem, to thereby define a new version of the problem;
- and
- submitting the new version of the problem to the solver module, the solver module being operative for automatically solving the new version of the problem by finding values of the integer variables that correspond to an extremum of the objective function within the subspace of the valid solutions to obtain a solution of the new version, the solution having an objective value;
- making a comparison of the objective value of a current iteration with the objective value of a previous iteration;
- responsively to the comparison choosing a new fixing fraction;
- iterating the steps of randomly selecting, constraining, submitting, making a comparison and choosing a new fixing fraction, using the new fixing fraction as the fixing fraction until a termination criterion is satisfied;
- and
- thereafter reporting an optimum solution to the problem.
12 more elements
A method for configuring a computer-readable medium comprising:
- forming transitions in a non-transitory tangible computer-readable medium, the transitions comprising digital patterns that are interpretable by a computer as instructions, wherein the instructions comprise distinct software modules, the software modules including a cruncher module and a solver module, which instructions, when executed by the computer, cause the computer to perform the steps of:
- accepting a model of a problem to be solved, the model being formatted in a mixed integer programming format and being constrained within a space of valid solutions by a plurality of variables, the variables comprising integer variables and non-integer variables;
- with the cruncher module accepting a definition of an objective function to evaluate a solution of the problem;
- generating an initial solution for a version of the problem;
- designating a set of the integer variables as skeleton variables that are eligible for fixed value assignments;
- choosing a fixing fraction as a proportion of the skeleton variables to be selected;
- randomly selecting a subset of the skeleton variables, a size of the subset being the fixing fraction of the skeleton variables;
- constraining the space of the valid solutions to a non-empty subspace of the valid solutions by assigning fixed values to members of the subset according to respective values thereof that were determined in a previous solution of the problem, to thereby define a new version of the problem;
- and
- submitting the new version of the problem to the solver module, the solver module being operative for automatically solving the new version of the problem by finding values of the integer variables that correspond to an extremum of the objective function within the subspace of the valid solutions to obtain a solution of the new version, the solution having an objective value;
- making a comparison of the objective value of a current iteration with the objective value of a previous iteration;
- responsively to the comparison choosing a new fixing fraction;
- iterating the steps of randomly selecting, constraining, submitting, making a comparison and choosing a new fixing fraction, using the new fixing fraction as the fixing fraction until a termination criterion is satisfied;
- and
- thereafter reporting an optimum solution to the problem.
12 more elements
A computer software product for solving an optimization problem, including:
- a non-transitory computer storage medium in which computer program instructions are stored, wherein the instructions comprise distinct modules that include a model builder, a mixed integer programming solver module, and a cruncher module, which instructions, when executed by a computer, cause the computer to perform the steps of:
- cooperatively with the model builder preparing a model of a problem to be solved, the model being formatted in a mixed integer programming format and being constrained within a space of valid solutions by a plurality of variables, the variables comprising integer variables and non-integer variables;
- with the cruncher module accepting a definition of an objective function to evaluate a solution of the problem;
- generating an initial solution for a version of the problem;
- designating a set of the integer variables as skeleton variables for fixed value assignments;
- and
- choosing a fixing fraction as a proportion of the skeleton variables to be selected;
- randomly selecting a subset of the skeleton variables, a size of the subset being the fixing fraction of the skeleton variables;
- constraining the space of the valid solutions to a non-empty subspace of the valid solutions by assigning fixed values to members of the subset according to respective values thereof that were determined in a previous solution of the problem, to thereby define a new version of the problem;
- and
- submitting the new version of the problem to the solver module, the solver module being operative for automatically solving the new version of the problem by finding values of the integer variables that correspond to an extremum of the objective function within the subspace of the valid solutions to obtain a solution of the new version, the solution having an objective value;
- making a comparison of the objective value of a current iteration with the objective value of a previous iteration;
- responsively to the comparison choosing a new fixing fraction;
- iterating the steps of randomly selecting, constraining, submitting, making a comparison and choosing a new fixing fraction, using the new fixing fraction as the fixing fraction until a termination criterion is satisfied;
- and
- thereafter reporting an optimum solution to the problem.
13 more elements
A data processing system for solving an optimization problem, comprising:
- a processor;
- a memory accessible to the processor storing programs and data objects therein, wherein execution of the programs cause the processor to perform the steps of:
- preparing a model of a problem to be solved, the model being formatted in a mixed integer programming format and being constrained within a space of valid solutions by a plurality of variables, the variables comprising integer variables and non-integer variables;
- defining an objective function to evaluate a solution of the problem;
- generating an initial solution for a version of the problem;
- designating a set of the integer variables as eligible integer skeleton variables for fixed value assignments;
- and
- choosing a fixing fraction as a proportion of the skeleton variables to be selected;
- randomly selecting a subset of the skeleton variables, a size of the subset being the fixing fraction of the skeleton variables;
- constraining the space of valid solutions to a non-empty subspace of valid solutions by assigning fixed values to members of the subset according to respective values thereof that were determined in a previous solution of the problem, to thereby define a new version of the problem, wherein the members of the subset are ineligible for subsequent fixed value assignments;
- and
- automatically solving the new version of the problem by finding values of the integer variables that correspond to an extremum of the objective function within the subspace of valid solutions to obtain a solution of the new version, the solution having an objective value;
- making a comparison of the objective value of a current iteration with the objective value of a previous iteration;
- responsively to the comparison choosing a new fixing fraction;
- iterating the steps of randomly selecting, constraining, solving the new version, making a comparison and choosing a new fixing fraction, using the new fixing fraction as the fixing fraction until a termination criterion is satisfied, wherein the programs include:
- a model builder for preparing the model of the problem to be solved;
- a mixed integer programming solver module for solving the new version of the problem;
- a cruncher module that iteratively submits the new version of the problem to the solver module;
- and
- a monitoring module that exercises supervisory control over the cruncher module.
17 more elements
Dependencies are inferred from the claim text.