Logical Constraints as Cardinality Rules: Tight Representation

We derive by means of disjunctive programming the convex hull representation of logical conditions called cardinality rules given by Hong and Hooker (1999), and specify an efficient separation algorithm for the family of inequalities defining the convex hull. We then extend both the convex hull characterization and the efficient separation procedure to more general logical conditions.     

The QAP-polytope and the graph isomorphism problem

In this paper we propose a geometric approach to solve the Graph Isomorphism (GI in short) problem. Given two graphs \(G_1, G_2\), the GI problem is to decide if the given graphs are isomorphic i.e., there exists an edge preserving bijection between the vertices of the two graphs. We propose an Integer Linear Program (ILP) that has a non-empty solution if and only if the given graphs are isomorphic. The convex hull of all possible solutions of the ILP has been studied in literature as the Quadratic Assignment Problem (QAP) polytope. We study the feasible region of the linear programming relaxation of the ILP and show that the given graphs are isomorphic if and only if this region intersects with the QAP-polytope. As a consequence, if the graphs are not isomorphic, the feasible region must lie entirely outside the QAP-polytope. We study the facial structure of the QAP-polytope with the intention of using the facet defining inequalities to eliminate the feasible region outside the polytope. We determine two new families of facet defining inequalities of the QAP-polytope and show that all the known facet defining inequalities are special instances of a general inequality. Further we define a partial ordering on each exponential sized family of facet defining inequalities and show that if there exists a common minimal violated inequality for all points in the feasible region outside the QAP-polytope, then we can solve the GI problem in polynomial time. We also study the general case when there are k such inequalities and give an algorithm for the GI problem that runs in time exponential in k.     

On the <Emphasis Type="Italic">m</Emphasis>-clique free interval subgraphs polytope: polyhedral analysis and applications

In this paper we study the m-clique free interval subgraphs. We investigate the facial structure of the polytope defined as the convex hull of the incidence vectors associated with these subgraphs. We also present some facet-defining inequalities to strengthen the associated linear relaxation. As an application, the generalized open-shop problem with disjunctive constraints (GOSDC) is considered. Indeed, by a projection on a set of variables, the m-clique free interval subgraphs represent the solution of an integer linear program solving the GOSDC presented in this paper. Moreover, we propose exact and heuristic separation algorithms, which are exploited into a Branch-and-cut algorithm for solving the GOSDC. Finally, we present and discuss some computational results.     

Implicit cover inequalities

In this paper we consider combinatorial optimization problems whose feasible sets are simultaneously restricted by a binary knapsack constraint and a cardinality constraint imposing the exact number of selected variables. In particular, such sets arise when the feasible set corresponds to the bases of a matroid with a side knapsack constraint, for instance the weighted spanning tree problem and the multiple choice knapsack problem. We introduce the family of implicit cover inequalities which generalize the well-known cover inequalities for such feasible sets and discuss the lifting of the implicit cover inequalities. A computational study for the weighted spanning tree problem is reported.     

The 2-Edge-Connected Subgraph Polyhedron

We study the polyhedron P(G) defined by the convex hull of 2-edge-connected subgraphs of G where multiple copies of edges may be chosen. We show that each vertex of P(G) is also a vertex of the LP relaxation. Given the close relationship with the Graphical Traveling Salesman problem (GTSP), we examine how polyhedral results for GTSP can be modified and applied to P(G). We characterize graphs for which P(G) is integral and study how this relates to a similar result for GTSP. In addition, we show how one can modify some classes of valid inequalities for GTSP and produce new valid inequalities and facets for P(G).     

On some geometric problems of color-spanning sets

In this paper we study several geometric problems of color-spanning sets: given n points with m colors in the plane, selecting m points with m distinct colors such that some geometric properties of the m selected points are minimized or maximized. The geometric properties studied in this paper are the maximum diameter, the largest closest pair, the planar smallest minimum spanning tree, the planar largest minimum spanning tree and the planar smallest perimeter convex hull. We propose an O(n ^1+ε ) time algorithm for the maximum diameter color-spanning set problem where ε could be an arbitrarily small positive constant. Then, we present hardness proofs for the other problems and propose two efficient constant factor approximation algorithms for the planar smallest perimeter color-spanning convex hull problem.     

Sum-of-squares rank upper bounds for matching problems

The matching problem is one of the most studied combinatorial optimization problems in the context of extended formulations and convex relaxations. In this paper we provide upper bounds for the rank of the sum-of-squares/Lasserre hierarchy for a family of matching problems. In particular, we show that when the problem formulation is strengthened by incorporating the objective function in the constraints, the hierarchy requires at most \(\left\lceil \frac{k}{2} \right\rceil \) levels to refute the existence of a perfect matching in an odd clique of size \(2k+1\).     

Repeated Games with Differential Time Preferences

