A branch and bound algorithm for extreme point mathematical programming problems
The extreme point mathematical programming problem is to minimize a linear function on those extreme points of a convex polytope Y, which lie within a convex polytope X. Both X and Y are defined by linear inequalities. This generalizes both zero-one and mixed-integer linear programming. After reviewing the known techniques which have been or could be applied, the authors develop their own branch and bound method. Basically branching is achieved by considering a hyperplane defining Y and either impose it as binding, or add it to X's definition, while removing it for Y's definition. Bounds are derived by continuous relaxation, improved by penalties. The efficiency is further increased by the addition, when possible, of some disjunctive constraints. Two different branching rules are proposed. Some computational results are given, indicating that problems with up to 40 variables (including slacks) for defining Y may be solved in reasonable time.
- A finite procedure to generate feasible points for the extreme point mathematical programming problem
- An extreme-point-ranking algorithm for the extreme-point mathematical programming problem
- scientific article; zbMATH DE number 4199967
- A disjunctive cutting plane algorithm for the extreme point mathematical programming problem
- On Extreme Point Programming Problem
- A classroom/time assignment model
- A Survey and Comparison of Methods for Finding All Vertices of Convex Polyhedral Sets
- An Algorithm for Determining Irrelevant Constraints and all Vertices in Systems of Linear Inequalities
- An Automatic Method of Solving Discrete Programming Problems
- Computer Codes for Problems of Integer Programming
- Concave Programming Applied to a Special Class of 0-1 Integer Programs
- Convergent Algorithms for Minimizing a Concave Function
- Critical Path Problem under Assignment Constraint—An Application of an Extreme Point Mathematical Programming Problom
- Expected Number of Vertices of a Random Convex Polyhedron
- Extreme Point Mathematical Programming
- Generating All the Faces of a Polyhedron
- scientific article; zbMATH DE number 3526452 (Why is no real title available?)
- scientific article; zbMATH DE number 3545380 (Why is no real title available?)
- scientific article; zbMATH DE number 3564694 (Why is no real title available?)
- scientific article; zbMATH DE number 3215121 (Why is no real title available?)
- scientific article; zbMATH DE number 3298499 (Why is no real title available?)
- scientific article; zbMATH DE number 3375242 (Why is no real title available?)
- Hypercylindrically Deduced Cuts in Zero-One Integer Programs
- Integer Programming by Implicit Enumeration and Balas’ Method
- Nonlinear Programming: Counterexamples to Two Global Optimization Algorithms
- On the convergence of cutting plane algorithms for a class of nonconvex mathematical programs
- Optimization with disjunctive constraints
- Practical Solution of Large Mixed Integer Programming Problems with Umpire
- Strong-Cut Enumerative procedure for Extreme point Mathematical Programming Problems
- Technical Note—On the Generalized Lattice Point Problem and Nonlinear Programming
- The Generalized Lattice-Point Problem
- Variations on a cutting plane method for solving concave minimization problems with linear constraints
- A disjunctive cutting plane algorithm for the extreme point mathematical programming problem
- A finite procedure to generate feasible points for the extreme point mathematical programming problem
- A finite algorithm for solving the generalized lattice point problem
- Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming
- The \(C^3\) theorem and a \(D^2\) algorithm for large scale stochastic mixed-integer programming: set convexification
- Nondifferentiable reverse convex programs and facetial convexity cuts via a disjunctive characterization
- scientific article; zbMATH DE number 3878317 (Why is no real title available?)
- scientific article; zbMATH DE number 4199967 (Why is no real title available?)
- scientific article; zbMATH DE number 4152172 (Why is no real title available?)
- Positive cases to the branch point problem
- An extreme-point-ranking algorithm for the extreme-point mathematical programming problem
- A primal like algorithm for extreme point fuzzy mathematical programming problem
This page was built for publication: A branch and bound algorithm for extreme point mathematical programming problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1078072)
