Order selection on a single machine with high set-up costs

We study the problem of allocating a limited quantity of a single manufacturing resource to produce a subset of possible part-types. Customer orders require one or more part-types. We assume that revenue is received for an order only if it is completely filled, and that set-up costs and order revenues dominate the variable costs of production. We present a heuristic for the solution of our problem, as well as families of cutting-planes for an integer programming formulation. Computational results on a set of random test problems indicate that the heuristic is quite effective in producing near optimal solutions. The cutting-planes appear to be quite useful in reducing the number of linear programming solutions required by branch-and-bound.     

Exact Penalty Functions for Nonlinear Integer Programming Problems

In this work, we study exact continuous reformulations of nonlinear integer programming problems. To this aim, we preliminarily state conditions to guarantee the equivalence between pairs of general nonlinear problems. Then, we prove that optimal solutions of a nonlinear integer programming problem can be obtained by using various exact penalty formulations of the original problem in a continuous space.     

Some properties of convex hulls of integer points contained in general convex sets

In this paper, we study properties of general closed convex sets that determine the closedness and polyhedrality of the convex hull of integer points contained in it. We first present necessary and sufficient conditions for the convex hull of integer points contained in a general convex set to be closed. This leads to useful results for special classes of convex sets such as pointed cones, strictly convex sets, and sets containing integer points in their interior. We then present a sufficient condition for the convex hull of integer points in general convex sets to be a polyhedron. This result generalizes the well-known result due to Meyer (Math Program 7:223–225, 1974). Under a simple technical assumption, we show that these sufficient conditions are also necessary for the convex hull of integer points contained in general convex sets to be a polyhedron.     

Lot-sizing with fixed charges on stocks: the convex hull

In this paper, we examine a variant of the uncapacitated lot-sizing model of Wagner–Whitin that includes fixed charges on the stocks. Such a model is natural in a production environment where stocking is a complex operation, and appears as a subproblem in more general network design problems.

Linear-programming formulations, a dynamic program, the convex hull of integer solutions and a separation algorithm are presented. All these turn out to be very natural extensions of the corresponding results of Barany et al. (Math. Programming Stud. 22 (1984) 32) for the uncapacitated lot-sizing problem. The convex hull proof is based on showing that an extended facility location formulation is tight and by projecting it onto the original space of variables.     

pth Power Lagrangian Method for Integer Programming

When does there exist an optimal generating Lagrangian multiplier vector (that generates an optimal solution of an integer programming problem in a Lagrangian relaxation formulation), and in cases of nonexistence, can we produce the existence in some other equivalent representation space? Under what conditions does there exist an optimal primal-dual pair in integer programming? This paper considers both questions. A theoretical characterization of the perturbation function in integer programming yields a new insight on the existence of an optimal generating Lagrangian multiplier vector, the existence of an optimal primal-dual pair, and the duality gap. The proposed pth power Lagrangian method convexifies the perturbation function and guarantees the existence of an optimal generating Lagrangian multiplier vector. A condition for the existence of an optimal primal-dual pair is given for the Lagrangian relaxation method to be successful in identifying an optimal solution of the primal problem via the maximization of the Lagrangian dual. The existence of an optimal primal-dual pair is assured for cases with a single Lagrangian constraint, while adopting the pth power Lagrangian method. This paper then shows that an integer programming problem with multiple constraints can be always converted into an equivalent form with a single surrogate constraint. Therefore, success of a dual search is guaranteed for a general class of finite integer programming problems with a prominent feature of a one-dimensional dual search.     

Minimum power multicasting in wireless networks under probabilistic node failures

In this paper we deal with a probabilistic extension of the minimum power multicast (MPM) problem for wireless networks. The deterministic MPM problem consists in assigning transmission powers to the nodes, so that a multihop connection can be established between a source and a given set of destination nodes and the total power required is minimized. We present an extension to the basic problem, where node failure probabilities for the transmission are explicitly considered. This model reflects the necessity of taking uncertainty into account in the availability of the hosts. The novelty of the probabilistic minimum power multicast (PMPM) problem treated in this paper consists in the minimization of the assigned transmission powers, imposing at the same time a global reliability level to the solution network. An integer linear programming formulation for the PMPM problem is presented. Furthermore, an exact algorithm based on an iterative row and column generation procedure, as well as a heuristic method are proposed. Computational experiments are finally presented.     

Convex hull representations of models for computing collisions between multiple bodies

In this paper, we consider a collision detection problem that frequently arises in the field of robotics. Given a set of bodies with their initial positions and trajectories, we wish to identify the first collision that occurs between any two bodies, or to determine that none exists. For the case of bodies having linear trajectories, we construct a convex hull representation of the integer programming model of S.Z. Selim and H.A. Almohamad [European Journal of Operational Research 119 (1) (1999) 121–129], and compare the relative effectiveness in solving this problem via the resultant linear program. We also extend this analysis to model a situation in which bodies move along piecewise linear trajectories, possibly rotating at the end of each linear segment. For this case, we again compare an integer programming approach with its linear programming convex hull representation, and exhibit the effectiveness of solving a sequence of mathematical programs for each time segment over a global programming scheme which considers all segments at once. We provide computational results to illustrate the effect of various numbers of bodies present in the collision scenarios, as well as the times at which the first collision occurs.     

