We consider a single machine scheduling problem to minimize the completion time variance of n jobs. This problem is known to be NP-hard and our contribution is to establish a novel bounding condition for a characterization of an optimal sequence. Specifically, we prove a necessary and sufficient condition (which can be verified in O(n\log n)) … Read more
We consider the class of 2-partition inequalities for the clique partitioning problem associated with complete graphs. We propose a heuristic separation algorithm for the inequalities and evaluate its usefulness in a cutting-plane algorithm. Our computational experiments fall into two parts. In the first part, we compare the LP objective values obtained by the proposed separator … Read more
Multi-modal distributed energy system planning is applied in the context of smart grids, industrial energy supply, and in the building energy sector. In real-world applications, these systems are commonly characterized by existing system structures of different age where monitoring and investment are conducted in a closed-loop, with the iterative possibility to invest. The literature contains … Read more
It is a challenging task to fairly compare local solvers and heuristics against each other and against global solvers. How does one weigh a faster termination time against a better quality of the found solution? In this paper, we introduce the confined primal integral, a new performance measure that rewards a balance of speed and … Read more
The generalization of MIP techniques to deal with nonlinear, potentially non-convex, constraints have been a fruitful direction of research for computational MINLP in the last decade. In this paper, we follow that path in order to extend another essential subroutine of modern MIP solvers towards the case of nonlinear optimization: the analysis of infeasible subproblems … Read more
The class of potential-driven network flow problems provides important models for a range of infrastructure networks that lead to hard-to-solve MINLPs in real-world applications. On large-scale meshed networks the relaxations usually employed are rather weak due to cycles in the network. To address this situation, we introduce the concept of ASTS orientations, a generalization of … Read more
Many practical integer programming problems involve variables with one or two-sided bounds. Dunkel and Schulz (2012) considered a strengthened version of Chvatal-Gomory (CG) inequalities that use 0-1 bounds on variables, and showed that the set of points in a rational polytope that satisfy all these strengthened inequalities is a polytope. Recently, we generalized this result … Read more
The restoration of a power system after an extended blackout starts around units with enhanced technical capabilities, referred to as black start units (BSUs). We examine the planning problem of optimally allocating these units on the grid subject to a budget constraint. We present a mixed integer programming model based on current literature in power … Read more
We study deep neural networks with binary activation functions (BDNN), i.e. the activation function only has two states. We show that the BDNN can be reformulated as a mixed-integer linear program which can be solved to global optimality by classical integer programming solvers. Additionally, a heuristic solution algorithm is presented and we study the model … Read more
We present a branch-and-bound algorithm for minimizing multiple convex quadratic objective functions over integer variables. Our method looks for efficient points by fixing subsets of variables to integer values and by using lower bounds in the form of hyperplanes in the image space derived from the continuous relaxations of the restricted objective functions. We show … Read more