Using convex envelopes to solve the interactive fixed-charge linear programming problem
type: Item
instance of: scholarly article
title: Using convex envelopes to solve the interactive fixed-charge linear programming problem
zbMATH Open document ID: 0628.90045
DOI: 10.1007/BF00938310
author: B. George
published in: Journal of Optimization Theory and Applications
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C30
zbMATH DE Number: 4023011
zbMATH Keywords: nonconvex programming
zbMATH Keywords: fixed-charge linear programming
zbMATH Keywords: convex envelopes
zbMATH Keywords: branch-and-bound
zbMATH Keywords: exact optimal solution
MaRDI profile type: Publication
cites work: The interactive fixed charge linear programming problem
cites work: Q5342287
cites work: Concave minimization over a convex polyhedron
cites work: Global Maximization of a Convex Function with Linear Inequality Constraints
cites work: Variations on a cutting plane method for solving concave minimization problems with linear constraints
cites work: Quasi-concave minimization subject to linear constraints
cites work: Global Minimization of a Linearly Constrained Concave Function by Partition of Feasible Domain
cites work: A finite algorithm for concave minimization over a polyhedron
cites work: Convex Analysis
cites work: The Direct Power of Adjacent Vertex Programming Methods
cites work: A Successive Underestimation Method for Concave Minimization Problems
cites work: The computation of fixed points and applications
cites work: Lagrange Multipliers and Nonconvex Programs
cites work: A Multi-Product Dynamic Lot-Size Model with Individual and Joint Set-up Costs
Recommended article: The interactive fixed charge linear programming problem
Recommended article: Q3468877
Recommended article: Q3991517
Recommended article: Q4883167
Recommended article: A General Primal-Dual Envelope Method for Convex Programming Problems
Recommended article: Q3325480
Recommended article: On the convex programming approach to linear programming
Recommended article: Solving the linear complementarity problem through concave programming
Recommended article: Satisfying constraint sets through convex envelopes
Recommended article: Q3316971
description: scientific article; zbMATH DE number 4023011