Dual-feasible functions for integer programming and combinatorial optimization. Basics, extensions and applications (Q2634938)

The authors provide a textbook covering the topic of dual feasible functios (DFF), that were originally used to solve the problems involving the knapsack inequalities (like cuting, packing, scheduling etc.). A function \(f:[0,1]\rightarrow [0,1]\) is DFF if for any finite index set \(I\) of real numbers \(x_i\geq 0\), we have \(\sum_{i\in I}{x_i}\leq 1 \Rightarrow \sum_{i\in I}{f(x_i)}\leq 1\). The authors analyze the properties of such functions and present some generation techniques. Then they discuss the general DFF i.e., the functions \(f:\mathbb R\rightarrow \mathbb R\) defined in the same way. In the last chapter, some applications for cutting and packing problems are presented. All the results are illustrated with examples. There are also exercises with solutions ending each chapter. The book will be for sure interesting and useful for the graduate students in operations research, mathematics, optimization and similar areas, as well as for their lecturers. Also, more advanced undergraduate students could make use of this textbook.