The value function of an infinite-horizon single-item lot-sizing problem

We characterize the value function of a discounted infinite-horizon version of the single-item lot-sizing problem. As corollaries, we show that this value function inherits several properties of finite, mixed-integer program value functions; namely, it is subadditive, lower semicontinuous, and piecewise linear.     

Evaluating mixed-integer programming models over multiple right-hand sides

A critical measure of model quality for a mixed-integer program (MIP) is the difference, or gap, between its optimal objective value and that of its linear programming relaxation. In some cases, the right-hand side is not known exactly; however, there is no consensus metric for evaluating a MIP model when considering multiple right-hand sides. In this paper, we provide model formulations for the expectation and extrema of absolute and relative MIP gap functions over finite discrete sets.     

Continuity of the optimal value function and optimal solutions of parametric mixed-integer quadratic programs

To properly describe and solve complex decision problems, research on theoretical properties and solution of mixed-integer quadratic programs is becoming very important. We establish in this paper different Lipschitz-type continuity results about the optimal value function and optimal solutions of mixed-integer parametric quadratic programs with parameters in the linear part of the objective function and in the right-hand sides of the linear constraints. The obtained results extend some existing results for continuous quadratic programs, and, more importantly, lay the foundation for further theoretical study and corresponding algorithm analysis on mixed-integer quadratic programs.     

A Gilmore-Gomory construction of integer programming value functions

In this paper, we analyze how sequentially introducing decision variables into an integer program (IP) affects the value function and its level sets. We use a Gilmore-Gomory approach to find parametrized IP value functions over a restricted set of variables. We introduce the notion of maximal connected subsets of level sets - volumes in which changes to the constraint right-hand side have no effect on the value function - and relate these structures to IP value functions and optimal solutions.     

Parametric error bounds for convex approximations of two-stage mixed-integer recourse models with a random second-stage cost vector

We consider two-stage recourse models with integer restrictions in the second stage. These models are typically non-convex and hence, hard to solve. There exist convex approximations of these models with accompanying error bounds. However, it is unclear how these error bounds depend on the distributions of the second-stage cost vector q. In this paper, we derive parametric error bounds whose dependence on the distribution of q is explicit: they scale linearly in the expected value of the ${?}_1$-norm of q.     

A decomposition heuristic for mixed-integer supply chain problems

Mixed-integer supply chain models typically are very large but are also very sparse and can be decomposed into loosely coupled blocks. In this paper, we use general-purpose techniques to obtain a block decomposition of supply chain instances and apply a tailored penalty alternating direction method, which exploits the structural properties of the decomposed instances. We further describe problem-specific enhancements of the algorithm and present numerical results on real-world instances that illustrate the applicability of the approach.     

Retrospective optimization of mixed-integer stochastic systems using dynamic simplex linear interpolation

We propose a family of retrospective optimization (RO) algorithms for optimizing stochastic systems with both integer and continuous decision variables. The algorithms are continuous search procedures embedded in a RO framework using dynamic simplex interpolation (RODSI). By decreasing dimensions (corresponding to the continuous variables) of simplex, the retrospective solutions become closer to an optimizer of the objective function. We present convergence results of RODSI algorithms for stochastic “convex” systems. Numerical results show that a simple implementation of RODSI algorithms significantly outperforms some random search algorithms such as Genetic Algorithm (GA) and Particle Swarm Optimization (PSO).     

Integer and mixed-integer programming models: General properties

It is well known that mixed-integer formulations can be used tomodel important classes of nonconvex functions, such as fixed-charge functions and linear economy-of-scale cost functions. The purpose of this paper is to formulate a rigorous definition of a mixed-integer model of a given function and to study the properties of the functions that can be so modelled. An interesting byproduct of this approach is the identification of a simple class of functions that cannot be modelled by computer-representable mixed-integer formulations, even though mixed-integer models based on the use of a single arbitrary irrational constant are available for this class.This research was sponsored by the United States Army under Contract No. DA-31-124-ARO-D-462.     

Univariate parameterization for global optimization of mixed-integer polynomial problems

This paper presents a new relaxation technique to globally optimize mixed-integer polynomial programming problems that arise in many engineering and management contexts. Using a bilinear term as the basic building block, the underlying idea involves the discretization of one of the variables up to a chosen accuracy level (Teles, J.P., Castro, P.M., Matos, H.A. (2013). Multiparametric disaggregation technique for global optimization of polynomial programming problems. J. Glob. Optim. 55, 227–251), by means of a radix-based numeric representation system, coupled with a residual variable to effectively make its domain continuous. Binary variables are added to the formulation to choose the appropriate digit for each position together with new sets of continuous variables and constraints leading to the transformation of the original mixed-integer non-linear problem into a larger one of the mixed-integer linear programming type. The new underestimation approach can be made as tight as desired and is shown capable of providing considerably better lower bounds than a widely used global optimization solver for a specific class of design problems involving bilinear terms.     

