Local cuts revisited

We present a variant of the local cut generation procedure by Applegate, Bixby, Chvátal and Cook. Unlike the original procedure, our method immediately yields a facet of the projected polytope as the solution of a single LP, without the need for the time-consuming tilting step. Moreover, our facets have big volume in general.     

The symmetric quadratic traveling salesman problem

In the quadratic traveling salesman problem a cost is associated with any three nodes traversed in succession. This structure arises, e.g., if the succession of two edges represents energetic conformations, a change of direction or a possible change of transportation means. In the symmetric case, costs do not depend on the direction of traversal. We study the polyhedral structure of a linearized integer programming formulation of the symmetric quadratic traveling salesman problem. Our constructive approach for establishing the dimension of the underlying polyhedron is rather involved but offers a generic path towards proving facetness of several classes of valid inequalities. We establish relations to facets of the Boolean quadric polytope, exhibit new classes of polynomial time separable facet defining inequalities that exclude conflicting configurations of edges, and provide a generic strengthening approach for lifting valid inequalities of the usual traveling salesman problem to stronger valid inequalities for the symmetric quadratic traveling salesman problem. Applying this strengthening to subtour elimination constraints gives rise to facet defining inequalities, but finding a maximally violated inequality among these is NP-complete. For the simplest comb inequality with three teeth the strengthening is no longer sufficient to obtain a facet. Preliminary computational results indicate that the new cutting planes may help to considerably improve the quality of the root relaxation in some important applications.     

Facet inequalities from simple disjunctions in cutting plane theory

The duality between facets of the convex hull of disjunctive sets and the extreme points of reverse polars of these sets is utilized to establish simple rules for the derivation of all facet cuts for simple disjunctions, namely, elementary disjunctions in nonnegative variables. These rules generalize the cut generation procedure underlying polyhedral convexity cuts with negative edge extensions. The latter are also shown to possess some interesting properties with respect to a biextremal problem that maximizes the distance, from the origin, of the nearest point feasible to the cut. A computationally inexpensive procedure is given to generate facet cuts for simple disjunctions which are dominant with respect to any specified preemptive ordering of variables.     

The generalized assignment problem: Valid inequalities and facets

Three classes of valid inequalities based upon multiple knapsack constraints are derived for the generalized assignment problem. General properties of the facet defining inequalities are discussed and, for a special case, the convex hull is completely characterized. In addition, we prove that a basic fractional solution to the linear programming relaxation can be eliminated by a facet defining inequality associated with an individual knapsack constraint.Partial financial support under NSF grant #CCR-8812736.Partial financial support under NSF grant #DMS-8606188.     

Results for a turbulent system with unbounded viscosities: Weak formulations,existence of solutions,boundedness and smoothness

We consider a circulation system arising in turbulence modelling in fluid dynamics with unbounded eddy viscosities. Various notions of weak solution are considered and compared. We establish existence and regularity results. In particular we study the boundedness of weak solutions. We also establish an existence result for a classical solution.     

Quasi-concave minimization subject to linear constraints

A finite algorithm is presented for solving the quasi-concave minimization problem subject to linear constraints. The concept of an extreme point is generalized to that of an extreme facet of a polyhedron. Then a search routine is developed for the detection of an extreme facet of the feasible region relative to the polyhedron defined by the current set of cuts. After identifying an extreme facet we cut it off by a cut developed for this purpose. We call this cut the facet cut. The method is both compatible with other cutting procedures and is finite..     

Triangulation sous contraintes en dimension quelconque

It is not always possible to insert a facet of any dimension in a triangulation of a finite set of points in R^d for d > 2 without the adjunction of Steiner points. We propose here a simple method consisting in the inclusion of a triangulation of the constrained facet by adjunction of points upon it. These points are defined by using the intersections of the constrained facet with the simplices of the given triangulation.     

Time-constrained temporal logic control of multi-affine systems

In this paper, we consider the problem of controlling a dynamical system such that its trajectories satisfy a temporal logic property in a given amount of time. We focus on multi-affine systems and specifications given as syntactically co-safe linear temporal logic formulas over rectangular regions in the state space. The proposed algorithm is based on estimating the time bounds for facet reachability problems and solving a time optimal reachability problem on the product between a weighted transition system and an automaton that enforces the satisfaction of the specification. A random optimization algorithm is used to iteratively improve the solution.     

Generating facets for the cut polytope of a graph by triangular elimination

The cut polytope of a graph arises in many fields. Although much is known about facets of the cut polytope of the complete graph, very little is known for general graphs. The study of Bell inequalities in quantum information science requires knowledge of the facets of the cut polytope of the complete bipartite graph or, more generally, the complete k-partite graph. Lifting is a central tool to prove certain inequalities are facet inducing for the cut polytope. In this paper we introduce a lifting operation, named triangular elimination, applicable to the cut polytope of a wide range of graphs. Triangular elimination is a specific combination of zero-lifting and Fourier–Motzkin elimination using the triangle inequality. We prove sufficient conditions for the triangular elimination of facet inducing inequalities to be facet inducing. The proof is based on a variation of the lifting lemma adapted to general graphs. The result can be used to derive facet inducing inequalities of the cut polytope of various graphs from those of the complete graph. We also investigate the symmetry of facet inducing inequalities of the cut polytope of the complete bipartite graph derived by triangular elimination.      

Polyhedral analysis for the two-item uncapacitated lot-sizing problem with one-way substitution

