Intersection cuts for convex mixed integer programs from translated cones

We develop a general framework for linear intersection cuts for convex integer programs with full-dimensional feasible regions by studying integer points of their translated tangent cones, generalizing the idea of Balas (1971). For proper (i.e, full-dimensional, closed, convex, pointed) translated cones with fractional vertices, we show that under certain mild conditions all intersection cuts are indeed valid for the integer hull, and a large class of valid inequalities for the integer hull are intersection cuts, computable via polyhedral approximations. We also give necessary conditions for a class of valid inequalities to be tangent halfspaces of the integer hull of proper translated cones. We also show that valid inequalities for non-pointed regular translated cones can be derived as intersection cuts for associated proper translated cones under some mild assumptions.     

Integrating nonlinear branch-and-bound and outer approximation for convex Mixed Integer Nonlinear Programming

In this paper, we present a new hybrid algorithm for convex Mixed Integer Nonlinear Programming (MINLP). The proposed hybrid algorithm is an improved version of the classical nonlinear branch-and-bound (BB) procedure, where the enhancements are obtained with the application of the outer approximation algorithm on some nodes of the enumeration tree. The two methods are combined in such a way that each one collaborates to the convergence of the other. Computational experiments with benchmark instances of the MINLP problem show the good performance of the proposed algorithm, which is compared to the outer approximation algorithm, the nonlinear BB algorithm and the hybrid algorithm implemented in the solver Bonmin.     

Integer programming duality: Price functions and sensitivity analysis

Recently a duality theory for integer programming has been developed. Here we examine some of the economic implications of this theory, in particular the necessity of using price functions in place of prices, and the possibility of carrying out sensitivity analysis of optimal solutions. In addition we consider the form of price functions that are generated by known algorithms for integer programming.This research was supported in part by a Senior Visiting Research Fellowship from the Science Research Council at the London School of Economics while the author was on leave from CORE, Université Catholique de Louvain, at Louvain-la-Neuve.     

A convex analysis approach for convex multiplicative programming

Global optimization problems involving the minimization of a product of convex functions on a convex set are addressed in this paper. Elements of convex analysis are used to obtain a suitable representation of the convex multiplicative problem in the outcome space, where its global solution is reduced to the solution of a sequence of quasiconcave minimizations on polytopes. Computational experiments illustrate the performance of the global optimization algorithm proposed.      

Integer programming and pricing revisited

Three applications of duality are mentioned: mathematical, computational,and economic. One of the earliest attempts toproduce a dualof an integer programme with economic interpretations was byGomory & Baumol in 1960. This is describedtogether withits economic properties and some refinements and corrections.A more recent integer programming dual due to Chvátal,whose main use to date has been computational, is then described.It is shown that this can be given an economic interpretationas a generalization of Gomory & Baumol‘s dual whichrectifies some of the deficiencies of the latter. The computationalproblems of calculating Chvátal’s dual are remarkedon.     

Multistage stochastic programming: Error analysis for the convex case

We consider convex stochastic multistage problems and present an approximation technique which allows to analyse the error with respect to time. The technique is based on barycentric approximation of conditional and marginal probability spaces and requiresstrict nonanticipativity for the constraint multifunction and thesaddle property for the value functions.Part of this work was carried out at the Institute of Operations Research of the University of Zurich.     

Discrepancy and convex programming

Summary The pertinence of convexity arguments in the study of discrepancy of sequences is exhibited. The usefulness of this viewpoint can be twofold. Firstly, it allows the interpretation of the problem of estimating the discrepancy as a problem in convex programming in important cases. Secondly, it helps to restrict the family of sets which have to be considered when evaluating the usual (or extreme) discrepancy and the isotrope discrepancy of sequences. In particular, in the latter case it suffices to look at a rather special class of convex polytopes. Entrata in Redazione il 27 maggio 1971. Some results of this paper were presented in an address delivered at the Conference on Analytic Number Theory, Carbondale, Ill., October 22–24, 1970.     

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.     

Optimal 3-terminal cuts and linear programming

Given an undirected graph G=(V,E) and three specified terminal nodes t ₁,t ₂,t ₃, a 3-cut is a subset A of E such that no two terminals are in the same component of G\A. If a non-negative edge weight c _e is specified for each e∈E, the optimal 3-cut problem is to find a 3-cut of minimum total weight. This problem is -hard, and in fact, is max- -hard. An approximation algorithm having performance guarantee has recently been given by Călinescu, Karloff, and Rabani. It is based on a certain linear-programming relaxation, for which it is shown that the optimal 3-cut has weight at most times the optimal LP value. It is proved here that can be improved to , and that this is best possible. As a consequence, we obtain an approximation algorithm for the optimal 3-cut problem having performance guarantee . In addition, we show that is best possible for this algorithm. Research of this author was supported by NSERC PGSB. Research supported by a grant from NSERC of Canada.     

Feasible partition problem in reverse convex and convex mixed-integer programming

In this paper we consider the consistent partition problem in reverse convex and convex mixed-integer programming. In particular we will show that for the considered classes of convex functions, both integer and relaxed systems can be partitioned into two disjoint subsystems, each of which is consistent and defines an unbounded region. The polynomial time algorithm to generate the partition will be proposed and the algorithm for a maximal partition will also be provided.     

Partly convex programming and zermelo's navigation problems

Mathematical programs, that become convex programs after freezing some variables, are termed partly convex. For such programs we give saddle-point conditions that are both necessary and sufficient that a feasible point be globally optimal. The conditions require cooperation of the feasible point tested for optimality, an assumption implied by lower semicontinuity of the feasible set mapping. The characterizations are simplified if certain point-to-set mappings satisfy a sandwich condition.The tools of parametric optimization and basic point-to-set topology are used in formulating both optimality conditions and numerical methods. In particular, we solve a large class of Zermelo's navigation problems and establish global optimality of the numerical solutions.Research partly supported by NSERC of Canada.     

Calibration and convex programming: two approaches to one problem

Calibration is a common technique of data processing in survey sampling. Although convex programming would be an obvious tool for this purpose, usually other methods are used in the practice of statistical institutes. A comparison of those methods and convex programming is reported on in this paper.     

Conditions for boundedness in concave programming under reverse convex and convex constraints

In this paper, we are concerned with the problem of boundedness in the constrained global maximization of a convex function. In particular, we present necessary and sufficient conditions for boundedness of a feasible region defined by reverse convex constraints and we establish sufficient and necessary conditions for existence of an upper bound for a convex objective function defined over the system of concave inequality constraints. We also address the problem of boundedness in the global maximization problem when a feasible region is convex and unbounded.     

Integer programming, Barvinok's counting algorithm and Gomory relaxations

We propose an algorithm based on Barvinok's counting algorithm for . It runs in time polynomial in the input size of when n is fixed, and under a condition on c, provides the optimal value of . We also relate Barvinok's counting formula and Gomory relaxations.