In this paper, we analyze mixed 0-1 linear programs under objective uncertainty. The mean vector and the second moment matrix of the nonnegative objective coefficients is assumed to be known, but the exact form of the distribution is unknown. Our main result shows that computing a tight upper bound on the expected value of a … Read more
Mixed Integer Nonlinear Programming (MINLP) problems present two main challenges: the integrality of a subset of variables and nonconvex (nonlinear) objective function and constraints. Many exact solvers for MINLP are branch-and-bound algorithms that compute a lower bound on the optimal solution using a linear programming relaxation of the original problem. In order to solve these … Read more
The classical branch-and-bound algorithm for the integer feasibility problem has exponential worst case complexity. We prove that it is surprisingly efficient on reformulations, in which the columns of the constraint matrix are short, and near orthogonal, i.e. a reduced basis of the generated lattice; when the entries of A (i.e. the dense part of the … Read more
This paper surveys results on the NP-hard mixed-integer quadratically constrained programming problem. The focus is strong convex relaxations and valid inequalities, which can become the basis of efficient global techniques. In particular, we discuss relaxations and inequalities arising from the algebraic description of the problem as well as from dynamic procedures based on disjunctive programming. … Read more
Research efforts of the past fifty years have led to a development of linear integer programming as a mature discipline of mathematical optimization. Such a level of maturity has not been reached when one considers nonlinear systems subject to integrality requirements for the variables. This chapter is dedicated to this topic. The primary goal is … Read more
In this paper, the first approach for solving the vertex-biconnectivity augmentation problem (V2AUG) to optimality is proposed. Given a spanning subgraph of an edge-weighted graph, we search for the cheapest subset of edges to augment this subgraph in order to make it vertex-biconnected. The problem is reduced to the augmentation of the corresponding block-cut tree, … Read more
Global optimization algorithms, e.g., spatial branch-and-bound approaches like those implemented in codes such as BARON and COUENNE, have had substantial success in tackling complicated, but generally small scale, non-convex MINLPs (i.e., mixed-integer nonlinear programs having non-convex continuous relaxations). Because they are aimed at a rather general class of problems, the possibility remains that larger instances … Read more
Given a valid inequality for the mixed integer infinite group relaxation, a lifting based approach is presented that can be used to strengthen this inequality. Bounds on the solution of the corresponding lifting problem and some necessary conditions for the lifted inequality to be minimal for the mixed integer infinite group relaxation are presented. Finally, … Read more
A suggested program with fuzzy linear fractional objective and integer decision variables (FILFP) is considered. The fuzzy coefficients are involved in the numerator of the linear objective function and can be characterized by trapezoidal fuzzy numbers. The purpose of this paper is to outline an algorithm available to solve (FILFP). In addition, an illustrative example … Read more
A simple relaxation of two rows of a simplex tableau is a mixed integer set consisting of two equations with two free integer variables and non-negative continuous variables. Recently Andersen et al. (2007) and Cornuejols and Margot (2007) showed that the facet-defining inequalities of this set are either split cuts or intersection cuts obtained from … Read more