We consider a production planning problem for two items where the high quality item can substitute the demand for the low quality item. Given the number of periods, the demands, the production, inventory holding, setup and substitution costs, the problem is to find a minimum cost production and substitution plan. This problem generalizes the well-known uncapacitated lot-sizing problem. We study the projection of the feasible set onto the space of production and setup variables and derive a family of facet defining inequalities for the associated convex hull. We prove that these inequalities together with the trivial facet defining inequalities describe the convex hull of the projection if the number of periods is two. We present the results of a computational study and discuss the quality of the bounds given by the linear programming relaxation of the model strengthened with these facet defining inequalities for larger number of periods.     

The Dirichlet problem for telegraph equation in a rectangular domain

We investigate the Dirichlet problem for the telegraph equation in a rectangular domain. We establish a criterion of uniqueness of solution to the problem. The solution is constructed as the sum of an orthogonal series. In substantiation of convergence of the series, the problem of small denominators occurs. In connection with this, we establish estimates ensuring separation from zero of denominators with the corresponding asymptotics which allow us to prove the existence of a regular solution and prove its stability under small perturbations of boundary functions.     

A problem with formal initial conditions for differential equations with constant pseudodifferential coefficients

We establish conditions for the unique existence of a solution of a problem with formal initial conditions. We investigate the problem of its solvability in the case where a solution is not unique.     

A polyhedral approach to single-machine scheduling problems

We report new results for a time-indexed formulation of nonpreemptive single-machine scheduling problems. We give complete characterizations of all facet inducing inequalities with integral coefficients and right-hand side 1 or 2 for the convex hull of the set of feasible partial schedules, i.e., schedules in which not all jobs have to be started. Furthermore, we identify conditions under which these facet inducing inequalities are also facet inducing for the original polytope, which is the convex hull of the set of feasible complete schedules, i.e., schedules in which all jobs have to be started. To obtain insight in the effectiveness of these classes of facet-inducing inequalities, we develop a branch-and-cut algorithm based on them. We evaluate its performance on the strongly NP-hard single machine scheduling problem of minimizing the weighted sum of the job completion times subject to release dates. Received March 24, 1994 / Revised version received February 13, 1997 Published online June 28, 1999     

The boundary-value problem for the Lavrent’ev-Bitsadze equation with unknown right-hand side

We study the inverse problem for the Lavrent’ev-Bitsadze equation in a rectangular domain. We construct its solution as a series of eigenfunctions for the corresponding problem on eigenvalues and establish a criterion for its uniqueness. We also prove the stability of the obtained solution.     

The precedence-constrained asymmetric traveling salesman polytope

Many applications of the traveling salesman problem require the introduction of additional constraints. One of the most frequently occurring classes of such constraints are those requiring that certain cities be visited before others (precedence constraints). In this paper we study the Precedence-Constrained Asymmetric Traveling Salesman (PCATS) polytope, i.e. the convex hull of incidence vectors of tours in a precedence-constrained directed graph. We derive several families of valid inequalities, and give polynomial time separation algorithms for important subfamilies. We then establish the dimension of the PCATS polytope and show that, under reasonable assumptions, the two main classes of inequalities derived are facet inducing.An early version of this paper was presented at the Oberwolfach Conference on Combinatorial Optimization in January 1991. This research was supported in part by the National Science Foundation, Grant #DDM-8901495 and the Office of Naval Research through Contract N00014-85-K-0198.Corresponding author.The work of this author was supported by MURST, Italy.     

Simplicial trees are sequentially Cohen–Macaulay

This paper uses dualities between facet ideal theory and Stanley–Reisner theory to show that the facet ideal of a simplicial tree is sequentially Cohen–Macaulay. The proof involves showing that the Alexander dual (or the cover dual, as we call it here) of a simplicial tree is a componentwise linear ideal. We conclude with additional combinatorial properties of simplicial trees.     

Asymptotic behavior for a cellular replication and maturation model

We consider a nonlocal first order partial differential equation with time delay that models simultaneous cell replication and maturation processes. We establish a comparison principle and construct monotone sequences to show the existence and uniqueness of the solution to the equation. We then analyze the asymptotic behavior of the solution via upper–lower solution technique.     

How to recycle your facets

We show how to transform any inequality defining a facet of some 0/1-polytope into an inequality defining a facet of the acyclic subgraph polytope. While this facet-recycling procedure can potentially be used to construct ‘nasty’ facets, it can also be used to better understand and extend the polyhedral theory of the acyclic subgraph and linear ordering problems.     

On the monotonization of polyhedra

In polyhedral combinatorics one often has to analyze the facial structure of less than full dimensional polyhedra. The presence of implicit or explicit equations in the linear system defining such a polyhedron leads to technical difficulties when analyzing its facial structure. It is therefore customary to approach the study of such a polytopeP through the study of one of its (full dimensional) relaxations (monotonizations) known as the submissive and the dominant ofP. Finding sufficient conditions for an inequality that induces a facet of the submissive or the dominant of a polyhedron to also induce a facet of the polyhedron itself has been posed in the literature as an important research problem. Our paper goes a long way towards solving this problem. We address the problem in the framework of a generalized monotonization of a polyhedronP, g-mon(P), that subsumes both the submissive and the dominant, and give a sufficient condition for an inequality that defines a facet of g-mon(P) to define a facet ofP. For the important cases of the traveling salesman (TS) polytope in both its symmetric and asymmetric variants, and of the linear ordering polytope, we give sufficient conditions trivially easy to verify, for a facet of the monotone completion to define a facet of the original polytope itself. Research supported by grant DMI-9201340 of the National Science Foundation and contract N00014-89-J-1063 of the Office of Naval Research. Research supported by MURST, Italy.     

Variational Inequalities for Leavable Bounded-Velocity Control

We study the variational inequality associated with a bounded-velocity control problem when discretionary stopping is allowed. We establish the existence of a strong solution by using the viscosity solution techniques. The optimal policy is shown to exist from the optimality conditions in the variational inequality.