We describe an implementation of the Feasibility Pump heuristic for nonconvex MINLPs. Our implementation takes advantage of three novel techniques, which we discuss here: a hierarchy of procedures for obtaining an integer solution, a generalized definition of the distance function that takes into account the nonlinear character of the problem, and the insertion of linearization … Read more
Akaike’s information criterion (AIC) is a measure of the quality of a statistical model for a given set of data. We can determine the best statistical model for a particular data set by the minimization of the AIC. Since we need to evaluate exponentially many candidates of the model by the minimization of the AIC, … Read more
We consider a challenging resource allocation problem arising in mobile wireless communications. The goal is to allocate the available channels and power in a so-called OFDMA system, in order to maximise the transmission rate, subject to quality of service (QoS) constraints. Standard MINLP software struggled to solve even small instances of this problem. Using outer … Read more
Feasibility pumps are highly effective primal heuristics for mixed-integer linear and nonlinear optimization. However, despite their success in practice there are only few works considering their theoretical properties. We show that feasibility pumps can be seen as alternating direction methods applied to special reformulations of the original problem, inheriting the convergence theory of these methods. … Read more
Optimization-based bound tightening (OBBT) is one of the most effective procedures to reduce variable domains of nonconvex mixed-integer nonlinear programs (MINLPs). At the same time it is one of the most expensive bound tightening procedures, since it solves auxiliary linear programs (LPs)—up to twice the number of variables many. The main goal of this paper … Read more
Traditional decomposition based branch-and-bound algorithms, like branch-and-price, can be very efficient if the duality gap is not too large. However, if this is not the case, the branch-and-bound tree may grow rapidly, preventing the method to find a good solution. In this paper, we present a new decompositon algorithm, called ADGO (Alternating Direction Global Optimization … Read more
The development of mathematical simulation and optimization models and algorithms for solving gas transport problems is an active field of research. In order to test and compare these models and algorithms, gas network instances together with demand data are needed. The goal of GasLib is to provide a set of publicly available gas network instances … Read more
We discuss an application of the well-known Multiplicative Weights Update (MWU) algorithm to non-convex and mixed-integer nonlinear programming. We present applications to: (a) the distance geometry problem, which arises in the positioning of mobile sensors and in protein conformation; (b) a hydro unit commitment problem arising in the energy industry, and (c) a class of … Read more
When using the standard McCormick inequalities twice to convexify trilinear monomials, as is often the practice in modeling and software, there is a choice of which variables to group first. For the important case in which the domain is a nonnegative box, we calculate the volume of the resulting relaxation, as a function of the … Read more
Expansion of natural gas networks is a critical process involving substantial capital expenditures with complex decision-support requirements. Given the non-convex nature of gas transmission constraints, global optimality and infeasibility guarantees can only be offered by global optimisation approaches. Unfortunately, state-of-the-art global optimisation solvers are unable to scale up to real-world size instances. In this study, … Read more