Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming
86
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global epsilon-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solver can often successfully handle a moderate presence of nonconvexities, which opens the door for the use of potentially tighter nonconvex relaxations. In this work, we exploit this fact and make use of a nonconvex relaxation obtained via aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in an MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithms ability to generate strong dual bounds through extensive computational experiments.
rate research
Read More
In this paper, we consider the problem of joint antenna selection and analog beamformer design in downlink single-group multicast networks. Our objective is to reduce the hardware costs by minimizing the number of required phase shifters at the transmitter while fulfilling given distortion limits at the receivers. We formulate the problem as an L0 minimization problem and devise a novel branch-and-cut based algorithm to solve the resulting mixed-integer nonlinear program to optimality. We also propose a suboptimal heuristic algorithm to solve the above problem approximately with a low computational complexity. Computational results illustrate that the solutions produced by the proposed heuristic algorithm are optimal in most cases. The results also indicate that the performance of the optimal methods can be significantly improved by initializing with the result of the suboptimal method.
We study robust convex quadratic programs where the uncertain problem parameters can contain both continuous and integer components. Under the natural boundedness assumption on the uncertainty set, we show that the generic problems are amenable to exact copositive programming reformulations of polynomial size. These convex optimization problems are NP-hard but admit a conservative semidefinite programming (SDP) approximation that can be solved efficiently. We prove that the popular approximate S-lemma method --- which is valid only in the case of continuous uncertainty --- is weaker than our approximation. We also show that all results can be extended to the two-stage robust quadratic optimization setting if the problem has complete recourse. We assess the effectiveness of our proposed SDP reformulations and demonstrate their superiority over the state-of-the-art solution schemes on instances of least squares, project management, and multi-item newsvendor problems.
We study the problem of learning a linear model to set the reserve price in an auction, given contextual information, in order to maximize expected revenue from the seller side. First, we show that it is not possible to solve this problem in polynomial time unless the emph{Exponential Time Hypothesis} fails. Second, we present a strong mixed-integer programming (MIP) formulation for this problem, which is capable of exactly modeling the nonconvex and discontinuous expected reward function. Moreover, we show that this MIP formulation is ideal (i.e. the strongest possible formulation) for the revenue function of a single impression. Since it can be computationally expensive to exactly solve the MIP formulation in practice, we also study the performance of its linear programming (LP) relaxation. Though it may work well in practice, we show that, unfortunately, in the worst case the optimal objective of the LP relaxation can be O(number of samples) times larger than the optimal objective of the true problem. Finally, we present computational results, showcasing that the MIP formulation, along with its LP relaxation, are able to achieve superior in- and out-of-sample performance, as compared to state-of-the-art algorithms on both real and synthetic datasets. More broadly, we believe this work offers an indication of the strength of optimization methodologies like MIP to exactly model intrinsic discontinuities in machine learning problems.
Cutting plane methods play a significant role in modern solvers for tackling mixed-integer programming (MIP) problems. Proper selection of cuts would remove infeasible solutions in the early stage, thus largely reducing the computational burden without hurting the solution accuracy. However, the major cut selection approaches heavily rely on heuristics, which strongly depend on the specific problem at hand and thus limit their generalization capability. In this paper, we propose a data-driven and generalizable cut selection approach, named Cut Ranking, in the settings of multiple instance learning. To measure the quality of the candidate cuts, a scoring function, which takes the instance-specific cut features as inputs, is trained and applied in cut ranking and selection. In order to evaluate our method, we conduct extensive experiments on both synthetic datasets and real-world datasets. Compared with commonly used heuristics for cut selection, the learning-based policy has shown to be more effective, and is capable of generalizing over multiple problems with different properties. Cut Ranking has been deployed in an industrial solver for large-scale MIPs. In the online A/B testing of the product planning problems with more than $10^7$ variables and constraints daily, Cut Ranking has achieved the average speedup ratio of 12.42% over the production solver without any accuracy loss of solution.
We propose a dual dynamic integer programming (DDIP) framework for solving multi-scale mixed-integer model predictive control (MPC) problems. Such problems arise in applications that involve long horizons and/or fine temporal discretizations as well as mixed-integer states and controls (e.g., scheduling logic and discrete actuators). The approach uses a nested cutting-plane scheme that performs forward and backward sweeps along the time horizon to adaptively approximate cost-to-go functions. The DDIP scheme proposed can handle general MPC formulations with mixed-integer controls and states and can perform forward-backward sweeps over block time partitions. We demonstrate the performance of the proposed scheme by solving mixed-integer MPC problems that arise in the scheduling of central heating, ventilation, and air-conditioning (HVAC) plants. We show that the proposed scheme is scalable and dramatically outperforms state-of-the-art mixed-integer solvers.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
