Partitioning procedures for solving mixed-variables programming problems

Partitioning procedures for solving mixed-variables programming problems

2005 | J.F. Benders
This paper presents two slightly different procedures for solving mixed-variables programming problems of the form max{c^T x + f(y) | Ax + F(y) ≤ b, x ∈ R^p, y ∈ S}, where x and y are variables, and S is an arbitrary subset of R^q. The problem includes both continuous and discrete variables, such as in mixed-integer programming, where some variables are restricted to integer values. The paper also discusses non-linear programming problems where some variables appear in non-linear functions. The basic idea of the procedures is to partition the problem into two subproblems: one defined on S (which may be linear, non-linear, or discrete) and another linear programming problem in R^p. This approach avoids the need to calculate all constraints for the feasible region, which can be computationally intensive. The two procedures differ in how the linear programming problem is solved. Earlier versions of these procedures were part of the author's doctoral dissertation. This paper provides a more detailed description of the computational aspects. The paper also introduces some preliminary concepts, including convex polyhedral sets and the simplex method for solving linear programming problems. It defines several convex cones and polyhedrons, including C, C0, and P, which are used in the formulation of the problem. These concepts are essential for understanding the procedures for solving mixed-variables programming problems. The paper emphasizes the importance of partitioning variables to exploit the structure of the problem, which can lead to more efficient solutions. This is particularly useful in problems that combine linear programming with other types of programming, such as transportation problems. The procedures are designed to solve such problems in a finite number of steps, with each step involving the solution of a general programming problem.This paper presents two slightly different procedures for solving mixed-variables programming problems of the form max{c^T x + f(y) | Ax + F(y) ≤ b, x ∈ R^p, y ∈ S}, where x and y are variables, and S is an arbitrary subset of R^q. The problem includes both continuous and discrete variables, such as in mixed-integer programming, where some variables are restricted to integer values. The paper also discusses non-linear programming problems where some variables appear in non-linear functions. The basic idea of the procedures is to partition the problem into two subproblems: one defined on S (which may be linear, non-linear, or discrete) and another linear programming problem in R^p. This approach avoids the need to calculate all constraints for the feasible region, which can be computationally intensive. The two procedures differ in how the linear programming problem is solved. Earlier versions of these procedures were part of the author's doctoral dissertation. This paper provides a more detailed description of the computational aspects. The paper also introduces some preliminary concepts, including convex polyhedral sets and the simplex method for solving linear programming problems. It defines several convex cones and polyhedrons, including C, C0, and P, which are used in the formulation of the problem. These concepts are essential for understanding the procedures for solving mixed-variables programming problems. The paper emphasizes the importance of partitioning variables to exploit the structure of the problem, which can lead to more efficient solutions. This is particularly useful in problems that combine linear programming with other types of programming, such as transportation problems. The procedures are designed to solve such problems in a finite number of steps, with each step involving the solution of a general programming problem.
Reach us at info@study.space
[slides] Partitioning procedures for solving mixed-variables programming problems | StudySpace