Using convex envelopes to solve the interactive fixed-charge linear programming problem
In the well-known fixed-charge linear programming problem, it is assumed, for each activity, that the value of the fixed charge that is incurred when the level of the activity is positive does not depend upon which other activities, if any, are also undertaken at a positive level. However, we have encountered several practical problems where this assumption does not hold. In an earlier paper, we developed a new problem, called the interactive fixed-charge linear programming problem (IFCLP), to model these problems. In this paper, we show how to construct the convex envelopes and other convex underestimating functions for the objective function for problem (IFCLP) over various rectangular subsets of its domain. Using these results, we develop a specialized branch-and- bound algorithm for problem (IFCLP) which finds an exact optimal solution for the problem in a finite number of steps. We also discuss the main properties of this algorithm.
- The interactive fixed charge linear programming problem
- scientific article; zbMATH DE number 4135708
- scientific article; zbMATH DE number 37091
- scientific article; zbMATH DE number 895009
- A General Primal-Dual Envelope Method for Convex Programming Problems
- scientific article; zbMATH DE number 3856836
- On the convex programming approach to linear programming
- Solving the linear complementarity problem through concave programming
- Satisfying constraint sets through convex envelopes
- scientific article; zbMATH DE number 3847229
- A finite algorithm for concave minimization over a polyhedron
- A Multi-Product Dynamic Lot-Size Model with Individual and Joint Set-up Costs
- A Successive Underestimation Method for Concave Minimization Problems
- Concave minimization over a convex polyhedron
- Convex Analysis
- Global Maximization of a Convex Function with Linear Inequality Constraints
- Global Minimization of a Linearly Constrained Concave Function by Partition of Feasible Domain
- scientific article; zbMATH DE number 3215121 (Why is no real title available?)
- Lagrange Multipliers and Nonconvex Programs
- Quasi-concave minimization subject to linear constraints
- The computation of fixed points and applications
- The Direct Power of Adjacent Vertex Programming Methods
- The interactive fixed charge linear programming problem
- Variations on a cutting plane method for solving concave minimization problems with linear constraints
- A new simplicial cover technique in constrained global optimization
- A composite branch and bound, cutting plane algorithm for concave minimization over a polyhedron
- An algorithm for concave integer minimization over a polyhedron
- Deterministic methods in constrained global optimization: Some recent advances and new fields of application
- The interactive fixed charge linear programming problem
- Multiproduct dynamic lot-sizing model with coordinated replenishments
- An algorithm and new penalties for concave integer minimization over a polyhedron
- scientific article; zbMATH DE number 895009 (Why is no real title available?)
- Existence and sum decomposition of vertex polyhedral convex envelopes
- A discrete dynamic convexized method for nonlinear integer programming
This page was built for publication: Using convex envelopes to solve the interactive fixed-charge linear programming problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1093525)
