A new method for hard concave minimization problems based on a robust counterpart reformulation


Nowadays, many practical decision problems are solved using modern mathematical optimization techniques. Convexity plays a crucial role in optimization. Large-scale convex problems with thousands to millions of variables and/or constraints can be solved in minutes due to very efficient algorithms and solvers. In practice, however, often the cost function is concave, due to economies of scale. These optimization problems are hard to solve. In general, only medium-scale concave problems can be solved in reasonable time even when the mathematical constraints are very simple.
The project’s main goal is to develop an efficient method to approximately solve large-scale optimization problems that have concave cost functions and linear (or convex) constraints. We propose a new approach: reformulate the concave optimization problem as a so-called adjustable robust linear optimization problem. Very efficient approaches have been developed to (approximately) solve such large-scale adjustable robust linear optimization problems. Preliminary numerical results are very promising. Moreover, we investigate two new ideas to significantly improve the so-called decision rules while controlling computational tractability. Decision rules are needed for the adjustable variables in the adjustable robust reformulation.
The most important test case will be the optimal food supply-chain problem for the World Food Programme (WFP). In the currently used supply-chain model it is assumed that, e.g., the warehousing, inventory and transportation costs are linear. However, often these costs are a concave function of the throughput due to economies of scale. Solving these large-scale concave problems will lead to a significant efficiency gain in WFP’s food supply.





Prof. dr. ir. D. den Hertog

Verbonden aan

Tilburg University, Tilburg School of Economics and Management (TiSEM), Econometrie & Operations Research


01/09/2019 tot 31/08/2023