The Quadratic Unconstrained Binary Optimization (QUBO) model has gained prominence in recent years with the discovery that it unifies a rich variety of combinatorial optimization problems. By its association with the Ising problem in physics, the QUBO model has emerged as an underpinning of the quantum computing area known as quantum annealing and has become … Read more
A system-interdiction problem can be modeled as a bilevel program in which the upper level models interdiction decisions and the lower level models system operation. This paper studies MILSIP, a mixed-integer linear system interdiction problem, which assumes binary interdiction decisions and models system operations through a mixed-integer linear program. To solve large-scale instances of MILSIP, … Read more
We describe strong convex valid inequalities for conic quadratic mixed 0-1 optimization. These inequalities can be utilized for solving numerous practical nonlinear discrete optimization problems from value-at-risk minimization to queueing system design, from robust interdiction to assortment optimization through appropriate conic quadratic mixed 0-1 relaxations. The inequalities exploit the submodularity of the binary restrictions and … Read more
The advances in conic optimization have led to its increased utilization for modeling data uncertainty. In particular, conic mean-risk optimization gained prominence in probabilistic and robust optimization. Whereas the corresponding conic models are solved efficiently over convex sets, their discrete counterparts are intractable. In this paper, we give a highly effective successive quadratic upper-bounding procedure … Read more
We introduce the noncooperative fixed charge transportation problem (NFCTP), which is a game-theoretic extension of the fixed charge transportation problem. In the NFCTP, competing players solve coupled fixed charge transportation problems simultaneously. Three versions of the NFCTP are discussed and compared, which differ in their treatment of shared social costs. This may be used from … Read more
Large Neighborhood Search (LNS) heuristics are among the most powerful but also most expensive heuristics for mixed integer programs (MIP). Ideally, a solver learns adaptively which LNS heuristics work best for the MIP problem at hand in order to concentrate its limited computational budget. To this end, this work introduces Adaptive Large Neighborhood Search (ALNS) … Read more
Influence maximization aims at identifying a limited set of key individuals in a (social) network which spreads information based on some propagation model and maximizes the number of individuals reached. We show that influence maximization based on the probabilistic independent cascade model can be modeled as a stochastic maximal covering location problem. A reformulation based … Read more
Weighted or reweighted strategies have not been considered for sparsity constrained optimization. In this paper, we reformulate the sparsity constraint as an equivalent weighted l1-norm constraint in the sparsity constrained optimization problem. To solve the reformulated problem, we investigate the problem in the Lagrange dual framework, and prove that the strong duality property holds. Then … Read more
Given a factorable function f, we propose a procedure that constructs a concave underestimor of f that is tight at a given point. These underestimators can be used to generate intersection cuts. A peculiarity of these underestimators is that they do not rely on a bounded domain. We propose a strengthening procedure for the intersection … Read more
We present well known properties related to the topology of Steiner minimal trees and to the geometric position of Steiner points, and investigate their application in the main exact algorithms that have been proposed for the Euclidean Steiner problem. We discuss the difficulty in the application of properties that were very successfully applied to solve … Read more