We describe strong mixed-integer programming formulations for robust mixed 0-1 programming with uncertainty in the objective coefficients. In particular, we focus on an objective uncertainty set described as a polytope with a budget constraint. We show that for a robust 0-1 problem, there is a tight linear programming formulation with size polynomial in the size … Read more
Interior-point methods (IPMs), originally conceived in the context of linear programming have found a variety of applications in integer programming, and combinatorial optimization. This survey presents an up to date account of IPMs in solving NP-hard combinatorial optimization problems to optimality, and also in developing approximation algorithms for some of them. The surveyed approaches include … Read more
This paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under uncertainty. We show that the classical (l,S) inequalities for the deterministic lot-sizing polytope are also valid for the stochastic lot-sizing polytope. We then extend the (l,S) inequalities to a general class of valid inequalities, called the (Q,S_Q) inequalities, and we … Read more
This paper is motivated by problem of optimal shape design of laminated elastic bodies. We use a recently introduced model of delamination, based on minimization of potential energy which includes the free (Gibbs-type) energy and (pseudo)potential of dissipative forces, to introduce and analyze a special mathematical program with equilibrium constraints. The equilibrium is governed by … Read more
This problem deals with the uncapacitated multiple allocation hub location problem. The dual problem of a four-indexed formulation is considered and a heuristic method, based on a dual-ascent technique, is designed. This heuristic, which is reinforced with several specifical subroutines and does not require any external linear problem solver, is the core tool embedded in … Read more
We study capacitated network flow problems with supplies and demands defined on a countably infinite collection of nodes having finite degree. This class of network flow models includes, for example, all infinite horizon deterministic dynamic programs with finite action sets since these are equivalent to the problem of finding a shortest infinite path in an … Read more
Process synthesis problems can be mathematically represented as mixed-integer nonlinear programming (MINLP) models, which are often irregular, large and non-convex and difficult to get the overall optimum by traditional method. In this paper, a new method named particle swarm optimization (PSO) is used to solve MINLP problems. By introduced penalty function and used sigmoid function, … Read more
This paper presents a new method for solving global optimization problems. We use a local technique based on the notion of discrete gradients for finding a cone of descent directions and then we use a global cutting angle algorithm for finding global minimum within the intersection of the cone and the feasible region. We present … Read more
Sufficient optimality criteria for linearly constrained, concave minimization problems is given in this paper. Our optimality criteria is based on the sensitivity analysis of the relaxed linear programming problem. Our main result is similar to that of Phillips and Rosen (1993), however our proofs are simpler and constructive. Phillips and Rosen (1993) in their paper … Read more
The natural approach for describing network flow problems is to introduce side constraints that capture restrictions of a logical or technological nature, e.g., capacity constraints. We study the traffic equilibria arising from selfish routing of individual users in networks with side constraints. We examine first the case of linear latency functions. Under very general assumptions … Read more