Optimal control of nonlinear evolution inclusions

In this paper, we study the optimal control of nonlinear evolution inclusions. First, we prove the existence of admissible trajectories and then we show that the set that they form is relatively sequentially compact and in certain cases sequentially compact in an appropriate function space. Then, with the help of a convexity hypothesis and using Cesari's approach, we solve a general Lagrange optimal control problem. After that, we drop the convexity hypothesis and pass to the relaxed system, for which we prove the existence of optimal controls, we show that it has a value equal to that of the original one, and also we prove that the original trajectories are dense in an appropriate topology to the relaxed ones. Finally, we present an example of a nonlinear parabolic optimal control that illustrates the applicability of our results.This research was supported by NSF Grant No. DMS-88-02688.     

Theoretical challenges towards cutting-plane selection

While many classes of cutting-planes are at the disposal of integer programming solvers, our scientific understanding is far from complete with regards to cutting-plane selection, i.e., the task of selecting a portfolio of cutting-planes to be added to the LP relaxation at a given node of the branch-and-bound tree. In this paper we review the different classes of cutting-planes available, known theoretical results about their relative strength, important issues pertaining to cut selection, and discuss some possible new directions to be pursued in order to accomplish cutting-plane selection in a more principled manner. Finally, we review some lines of work that we undertook to provide a preliminary theoretical underpinning for some of the issues related to cut selection.     

Solving some optimal path planning problems using an approach based on measure theory

In this paper we solve a collection of optimal path planning problems using a method based on measure theory. First we consider the problem as an optimization problem and then we convert it to an optimal control problem by defining some artificial control functions. Then we perform a metamorphosis in the space of problem. In fact we define an injection between the set of admissible pairs, containing the control vector function and a collision-free path defined on free space and the space of positive Radon measures. By properties of this kind of measures we obtain a linear programming problem that its solution gives rise to constructing approximate optimal trajectory of the original problem. Some numerical examples are proposed.     

On mixed-integer sets with two integer variables

We show that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with two integer variables is a crooked cross cut (which we defined in 2010). We extend this result to show that crooked cross cuts give the convex hull of mixed-integer sets with more integer variables if the coefficients of the integer variables form a matrix of rank 2. We also present an alternative characterization of the crooked cross cut closure of mixed-integer sets similar to the one on the equivalence of different definitions of split cuts presented in Cook et al. (1990) [4]. This characterization implies that crooked cross cuts dominate the 2-branch split cuts defined by Li and Richard (2008) [8]. Finally, we extend our results to mixed-integer sets that are defined as the set of points (with some components being integral) inside a closed, bounded and convex set.     

Strong valid inequalities for orthogonal disjunctions and bilinear covering sets

In this paper, we derive a closed-form characterization of the convex hull of a generic nonlinear set, when this convex hull is completely determined by orthogonal restrictions of the original set. Although the tools used in this construction include disjunctive programming and convex extensions, our characterization does not introduce additional variables. We develop and apply a toolbox of results to check the technical assumptions under which this convexification tool can be employed. We demonstrate its applicability in integer programming by providing an alternate derivation of the split cut for mixed-integer polyhedral sets and finding the convex hull of certain mixed/pure-integer bilinear sets. We then extend the utility of the convexification tool to relaxing nonconvex inequalities, which are not naturally disjunctive, by providing sufficient conditions for establishing the convex extension property over the non-negative orthant. We illustrate the utility of this result by deriving the convex hull of a continuous bilinear covering set over the non-negative orthant. Although we illustrate our results primarily on bilinear covering sets, they also apply to more general polynomial covering sets for which they yield new tight relaxations.     

Direct methods with maximal lower bound for mixed-integer optimal control problems

Many practical optimal control problems include discrete decisions. These may be either time-independent parameters or time-dependent control functions as gears or valves that can only take discrete values at any given time. While great progress has been achieved in the solution of optimization problems involving integer variables, in particular mixed-integer linear programs, as well as in continuous optimal control problems, the combination of the two is yet an open field of research. We consider the question of lower bounds that can be obtained by a relaxation of the integer requirements. For general nonlinear mixed-integer programs such lower bounds typically suffer from a huge integer gap. We convexify (with respect to binary controls) and relax the original problem and prove that the optimal solution of this continuous control problem yields the best lower bound for the nonlinear integer problem. Building on this theoretical result we present a novel algorithm to solve mixed-integer optimal control problems, with a focus on discrete-valued control functions. Our algorithm is based on the direct multiple shooting method, an adaptive refinement of the underlying control discretization grid and tailored heuristic integer methods. Its applicability is shown by a challenging application, the energy optimal control of a subway train with discrete gears and velocity limits.      

Formulations and valid inequalities for the node capacitated graph partitioning problem

We investigate the problem of partitioning the nodes of a graph under capacity restriction on the sum of the node weights in each subset of the partition. The objective is to minimize the sum of the costs of the edges between the subsets of the partition. This problem has a variety of applications, for instance in the design of electronic circuits and devices. We present alternative integer programming formulations for this problem and discuss the links between these formulations. Having chosen to work in the space of edges of the multicut, we investigate the convex hull of incidence vectors of feasible multicuts. In particular, several classes of inequalities are introduced, and their strength and robustness are analyzed as various problem parameters change.