Generating a mixed integer linear programming matrix from an annotated entity-relationship data model and a symbolic matrix

Patent metadata

Field	Value
Publication number	US-10073813-B2
Application number	US-201113243928-A
Country	US
Kind code	B2
Filing date	Sep 23, 2011
Priority date	Sep 6, 2011
Publication date	Sep 11, 2018
Grant date	Sep 11, 2018

Abstract

Programmatically generating a mixed integer linear programming (“MIP”) matrix, which can then be solved to provide an optimization, based on an annotated entity/relationship data model and a symbolic matrix. The annotated data model identifies one or more outputs of the optimization. The symbolic matrix provides one or more constraints that provide requirements under which the optimization is solved. Outputs of the optimization are represented as variables, inputs of the optimization are represented as constants, and primary keys from the data model are represented as indexes. The constraints are expressed using the variables, constants, and indexes. A MIP matrix is generated from the symbolic matrix, and is then solved by a MIP solver. The output of the MIP solver is used to update a corresponding data structure of the data model.

First claim

The invention claimed is:

1. A computer-implemented method of generating a mixed integer linear programming matrix for solving an optimization of a data model, comprising:
programmatically generating a constant definition to represent each input field of each of a plurality of tables in an entity-relationship data model schema that represents the data model, the constant definition being indexed by each primary key of the table in which the input field is defined, and programmatically generating, for each value of the primary key, a constant instance indexed by the value;
programmatically generating a variable definition to represent each output field of each of the tables, the variable definition being indexed by each primary key of the table in which the output field is defined, and programmatically generating, for each value of the primary key, a variable instance indexed by the value;
programmatically generating a symbolic matrix structure comprising:
for each indexed variable definition, a column corresponding to the indexed variable definition;
for each of at least one constraint on an optimization to be solved, a row corresponding to the constraint, each constraint reflecting at least one of the input fields, the constants, or the output fields, at least one of the at least one constraint being an indexed constraint that is indexed by at least one of the output fields;
a column for storing a comparator used in a selected constraint;
a column for storing a right-hand side of a selected constraint; and
a row corresponding to the optimization;

programmatically storing values into cells of the symbolic matrix structure, comprising:
for each row corresponding to a constraint, storing a specified right-hand side of the constraint into a cell where the row intersects the column for storing the right-hand side, storing a specified comparator of the constraint into a cell where the row intersects the column for storing the comparator, and storing a multiplier into a cell where the row intersects the column corresponding to the indexed variable definition, the multiplier for at least one row being an indexed constant; and
for the row corresponding to the optimization, storing an objective of the optimization into a cell where the row intersects the column for storing the right-hand side and storing a multiplier into a cell where the row intersects the column corresponding to the indexed variable definition, the multiplier being an indexed constant;

programmatically generating, from the symbolic matrix and the data model, a MIP matrix instance, the symbolic matrix being separate and distinct from the MIP matrix instance and from the data model, further comprising:
expanding each row of the symbolic matrix that corresponds to an indexed constraint to include a row in the MIP matrix instance for each value found in the data model for the constraint index;
expanding each column of the symbolic matrix that corresponds to an indexed variable definition to include a column in the MIP matrix instance for each value found in the data model for the indexed variable; and

inputting the MIP matrix instance to a MIP solver to yield the optimization.

2. The method according to claim 1 , wherein the yielded optimization comprises a determined value for each of the output fields, and further comprising updating the output fields in the data model using output of the MIP solver.

3. The method according to claim 1 , wherein the entity-relationship data model schema is annotated to identify each output field.

4. The method according to claim 1 , wherein the optimization comprises one of a minimization or a maximization.

5. A system for generating a mixed integer linear programming matrix for solving an optimization of a data model, comprising:
a computer comprising a processor; and
instructions which are executable, using the processor, to implement functions comprising:
programmatically generating a constant definition to represent each input field of each of a plurality of tables in an entity-relationship data model schema that represents the data model, the constant definition being indexed by each primary key of the table in which the input field is defined, and programmatically generating, for each value of the primary key, a constant instance indexed by the value;
programmatically generating a variable definition to represent each output field of each of the tables, the variable definition being indexed by each primary key of the table in which the output field is defined, and programmatically generating, for each value of the primary key, a variable instance indexed by the value;
programmatically generating a symbolic matrix structure comprising:
for each indexed variable definition, a column corresponding to the indexed variable definition;
for each of at least one constraint on an optimization to be solved, a row corresponding to the constraint, each constraint reflecting at least one of the input fields, the constants, or the output fields, at least one of the at least one constraint being an indexed constraint that is indexed by at least one of the output fields;
a column for storing a comparator used in a selected constraint;
a column for storing a right-hand side of a selected constraint; and
a row corresponding to the optimization;

programmatically storing values into cells of the symbolic matrix structure, comprising:
for each row corresponding to a constraint, storing a specified right-hand side of the constraint into a cell where the row intersects the column for storing the right-hand side, storing a specified comparator of the constraint into a cell where the row intersects the column for storing the comparator, and storing a multiplier into a cell where the row intersects the column corresponding to the indexed variable definition, the multiplier for at least one row being an indexed constant; and
for the row corresponding to the optimization, storing an objective of the optimization into a cell where the row intersects the column for storing the right-hand side and storing a multiplier into a cell where the row intersects the column corresponding to the indexed variable definition, the multiplier being an indexed constant;

programmatically generating, from the symbolic matrix and the data model, a MIP matrix instance, the symbolic matrix being separate and distinct from the MIP matrix instance and from the data model, further comprising:
expanding each row of the symbolic matrix that corresponds to an indexed constraint to include a row in the MIP matrix instance for each value found in the data model for the constraint index;
expanding each column of the symbolic matrix that corresponds to an indexed variable definition to include a column in the MIP matrix instance for each value found in the data model for the indexed variable; and

inputting the MIP matrix instance to a MIP solver to yield the optimization.

6. The system according to claim 5 , wherein the yielded optimization comprises a determined value for each of the output fields, and wherein the functions further comprise updating the output fields in the data model using output of the MIP solver.

7. The system according to claim 5 , wherein the entity-relationship data model schema is annotated to identify each output field.

8. A computer program product for generating a mixed integer linear programming matrix for solving an optimization of a data model, the computer program product comprising:
a non-transitory computer readable storage medium having computer readable program code embodied therein, the computer readable program code configured for:
programmatically generating a constant definition to represent each input field of each of a plurality of tables in

Assignees

• Beraudier Vincent
• Moll Georges Henri
• IBM

Inventors

• Beraudier Vincent
• Moll Georges-Henri

Classifications

• G06F17/11 Primary

  for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title