Mixing optimal solutions

Patent metadata

Field	Value
Publication number	US-9396163-B2
Application number	US-201214343956-A
Country	US
Kind code	B2
Filing date	Dec 5, 2012
Priority date	Dec 22, 2011
Publication date	Jul 19, 2016
Grant date	Jul 19, 2016

Abstract

This invention relates to a method, system and computer program product for selecting an optimized solution in a computerised multiple-constraint problem space, comprising: receiving a linear function for optimization; receiving a set of constraints for the linear function; determining a first optimal solution for the linear function and initial constraints using linear programming solver; creating a new set of constrains using the first optimal solution as a constraint in addition to the initial constraints; creating a new quadratic function by adding a quadratic objective of slack variables to the linear function; and determining a solution to the quadratic function and new constraints using a quadratic programming solver.

First claim

The invention claimed is:

1. A method for selecting an optimized solution in a computerized multiple-constraint problem space, comprising:
receiving, by a processor, a linear function for optimization;
receiving, by the processor, a set of constraints for the linear function;
determining, by the processor, a first optimal solution for the linear function and initial constraints using a linear programming solver;
creating, by the processor, a new set of constrains using the first optimal solution as a constraint in addition to the initial constraints;
creating, by the processor, a new quadratic function by adding a quadratic objective of slack variables to the linear function; and
determining, by the processor, a solution to the quadratic function and new constraints using a quadratic programming solver.

2. A method according to claim 1 wherein the slack variable constraints have a default set of weights.

3. A method according to claim 2 wherein the slack variable constraints are based on one or more administrator or user determined cost coefficients.

4. A method according to claim 1 wherein the linear function can be an integer function.

5. A method of controlling a device using a method as according to claim 1 .

6. A method for selecting one or more optimized values in a computerized multiple-constraint problem space, comprising:
receiving, by a processor, as inputs a first set of input values of a mixed integer programming component, a second set of input values of a linear programming component, and a cost-weighted set of squared slack variable constraints based on one or more user-determined cost coefficients;
producing, by the processor, a first set of output values of said mixed integer programming component;
producing, by the processor, a second set of output values of said linear programming component;
creating, by the processor, a restricted solution space according to said first set of output values and said second set of output values; and
selecting, by the processor, an optimized value from said restricted solution space by applying a further restriction based on said cost-weighted set of squared slack variable constraints based on said one or more user-determined cost coefficients.

7. A system comprising a processor configured to perform a method for selecting an optimized solution in a computerized multiple-constraint problem space, comprising, the method comprising:
receiving, by the processor, a linear function for optimization;
receiving, by the processor, a set of constraints for the linear function;

determining, by the processor, a first optimal solution for the linear function and initial constraints using the linear programming solver;
creating, by the processor, a new set of constrains using the first optimal solution as a constraint in addition to the initial constraints;
creating, by the processor, a new quadratic function by adding a quadratic objective of slack variables to the linear function; and
determining, by the processor, a solution to the quadratic function and new constraints using the quadratic programming solver.

8. A system according to claim 7 wherein the slack variable constraints have a default set of weights.

9. A system according to claim 8 wherein the slack variable constraints are based on said one or more administrator or user determined cost coefficients.

10. A system according to claim 7 wherein the linear function can be an integer function.

11. A computer program product comprising computer readable recording medium having computer readable code stored thereon for selecting an optimized solution in a computerized multiple-constraint problem space, said computer readable code which when loaded onto a computer system and executed performs the following steps:
receiving a linear function for optimization;
receiving a set of constraints for the linear function;

determining a first optimal solution for the linear function and initial constraints using a linear programming solver;
creating a new set of constrains using the first optimal solution as a constraint in addition to the initial constraints;
creating a new quadratic function by adding a quadratic objective of slack variables to the linear function; and
determining a solution to the quadratic function and new constraints using a quadratic programming solver.

12. A computer program product according to claim 11 wherein the slack variable constraints have a default set of weights.

13. A computer program product according to claim 12 wherein the slack variable constraints are based on one or more administrator or user determined cost coefficients.

Assignees

• IBM

Inventors

• Moll Georges-Henri
• Nodet Xavier

Classifications

• G06Q10/04 Primary

  Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" (market predictions or forecasting for commercial activities G06Q30/0202) · CPC title

• G06F17/11

  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

• G06F17/13

  Differential equations (using digital differential analysers G06F7/64) · CPC title

• G06F17/12 Primary

  Simultaneous equations {, e.g. systems of linear equations} · CPC title