A general purpose exact solution method for mixed integer concave minimization problems
From MaRDI portal
Abstract: In this article, we discuss an exact algorithm for solving mixed integer concave minimization problems. A piecewise inner-approximation of the concave function is achieved using an auxiliary linear program that leads to a bilevel program, which provides a lower bound to the original problem. The bilevel program is reduced to a single level formulation with the help of Karush-Kuhn-Tucker (KKT) conditions. Incorporating the KKT conditions lead to complementary slackness conditions that are linearized using BigM, for which we identify a tight value for general problems. Multiple bilevel programs, when solved over iterations, guarantee convergence to the exact optimum of the original problem. Though the algorithm is general and can be applied to any optimization problem with concave function(s), in this paper, we solve two common classes of operations and supply chain problems; namely, the concave knapsack problem, and the concave production-transportation problem. The computational experiments indicate that our proposed approach outperforms the customized methods that have been used in the literature to solve the two classes of problems by an order of magnitude in most of the test cases.
Cites work
- A branch and bound algorithm for solving a class of nonlinear integer programming problems
- A branch and search algorithm for a class of nonlinear knapsack problems
- A branch-and-price algorithm for facility location with general facility cost functions
- A branch-and-reduce approach to global optimization
- A cut-and-branch algorithm for the quadratic knapsack problem
- A cutting-plane approach to the edge-weighted maximal clique problem
- A Decomposition Algorithm for Solving the Multifacility Production-Transportation Problem with Nonlinear Production Costs
- A finite algorithm for concave minimization over a polyhedron
- A hybrid approach to discrete mathematical programming
- A Lagrangian based branch-and-bound algorithm for production-transportation problems
- A new exact algorithm for concave knapsack problems with integer variables
- A note on multi-item inventory systems with limited capacity
- A polynomial time solvable concave network flow problem
- A production-transportation problem with stochastic demand and concave production costs
- A pseudo-polynomial algorithm for solving rank three concave production-transportation problems
- A pseudo-polynomial primal-dual algorithm for globally solving a production-transportation problem
- A relaxation algorithm for the minimization of a quasiconcave function on a convex polyhedron
- A SIMPLICIAL BRANCH-AND-BOUND ALGORITHM FOR PRODUCTION-TRANSPORTATION PROBLEMS WITH INSEPARABLE CONCAVE PRODUCTION COST
- A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables
- A Successive Underestimation Method for Concave Minimization Problems
- An algorithm and new penalties for concave integer minimization over a polyhedron
- An algorithm for concave integer minimization over a polyhedron
- An algorithm for nonconvex programming problems
- An Algorithm for Separable Nonconvex Programming Problems
- An Algorithm for Separable Nonconvex Programming Problems II: Nonconvex Constraints
- An algorithm for the min concave cost flow problem
- An algorithm for the solution of the 0-1 knapsack problem
- An extended formulation approach to the edge-weighted maximal clique problem
- An integer concave minimization approach for the minimum concave cost capacitated flow problem on networks
- Benchmarking optimization software with performance profiles.
- Concave minimization over a convex polyhedron
- Constrained global optimization: algorithms and applications
- Constrained multi-item inventory systems: An implicit approach
- Convergent Lagrangian and Contour Cut Method for Nonlinear Integer Programming with a Quadratic Objective Function
- Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
- Exact algorithm for concave knapsack problems: linear underestimation and partition method
- Exact solution of a class of nonlinear knapsack problems
- Exact Solution of the Quadratic Knapsack Problem
- Finite exact branch-and-bound algorithms for concave minimization over polytopes
- Global Maximization of a Convex Function with Linear Inequality Constraints
- Global optimization of mixed-integer nonlinear programs: a theoretical and computational study
- Global search algorithms for minimum concave-cost network flow problems
- Handbook of test problems in local and global optimization
- Heuristic solutions for general concave minimum cost network flow problems
- scientific article; zbMATH DE number 4112385 (Why is no real title available?)
- scientific article; zbMATH DE number 2107164 (Why is no real title available?)
- scientific article; zbMATH DE number 3215121 (Why is no real title available?)
- scientific article; zbMATH DE number 3365044 (Why is no real title available?)
- Incorporating inventory and routing costs in strategic location models
- Lagrangean methods for the 0-1 quadratic knapsack problem
- Location and two-echelon inventory network design with economies and diseconomies of scale in facility operating costs
- Min-cut clustering
- Minimum concave-cost network flow problems: Applications, complexity, and algorithms
- Nonconvex generalized Benders decomposition for stochastic separable mixed-integer nonlinear programs
- Nonlinear integer programming for optimal allocation in stratified sampling
- On local search in d.c. optimization problems
- On the solution of concave knapsack problems
- Online Knapsack Problem Under Concave Functions
- Optimal Facility Location with Concave Costs
- Optimization on low rank nonconvex structures
- Quadratic knapsack problems
- Quasi-concave minimization subject to linear constraints
- Solving certain singly constrained convex optimization problems in production planning
- Solving the Fixed Charge Problem by Ranking the Extreme Points
- Solving the production transportation problem via a deterministic annealing neural network method
- Strongly polynomial algorithm for a production-transportation problem with concave production cost
- Strongly polynomial time algorithms for certain concave minimization problems on networks
- Tabu search and lower bounds for a combined production-transportation problem
- Technical note -- There's no free lunch: on the hardness of choosing a correct big-M in bilevel optimization
- The Nonlinear Resource Allocation Problem
- The quadratic knapsack problem -- a survey
- Tradeoff Curves, Targeting and Balancing in Manufacturing Queueing Networks
Cited in
(5)- A solution algorithm for non-convex mixed integer optimization problems with only few continuous variables
- On minimal valid inequalities for mixed integer conic programs
- scientific article; zbMATH DE number 4130198 (Why is no real title available?)
- A new solving procedure by m-M calculus for problems of constrained optimization
- Fiber-to-the-home passive optical distribution network design: a new formulation and valid inequalities using polar duality
This page was built for publication: A general purpose exact solution method for mixed integer concave minimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6112823)