When players have identical time preferences, the set of feasible repeated game payoffs coincides with the convex hull of the underlying stage- game payoffs. Moreover, all feasible and individually rational payoffs can be sustained by equilibria if the players are sufficiently patient. Neither of these facts generalizes to the case of different time preferences. First, players can mutually benefit from trading payoffs across time. Hence, the set of feasible repeated game payoffs is typically larger than the convex hull of the underlying stage-game payoffs. Second, it is not usually the case that every trade plan that guarantees individually rational payoffs can be sustained by an equilibrium, no matter how patient the players are. This paper provides a simple characterization of the sets of Nash and of subgame perfect equilibrium payoffs in two-player repeated games.     

Envelope Theorems for Arbitrary Choice Sets

The standard envelope theorems apply to choice sets with convex and topological structure, providing sufficient conditions for the value function to be differentiable in a parameter and characterizing its derivative. This paper studies optimization with arbitrary choice sets and shows that the traditional envelope formula holds at any differentiability point of the value function. We also provide conditions for the value function to be, variously, absolutely continuous, left‐ and right‐differentiable, or fully differentiable. These results are applied to mechanism design, convex programming, continuous optimization problems, saddle‐point problems, problems with parameterized constraints, and optimal stopping problems.     

Distributionally robust maximum probability shortest path problem

In this study, we discuss and develop a distributionally robust joint chance-constrained optimization model and apply it for the shortest path problem under resource uncertainty. In sch a case, robust chance constraints are approximated by constraints that can be reformulated using convex programming. Since the issue we are discussing here is of the multi-resource type, the resource related to cost is deterministic; however, we consider a robust set for other resources where covariance and mean are known. Thus, the chance-constrained problem can be expressed in terms of a cone constraint. In addition, since our problem is joint chance-constrained optimization, we can use Bonferroni approximation to divide the problem into L separate problems in order to build convex approximations of distributionally robust joint chance constraints. Finally, numerical results are presented to illustrate the rigidity of the bounds and the value of the distributionally robust approach.

     

Optimization and equilibrium problems with equilibrium constraints

This paper concerns optimization and equilibrium problems with the so-called equilibrium constraints mathematical programs with equilibrium constraint (MPEC) and equilibrium problems with equilibrium constraint (EPEC), which frequently appear in applications to operations research. These classes of problems can be naturally unified in the framework of multiobjective optimization with constraints governed by parametric variational systems (generalized equations, variational inequalities, complementarity problems, etc.). We focus on necessary conditions for optimal solutions to MPECs and EPECs under general assumptions in finite-dimensional spaces. Since such problems are intrinsically nonsmooth, we use advanced tools of generalized differentiation to study optimal solutions by methods of modern variational analysis. The general results obtained are concretized for special classes of MPECs and EPECs important in applications.     

Strong formulation for the spot 5 daily photograph scheduling problem

Earth observation satellites, such as the SPOT 5, take photographs of the earth according to consumers’ demands. Obtaining a good schedule for the photographs is a combinatorial optimization problem known in the literature as the daily photograph scheduling problem (DPSP). The DPSP consists of selecting a subset of photographs, from a set of candidates, to different cameras, maximizing a profit function and satisfying a large number of constraints. Commercial solvers, with standard integer programming formulations, are not able to solve some DPSP real instances available in the literature. In this paper we present a strengthened formulation for the DPSP, based on valid inequalities arising in node packing and 3-regular independence system polyhedra. This formulation was able, with a commercial solver, to solve to optimality all those instances in a short computation time.     

On Disjunctive Cuts for Combinatorial Optimization

In the successful branch-and-cut approach to combinatorial optimization, linear inequalities are used as cutting planes within a branch-and-bound framework. Although researchers often prefer to use facet-inducing inequalities as cutting planes, good computational results have recently been obtained using disjunctive cuts, which are not guaranteed to be facet-inducing in general.A partial explanation for the success of the disjunctive cuts is given in this paper. It is shown that, for six important combinatorial optimization problems (the clique partitioning, max-cut, acyclic subdigraph, linear ordering, asymmetric travelling salesman and set covering problems), certain facet-inducing inequalities can be obtained by simple disjunctive techniques. New polynomial-time separation algorithms are obtained for these inequalities as a by-product.The disjunctive approach is then compared and contrasted with some other general-purpose frameworks for generating cutting planes and some conclusions are made with respect to the potential and limitations of the disjunctive approach.     

When Restrictive Constraints Are Nonbinding: Illustrations and Implications

For convex and concave mathematical programs restrictive constraints (i.e., their deletion would change the optimum) will always be binding at the optimum, and vice versa. Less well-known is the fact that this property does not hold more generally, even for problems with convex feasible sets. This paper demonstrates the latter fact using numerical illustrations of common classes of problems. It then discusses the implications for public policy analysis, econometric estimation, and solution algorithms.     

