NON-LINEAR PROGRAMMING PROBLEM PROCESSING DEVICE AND NON-LINEAR PROGRAMMING PROBLEM PROCESSING METHOD

• US 20190311269A1
• Filed: 06/01/2015
• Published: 10/10/2019
• Est. Priority Date: 06/05/2014
• Status: Abandoned Application

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: KAMEDA, Yoshio
• Application Number:
  US15/316,390
• Publication Number:
  US 20190311269A1
• Time in Patent Office: Days
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G16Z 99/00 Subject matter not provided for in other main groups of this subclass

Abstract

To efficiently process a programming problem including a function defined piecewise without having the differentiability and continuity of the function expressing the problem or spatial continuity as prerequisites, a non-linear programming problem processing device is provided with: a non-linear programming problem input unit; a provisional solution generation unit that produces a solution obtained in a certain region of the non-linear programming problem as a provisional solution; a solution candidate generation unit that produces a solution obtained in a nearby region of the provisional solution as a solution candidate; a provisional solution update unit that updates the solution candidate in accordance with the result of comparison of the provisional solution and the solution candidate; an end determination unit that determines the end of the process using a provisional solution improvement degree and/or the number of times of generation of the solution candidate; and a non-linear programming problem solution output unit.

Claims

1. A non-linear programming problem processing device wherein a restriction or an objective function includes a piecewise defined function,

the device comprising:

a non-linear programming problem input unit configured to acquire a non-liner programming problem;

a provisional solution generation unit configured to determine as a provisional solution of the non-liner programming problem a solution obtained in a certain region of the non-liner programming problem;

a solution candidate generation unit configured to determine as a solution candidate of the non-liner programming problem a solution obtained in a region near the provisional solution;

a provisional solution update unit configured to update the solution candidate as a provisional solution in accordance with a result of comparison between the provisional solution and the solution candidate;

a end determination unit configured to determine a process end on the basis of a determination standard that is at least one of an improvement degree of a provisional solution and the number of times of generation of a solution candidate; and

a non-linear programming problem solution output unit configured to output the provisional solution.

2. The non-linear programming problem processing device according to claim 1, wherein the restriction is one of a linear function and a piecewise linear function, and

the objective function is one of a linear function, a piecewise linear function, a quadratic function, and a piecewise quadratic function.

3. The non-linear programming problem processing device according to claim 1, wherein the provisional solution generation unit comprises:

a provisional solution region selection unit configured to select a certain region of the non-linear programming problem;

a solution calculation unit configured to obtain a solution of a programming problem in the provisional solution region; and

a provisional solution generation end determination unit configured to determine whether the solution is good or not, repeating a provisional solution generation process when the solution is not good, and determine the solution as a provisional solution and ending a provisional solution generation process when the solution is good.

4. The non-linear programming problem processing device according to claim 1, wherein the solution candidate generation unit comprises:

a solution candidate region selection unit configured to select a region near the provisional solution;

a solution calculation unit configured to obtain a solution of a programming problem in the solution candidate region; and

a solution candidate generation end determination unit configured to determine whether the solution is good or not, repeat a solution candidate generation process when the solution is not good, and determine the solution as a solution candidate and end a solution candidate generation process when the solution is good.

5. The non-linear programming problem processing device according to claim 1, wherein the provisional solution update unit compares superiority between the provisional solution and the solution candidate, always determines the solution candidate as a new provisional solution when the solution candidate is better, and probabilistically determines the solution candidate as a new provisional solution when the solution candidate is not better.

6. The non-linear programming problem processing device according to claim 1, comprising region-and-solution information storage unit to which at least one of the provisional solution generation unit and the solution candidate generation unit can make reference and addition.

7. The non-linear programming problem processing device according to claim 1, wherein the solution candidate selection unit selects a region, using a distance from the provisional solution or a direction vector whose end point is the provisional solution.

8. The non-linear programming problem processing device according to claim 1, wherein the solution candidate selection unit selects a region, using an evaluation value of a region near a region including the provisional solution.

9. A non-linear programming problem processing method comprising:

acquiring a non-linear programming problem in which a restriction or an objective function includes a piecewise defined function;

obtaining a solution in a certain region of the non-liner programming problem, and determining the solution as a provisional solution of the non-liner programming problem;

obtaining a solution in a region near the provisional solution, and determining the solution as a solution candidate of the non-liner programming problem;

comparing the provisional solution and the solution candidate, and updating the provisional solution;

determining a process end on the basis of a determination standard that is at least one of an improvement degree of a provisional solution and the number of times of generation of a solution candidate; and

outputting the provisional solution.

10. The non-linear programming problem processing method according to claim 9, wherein the restriction is one of a linear function and a piecewise linear function, and

the objective function is one of a linear function, a piecewise linear function, a quadratic function, and a piecewise quadratic function.