Patent ID: 8554704
Filing Date: 2013-10-08
Classification: G06F

Abstract:
1. 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.