Distribution with Quality of Service Considerations: The Capacitated Routing Problem with Profits and Service Level Requirements

Inspired by a problem arising in cash logistics, we propose the Capacitated Routing Problem with Profits and Service Level Requirements (CRPPSLR). The CRPPSLR extends the class of Routing Problems with Profits by considering customers requesting deliveries to their (possibly multiple) service points. Moreover, each customer imposes a service level requirement specifying a minimum-acceptable bound on the fraction of its service points being delivered. A customer-specific financial penalty is incurred by the logistics service provider when this requirement is not met. The CRPPSLR consists in finding vehicle routes maximizing the difference between the collected revenues and the incurred transportation and penalty costs in such a way that vehicle capacity and route duration constraints are met. A fleet of homogeneous vehicles is available for serving the customers. We design a branch-and-cut algorithm and evaluate the usefulness of valid inequalities that have been effectively used for the capacitated vehicle routing problem and, more recently, for other routing problems with profits. A real-life case study taken from the cash supply chain in the Netherlands highlights the relevance of the problem under consideration. Computational results illustrate the performance of the proposed solution approach under different input parameter settings for the synthetic instances. For instances of real-life problems, we distinguish between coin and banknote distribution, as vehicle capacities only matter when considering the former. Finally, we report on the effectiveness of the valid inequalities in closing the optimality gap at the root node for both the synthetic and the real-life instances and conclude with a sensitivity analysis on the most significant input parameters of our model.     

A Semidefinite Programming Approach to the Quadratic Knapsack Problem

In order to gain insight into the quality of semidefinite relaxations of constrained quadratic 0/1 programming problems we study the quadratic knapsack problem. We investigate several basic semidefinite relaxations of this problem and compare their strength in theory and in practice. Various possibilities to improve these basic relaxations by cutting planes are discussed. The cutting planes either arise from quadratic representations of linear inequalities or from linear inequalities in the quadratic model. In particular, a large family of combinatorial cuts is introduced for the linear formulation of the knapsack problem in quadratic space. Computational results on a small class of practical problems illustrate the quality of these relaxations and cutting planes.     

Linear time-dependent constraints programming with MSVL

This paper investigates specifying and solving linear time-dependent constraints with an interval temporal logic programming language MSVL. To this end, linear constraint statements involving linear equality and non-strict inequality are first defined. Further, the time-dependent relations in the constraints are specified by temporal operators, such as . Thus, linear time-dependent constraints can be smoothly incorporated into MSVL. Moreover, to solve the linear constraints within MSVL by means of reduction, the operational semantics for linear constraints is given. In particular, semantic equivalence rules and transition rules within a state are presented, which enable us to reduce linear equations, inequalities and optimization problems in a convenient way. Besides, the operational semantics is proved to be sound. Finally, a production scheduling application is provided to illustrate how our approach works in practice.     

Rationalizing Policy Functions by Dynamic Optimization

We derive necessary and sufficient conditions for a pair of functions to be the optimal policy function and the optimal value function of a dynamic maximization problem with convex constraints and concave objective functional. It is shown that every Lipschitz continuous function can be the solution of such a problem. If the maintained assumptions include free disposal and monotonicity, then we obtain a complete characterization of all optimal policy and optimal value functions. This is the case, e.g., in the standard aggregative optimal growth model.     

On the vertex characterization of single-shape partition polytopes

Given a partition of distinct d-dimensional vectors into p parts, the partition sum of the partition is the sum of vectors in each part. The shape of the partition is a p-tuple of the size of each part. A single-shape partition polytope is the convex hull of partition sums of all partitions that have a prescribed shape. A partition is separable if the convex hull of its parts are pairwise disjoint. The separability of a partition is a necessary condition for the associated partition sum to be a vertex of the single-shape partition polytope. It is also a sufficient condition for d=1 or p=2. However, the sufficiency fails to hold for d≥3 and p≥3. In this paper, we give some geometric sufficient conditions as well as some necessary conditions of vertices in general d and p. Thus, the open case for d=2 and p≥3 is resolved.     

Asymptotically Efficient Estimation of Models Defined by Convex Moment Inequalities

This paper examines the efficient estimation of partially identified models defined by moment inequalities that are convex in the parameter of interest. In such a setting, the identified set is itself convex and hence fully characterized by its support function. We provide conditions under which, despite being an infinite dimensional parameter, the support function admits √n‐consistent regular estimators. A semiparametric efficiency bound is then derived for its estimation, and it is shown that any regular estimator attaining it must also minimize a wide class of asymptotic loss functions. In addition, we show that the “plug‐in” estimator is efficient, and devise a consistent bootstrap procedure for estimating its limiting distribution. The setting we examine is related to an incomplete linear model studied in Beresteanu and Molinari (2008) and Bontemps, Magnac, and Maurin (2012), which further enables us to establish the semiparametric efficiency of their proposed estimators for that problem.