Global optimization of signomial mixed-integer nonlinear programming problems with free variables

Mixed-integer nonlinear programming (MINLP) problems involving general constraints and objective functions with continuous and integer variables occur frequently in engineering design, chemical process industry and management. Although many optimization approaches have been developed for MINLP problems, these methods can only handle signomial terms with positive variables or find a local solution. Therefore, this study proposes a novel method for solving a signomial MINLP problem with free variables to obtain a global optimal solution. The signomial MINLP problem is first transformed into another one containing only positive variables. Then the transformed problem is reformulated as a convex mixed-integer program by the convexification strategies and piecewise linearization techniques. A global optimum of the signomial MINLP problem can finally be found within the tolerable error. Numerical examples are also presented to demonstrate the effectiveness of the proposed method.     

Lagrangian decomposition and mixed-integer quadratic programming reformulations for probabilistically constrained quadratic programs

Probabilistically constrained quadratic programming (PCQP) problems arise naturally from many real-world applications and have posed a great challenge in front of the optimization society for years due to the nonconvex and discrete nature of its feasible set. We consider in this paper a special case of PCQP where the random vector has a finite discrete distribution. We first derive second-order cone programming (SOCP) relaxation and semidefinite programming (SDP) relaxation for the problem via a new Lagrangian decomposition scheme. We then give a mixed integer quadratic programming (MIQP) reformulation of the PCQP and show that the continuous relaxation of the MIQP is exactly the SOCP relaxation. This new MIQP reformulation is more efficient than the standard MIQP reformulation in the sense that its continuous relaxation is tighter than or at least as tight as that of the standard MIQP. We report preliminary computational results to demonstrate the tightness of the new convex relaxations and the effectiveness of the new MIQP reformulation.     

Normal families and value distribution in connection with composite functions

We prove a value distribution result which has several interesting corollaries. Let k∈N, let α∈C and let f be a transcendental entire function with order less than 1/2. Then for every nonconstant entire function g, we have that (f○g)^(k)−α has infinitely many zeros. This result also holds when k=1, for every transcendental entire function g. We also prove the following result for normal families. Let k∈N, let f be a transcendental entire function with ρ(f)<1/k, and let a₀,…,ak−1,a be analytic functions in a domain Ω. Then the family of analytic functions g such that

     

A geometric way to build strong mixed-integer programming formulations

We give an explicit geometric way to build mixed-integer programming (MIP) formulations for unions of polyhedra. The construction is simply described in terms of spanning hyperplanes in an $r$-dimensional linear space. The resulting MIP formulation is ideal, and uses exactly $r$ integer variables and $2\times \left(\#\text{of spanning hyperplanes}\right)$ general inequality constraints. We use this result to derive novel logarithmic-sized ideal MIP formulations for discontinuous piecewise linear functions and structures appearing in robotics and power systems problems.     

A trust region SQP algorithm for mixed-integer nonlinear programming

We propose a modified sequential quadratic programming method for solving mixed-integer nonlinear programming problems. Under the assumption that integer variables have a smooth influence on the model functions, i.e., that function values do not change drastically when in- or decrementing an integer value, successive quadratic approximations are applied. The algorithm is stabilized by a trust region method with Yuan’s second order corrections. It is not assumed that the mixed-integer program is relaxable or, in other words, function values are evaluated only at integer points. The Hessian of the Lagrangian function is approximated by a quasi-Newton update formula subject to the continuous and integer variables. Numerical results are presented for a set of 80 mixed-integer test problems taken from the literature. The surprising result is that the number of function evaluations, the most important performance criterion in practice, is less than the number of function calls needed for solving the corresponding relaxed problem without integer variables.     

Models for representing piecewise linear cost functions

We study formulations of linear programs with piecewise linear objective functions with and without additional binary variables. We show that the two formulations without additional binary variables have the same LP bounds as those of the corresponding formulations with binary variables and therefore are preferable for efficient computation.     

A new approach to the representation of trigonometric and hyperbolic functions by infinite products

An innovative technique is developed for obtaining infinite product representations for some elementary functions. The technique is based on the comparison of alternative expressions of Green's functions constructed by two different methods. Some standard boundary value problems are considered posed for two-dimensional Laplace equation on regions of a regular configuration. Classical closed analytic form of Green's functions for such problems are compared against those obtained by the method of images in the form of infinite products. This yields a number of new infinite product representations for trigonometric and hyperbolic functions.     

Analytical representation of concave and quasiconcave homogeneous functions

The formula which implements bijection between the class of concave linearly homogeneous functions defined on the nonnegative orthant of an arithmetic space and the simpler class of concave functions defined on the standard (probabilistic) simplex is presented. Two generalizations of this formula for analytical representation of quasiconcave homogeneous function are also proposed. These formulas particularly extend opportunities of modelling production objects and consumption.