Direct Method for Solving Bilinear Programming Problem

The bilinear programming problem is considered, where a column, which corresponds to one of the variables, is not fixed but can be chosen from a convex set. This problem is known as the Dantzig – Wolfe problem. Earlier, a modified support method was proposed to solve the problem, using the decomposi...

Full description

Saved in:
Bibliographic Details
Main Author: L. D. Matveyeva
Format: Article
Language:Russian
Published: Belarusian National Technical University 2021-04-01
Series:Наука и техника
Subjects:
Online Access:https://sat.bntu.by/jour/article/view/2434
Tags: Add Tag
No Tags, Be the first to tag this record!
_version_ 1846144886091284480
author L. D. Matveyeva
author_facet L. D. Matveyeva
author_sort L. D. Matveyeva
collection DOAJ
description The bilinear programming problem is considered, where a column, which corresponds to one of the variables, is not fixed but can be chosen from a convex set. This problem is known as the Dantzig – Wolfe problem. Earlier, a modified support method was proposed to solve the problem, using the decomposition of the problem constraints of the Dantzig – Wolfe method. The author of the paper has developed a direct exact method for solving the formulated problem. The method is based on the idea of the solving a linear programming problem with generalized direct constraints and a general concept of an adaptive solution method. The notions of support, support plan, optimal and suboptimal (e-optimal) plan are introduced which is a given approximation of the objective function to the optimal plan of the problem. Criteria for optimality and suboptimality of the support plan have been formulated and have been proved in the paper. The search for the optimal solution is based on the idea of maximizing the increment of the objective function. This approach allows more fully to take into account the main target and structure of the problem. Improving a support plan consists of two parts: replacing the plan and replacing the support. To find a suitable direction, a special derived problem is solved while taking into account the main constraints of the problem. The replacement of the support is based on the search for the optimal plan of the dual problem. The method leads to an optimal solution to the problem in a finite number of iterations (in the case of a non-degenerate value).
format Article
id doaj-art-af7b0eb997b041689f7f6ee020b5e714
institution Kabale University
issn 2227-1031
2414-0392
language Russian
publishDate 2021-04-01
publisher Belarusian National Technical University
record_format Article
series Наука и техника
spelling doaj-art-af7b0eb997b041689f7f6ee020b5e7142024-12-02T06:52:25ZrusBelarusian National Technical UniversityНаука и техника2227-10312414-03922021-04-0120217918410.21122/2227-1031-2021-20-2-179-1842120Direct Method for Solving Bilinear Programming ProblemL. D. Matveyeva0Belаrusian National Technical UniversityThe bilinear programming problem is considered, where a column, which corresponds to one of the variables, is not fixed but can be chosen from a convex set. This problem is known as the Dantzig – Wolfe problem. Earlier, a modified support method was proposed to solve the problem, using the decomposition of the problem constraints of the Dantzig – Wolfe method. The author of the paper has developed a direct exact method for solving the formulated problem. The method is based on the idea of the solving a linear programming problem with generalized direct constraints and a general concept of an adaptive solution method. The notions of support, support plan, optimal and suboptimal (e-optimal) plan are introduced which is a given approximation of the objective function to the optimal plan of the problem. Criteria for optimality and suboptimality of the support plan have been formulated and have been proved in the paper. The search for the optimal solution is based on the idea of maximizing the increment of the objective function. This approach allows more fully to take into account the main target and structure of the problem. Improving a support plan consists of two parts: replacing the plan and replacing the support. To find a suitable direction, a special derived problem is solved while taking into account the main constraints of the problem. The replacement of the support is based on the search for the optimal plan of the dual problem. The method leads to an optimal solution to the problem in a finite number of iterations (in the case of a non-degenerate value).https://sat.bntu.by/jour/article/view/2434bilinear programmingoptimal plansupportdirect method
spellingShingle L. D. Matveyeva
Direct Method for Solving Bilinear Programming Problem
Наука и техника
bilinear programming
optimal plan
support
direct method
title Direct Method for Solving Bilinear Programming Problem
title_full Direct Method for Solving Bilinear Programming Problem
title_fullStr Direct Method for Solving Bilinear Programming Problem
title_full_unstemmed Direct Method for Solving Bilinear Programming Problem
title_short Direct Method for Solving Bilinear Programming Problem
title_sort direct method for solving bilinear programming problem
topic bilinear programming
optimal plan
support
direct method
url https://sat.bntu.by/jour/article/view/2434
work_keys_str_mv AT ldmatveyeva directmethodforsolvingbilinearprogrammingproblem