In the context of convex mixed-integer nonlinear programming (MINLP), we investigate how the outer approximation method and the generalized Benders decomposition method are affected when the respective NLP subproblems are solved inexactly. We show that the cuts in the corresponding master problems can be changed to incorporate the inexact residuals, still rendering equivalence and finiteness … Read more
We report and analyze the results of our extensive computational testing of branch-and-cut for piecewise linear optimization using the cutting planes given recently by Zhao and de Farias. Besides analysis of the performance of the cuts, we also analyze the effect of formulation on the performance of branch-and-cut. Finally, we report and analyze initial results … Read more
We give new facets and valid inequalities for the separable piecewise linear optimization knapsack polytope. We also extend the inequalities to the case in which some of the variables are semi-continuous. In a companion paper (de Farias, Gupta, Kozyreff, Zhao, 2011) we demonstrate the efficiency of the inequalities when used as cuts in a branch-and-cut … Read more
We consider the question of finding deep cuts from a model constructed with two rows of a simplex tableau. To do that, we show how to reduce the complexity of setting up the polar of such model from a quadratic number of integer hull computations to a linear number of integer hull computations. Furthermore we … Read more
Recent developments have drawn focus towards the efficient calculation of flows in AC power grids, which are difficult to solve systems of nonlinear equations. The common linearization approach leads to the well known and often used DC formulation, which has some major drawbacks. To overcome these drawbacks we revisit an alternative linearization of the AC … Read more
In this paper branching for attacking MILP is investigated. Under certain circumstances branches can be done concurrently. By introducing a new calculus it is shown there are restrictions for certain dual values and reduced costs. As a second unexpected result of this study a new class of cuts for MILP is found, which are defined … Read more
Pochet and Wolsey [Y. Pochet, L.A. Wolsey, Integer knapsack and flow covers with divisible coefficients: polyhedra, optimization and separation. Discrete Applied Mathematics 59(1995) 57-74] introduced partition inequalities for three substructures arising in various mixed integer programs, namely the integer knapsack set with nonnegative divisible/arbitrary coefficients and two forms of single-node capacitated flow set with divisible … Read more
We investigate the multi-trip elementary shortest path problem (MESPPRC) with resource constraints in which the objective is to find a shortest path between a source node and a sink node such that nodes other than the specified replenishment node are visited at most once and resource constraints are not violated. After each visit to the … Read more
In this paper, we propose a chance-constrained mathematical program for fixed broadband wireless networks under unreliable channel conditions. The model is reformulated as integer linear program and valid inequalities are derived for the corresponding polytope. Computational results show that by an exact separation approach the optimality gap is closed by 42 % on average. Article … Read more
Hierarchies of semidefinite programs have been used to approximate or even solve polynomial programs. This approach rapidly becomes computationally expensive and is often tractable only for problems of small size. In this paper, we propose a dynamic inequality generation scheme to generate valid polynomial inequalities for general polynomial programs. When used iteratively, this scheme improves … Read more