Method and apparatus for generating profile of solutions trading off number of activities utilized and objective value for bilinear integer optimization models
AssigneeInternational Business Machines Corporation
InventorJonathan Lee
Life of this patent
Estimating the term…
Abstract
A method and system of generating at least one of a solution and a profile of solutions for a problem, including trading off a reduction of an objective of the problem against a number of activities utilized in a solution. The method and system further include partitioning activities into known and potential new activities, and generating, via non-linear integer programming, a model comprising a profile of solutions based on the known and potential new activities.
Claims14
A computer-implemented method of generating a profile of solutions for a cutting stock problem, comprising programming a computer to perform a method comprising:
- inputting initial activities, said activities comprising stock cutting patterns;
- partitioning the initial activities into a set of known activities and a set of potential new activities;
- generating a model, said model comprising a profile of solutions to the cutting stock problem, based on the set of known activities and the set of potential new activities, said generating the model comprising:
- repeatedly setting up non-linear integer programs for simultaneously generating a column of potential new activities and a variable representing a utilization of each of the potential new activities;
- solving the non-linear integer programs using binary expansion and polyhedral methods;
- generating new activities during development of said model;
- and
- determining whether moving at least one of said new activities to the set of known activities would provide an improvement to a solution of said profile of solutions;
- and
- dynamically limiting a number of times each of said activities is used,
- wherein said profile of solutions trades off an amount of stock trim loss against a number of stock cutting patterns used, and
- wherein said model comprises pattern-exclusion constraints that prevent a binary-encoded pattern that is already indexed in the set of known activities from being re-generated as an integer-encoded pattern.
A computer-implemented method of generating a profile of solutions for a cutting stock problem, comprising programming a computer to perform a method comprising:
- inputting initial cutting patterns;
- partitioning the initial cutting patterns into a set of known cutting patterns and a set of potential new cutting patterns;
- generating a model based on the set of known cutting patterns and the set of potential new cutting patterns, said generating the model comprising:
- repeatedly setting up non-linear integer programs for simultaneously generating a column of potential new cutting patterns and a variable representing a utilization of each of the potential new cutting patterns;
- solving the non-linear integer programs using binary expansion and polyhedral methods;
- generating new activities during development of said model;
- and
- determining whether moving at least one of said new activities to the set of known activities would provide an improvement to said solution, and
- dynamically limiting a number of times each of said activities is used,
- wherein said model comprises pattern-exclusion constraints that prevent a binary-encoded pattern that is already indexed in the set of known activities from being re-generated as an integer-encoded pattern.
A tangible computer-readable storage device tangibly embodying a program of machine readable instructions executable by a digital processing apparatus to perform a method of generating a profile of solutions for a problem, the method comprising:
- inputting initial activities;
- partitioning the initial activities into a set of known activities and a set of potential new activities;
- generating a model based on the set of known activities and the set of potential new activities, said generating the model comprising:
- repeatedly setting up non-linear integer programs for simultaneously generating a column of potential new activities and a variable representing a utilization of each of the potential new activities;
- solving the non-linear integer programs using binary expansion and polyhedral methods;
- generating new activities during development of said model;
- and
- determining whether moving at least one of said new activities to the set of known activities would provide an improvement to said solution;
- and
- dynamically limiting a number of times each of said activities is used,
- wherein said model comprises pattern-exclusion constraints that prevent a binary-encoded pattern that is already indexed in the set of known activities from being re-generated as an integer-encoded pattern.
Dependencies are inferred from the claim text.