Strip generation algorithms for constrained two-dimensional two-staged cutting problems

The constrained two-dimensional cutting (C_TDC) problem consists of determining a cutting pattern of a set of n small rectangular piece types on a rectangular stock plate of length L and width W, as to maximize the sum of the profits of the pieces to be cut. Each piece type i, i = 1, …, n, is characterized by a length l_i, a width w_i, a profit (or weight) c_i and an upper demand value b_i. The upper demand value is the maximum number of pieces of type i which can be cut on rectangle (L, W). In this paper, we study the two-staged fixed orientation C_TDC, noted FC_2TDC. It is a classical variant of the C_TDC where each piece is produced, in the final cutting pattern, by at most two guillotine cuts, and each piece has a fixed orientation. We solve the FC_2TDC problem using several approximate algorithms, that are mainly based upon a strip generation procedure. We evaluate the performance of these algorithms on instances extracted from the literature.     

Separation of the Monotone NC Hierarchy

, for the monotone depth of functions in monotone-P. As a result we achieve the separation of the following classes. 1. monotone-NC ≠ monotone-P. 2. For every i≥1, monotone-≠ monotone-. 3. More generally: For any integer function D(n), up to (for some ε>0), we give an explicit example of a monotone Boolean function, that can be computed by polynomial size monotone Boolean circuits of depth D(n), but that cannot be computed by any (fan-in 2) monotone Boolean circuits of depth less than Const·D(n) (for some constant Const). Only a separation of monotone- from monotone- was previously known. Our argument is more general: we define a new class of communication complexity search problems, referred to below as DART games, and we prove a tight lower bound for the communication complexity of every member of this class. As a result we get lower bounds for the monotone depth of many functions. In particular, we get the following bounds: 1.  For st-connectivity, we get a tight lower bound of . That is, we get a new proof for Karchmer–Wigderson's theorem, as an immediate corollary of our general result. 2.  For the k-clique function, with , we get a tight lower bound of Ω(k log n). This lower bound was previously known for k≤ log n [1]. For larger k, however, only a bound of Ω(k) was previously known. Received: December 19, 1997     

A Gentzen-style axiomatization for basic predicate calculus

 We introduce a Gentzen-style sequent calculus axiomatization for Basic Predicate Calculus. Our new axiomatization is an improvement of the previous axiomatizations, in the sense that it has the subformula property. In this system the cut rule is eliminated. Received: 18 April 2000 / Published online: 2 September 2002 Mathematics Subject Classification (2000): Primary 03F05; Secondary 03F99, 03B60 Key words or phrases: Basic predicate calculus – Cut elimination – Sequent     

Multiobjective optimization problem with variational inequality constraints

 We study a general multiobjective optimization problem with variational inequality, equality, inequality and abstract constraints. Fritz John type necessary optimality conditions involving Mordukhovich coderivatives are derived. They lead to Kuhn-Tucker type necessary optimality conditions under additional constraint qualifications including the calmness condition, the error bound constraint qualification, the no nonzero abnormal multiplier constraint qualification, the generalized Mangasarian-Fromovitz constraint qualification, the strong regularity constraint qualification and the linear constraint qualification. We then apply these results to the multiobjective optimization problem with complementarity constraints and the multiobjective bilevel programming problem. Received: November 2000 / Accepted: October 2001 Published online: December 19, 2002 Key Words. Multiobjective optimization – Variational inequality – Complementarity constraint – Constraint qualification – Bilevel programming problem – Preference – Utility function – Subdifferential calculus – Variational principle Research of this paper was supported by NSERC and a University of Victoria Internal Research Grant Research was supported by the National Science Foundation under grants DMS-9704203 and DMS-0102496 Mathematics Subject Classification (2000): Sub49K24, 90C29     

Degenerate stochastic differential equations and super-Markov chains

 We consider diffusions corresponding to the generator

A linear integer programming bound for maximum-entropy sampling

 We introduce a new upper bound for the maximum-entropy sampling problem. Our bound is described as the solution of a linear integer program. The bound depends on a partition of the underlying set of random variables. For the case in which each block of the partition has bounded cardinality, we describe an efficient dynamic-programming algorithm to calculate the bound. For the very special case in which the blocks have no more than two elements, we describe an efficient algorithm for calculating the bound based on maximum-weight matching. This latter formulation has particular value for local-search procedures that seek to find a good partition. We relate our bound to recent bounds of Hoffman, Lee and Williams. Finally, we report on the results of some computational experiments. Received: September 27, 2000 / Accepted: July 26, 2001 Published online: September 5, 2002 Key words. experimental design – design of experiments – entropy – maximum-entropy sampling – matching – integer program – spectral bound – Fischer's inequality – branch-and-bound – dynamic programming Mathematics Subject Classification (2000): 52B12, 90C10 Send offprint requests to: Jon Lee Correspondence to: Jon Lee     

On a Generalization of Martins’ Inequality

 Let be an increasing nonconstant sequence of positive real numbers. Under certain conditions on this sequence we prove the following inequality

A multi-item production planning model with setup times: algorithms, reformulations, and polyhedral characterizations for a special case

 We study a special case of a structured mixed integer programming model that arises in production planning. For the most general case of the model, called PI, we have earlier identified families of facet–defining valid inequalities: (l, S) inequalities (introduced for the uncapacitated lot–sizing problem by Barany, Van Roy, and Wolsey), cover inequalities, and reverse cover inequalities. PI is 𝒩𝒫–hard; in this paper we focus on a special case, called PIC. We describe a polynomial algorithm for PIC, and we use this algorithm to derive an extended formulation of polynomial size for PIC. Projecting from this extended formulation onto the original space of variables, we show that (l, S) inequalities, cover inequalities, and reverse cover inequalities suffice to solve the special case PIC by linear programming. We also describe fast combinatorial separation algorithms for cover and reverse cover inequalities for PIC. Finally, we discuss the relationship between our results for PIC and a model studied previously by Goemans. Received: December 13, 2000 / Accepted: December 13, 2001 Published online: October 9, 2002 RID="★" ID="★" Some of the results in this paper have appeared in condensed form in Miller et al. (2001). Key words. mixed integer programming – polyhedral combinatorics – production planning – capacitated lot–sizing – fixed charge network flow – setup times This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors. This research was also supported by NSF Grant No. DMI-9700285 and by Philips Electronics North America.     

Edge Colouring of K2n with Spanning Star-Forests Receiving Distinct Colours

 Let S _ni be a star of size n _i and let S=S _n1∪…∪S _nk≠S _2n−3∪S ₁ or S ₂∪S ₂ be a spanning star-forest of the complete graph K _2n. We prove that K _2n has a proper (2n−1)-edge-colouring such that all the edges of S receive distinct colours. This result is very useful in the study of total-colourings of graphs. Received: March 8, 1995 / Revised: May 16, 1997     

Refined common knowledge logics or logics of common information

 In terms of formal deductive systems and multi-dimensional Kripke frames we study logical operations know, informed, common knowledge and common information. Based on [6] we introduce formal axiomatic systems for common information logics and prove that these systems are sound and complete. Analyzing the common information operation we show that it can be understood as greatest open fixed points for knowledge formulas. Using obtained results we explore monotonicity, omniscience problem, and inward monotonocity, describe their connections and give dividing examples. Also we find algorithms recognizing these properties for some particular cases. Received: 21 October 2000 / Published online: 2 September 2002 Key words or phrases: Multi-agent systems – Non-standard logic – Knowledge representation – Common knowledge – Common information – Fixed points, Kripke models – Modal logic     

A Sharper Estimate on the Betti Numbers of Sets Defined by Quadratic Inequalities

In this paper we consider the problem of bounding the Betti numbers, b _i (S), of a semi-algebraic set S⊂ℝ ^k defined by polynomial inequalities P ₁≥0,…,P _s ≥0, where P _i ∈ℝ[X ₁,…,X _k ], s<k, and deg (P _i )≤2, for 1≤i≤s. We prove that for 0≤i≤k−1,

On the separation of split cuts and related inequalities

 The split cuts of Cook, Kannan and Schrijver are general-purpose valid inequalities for integer programming which include a variety of other well-known cuts as special cases. To detect violated split cuts, one has to solve the associated separation problem. The complexity of split cut separation was recently cited as an open problem by Cornuéjols & Li CL01. In this paper we settle this question by proving strong 𝒩𝒫-completeness of separation for split cuts. As a by-product we also show 𝒩𝒫-completeness of separation for several other classes of inequalities, including the MIR-inequalities of Nemhauser and Wolsey and some new inequalities which we call balanced split cuts and binary split cuts. We also strengthen 𝒩𝒫-completeness results of Caprara & Fischetti CF96 (for -cuts) and Eisenbrand E99 (for Chvátal-Gomory cuts). To compensate for this bleak picture, we also give a positive result for the Symmetric Travelling Salesman Problem. We show how to separate in polynomial time over a class of split cuts which includes all comb inequalities with a fixed handle. Received: October 23, 2000 / Accepted: October 03, 2001 Published online: September 5, 2002 Key words. cutting planes – separation – complexity – travelling salesman problem – comb inequalities     

Two measures for proving Gentzen's Hauptsatz without mix

 This paper presents a cut-elimination procedure for classical and intuitionistic logic, in which cut is eliminated directly, without introducing the mix rule. The well-known problem of cut eliminations, when in the derivation the contractions of the cut-formulae are above the premisses of the cut, will be solved by new transformations of the derivation. Received: 1 June 2001 / Published online: 5 November 2002 Mathematics Subject Classification (2000): 03F05 Key words or phrases: Systems of sequents – Cut-elimination theorem     

On some invariants in numerical semigroups and estimations of the order bound

Let S={s _i } _i∈??? be a numerical semigroup. For s _i ∈S, let ν(s _i ) denote the number of pairs (s _i ?s _j ,s _j )∈S ². When S is the Weierstrass semigroup of a family $\{\mathcal{C}_{i}\}_{i\in\mathbb{N}}Let S={s _i } _i∈ℕ⊆ℕ be a numerical semigroup. For s _i ∈S, let ν(s _i ) denote the number of pairs (s _i −s _j ,s _j )∈S ². When S is the Weierstrass semigroup of a family {C_i}_{i ? \mathbbN}\{\mathcal{C}_{i}\}_{i\in\mathbb{N}} of one-point algebraic-geometric codes, a good bound for the minimum distance of the code C_i\mathcal{C}_{i} is the Feng and Rao order bound d _ORD (C _i ). It is well-known that there exists an integer m such that d _ORD (C _i )=ν(s _i+1) for each i≥m. By way of some suitable parameters related to the semigroup S, we find upper bounds for m and we evaluate m exactly in many cases. Further we conjecture a lower bound for m and we prove it in several classes of semigroups.     

D.C. Versus Copositive Bounds for Standard QP

The standard quadratic program (QPS) is min_xεΔx^TQx, where is the simplex Δ = {x ⩽ 0 ∣ ∑_i=1ⁿ x_i = 1}. QPS can be used to formulate combinatorial problems such as the maximum stable set problem, and also arises in global optimization algorithms for general quadratic programming when the search space is partitioned using simplices. One class of ‘d.c.’ (for ‘difference between convex’) bounds for QPS is based on writing Q=S−T, where S and T are both positive semidefinite, and bounding x^T Sx (convex on Δ) and −x^Tx (concave on Δ) separately. We show that the maximum possible such bound can be obtained by solving a semidefinite programming (SDP) problem. The dual of this SDP problem corresponds to adding a simple constraint to the well-known Shor relaxation of QPS. We show that the max d.c. bound is dominated by another known bound based on a copositive relaxation of QPS, also obtainable via SDP at comparable computational expense. We also discuss extensions of the d.c. bound to more general quadratic programming problems. For the application of QPS to bounding the stability number of a graph, we use a novel formulation of the Lovasz ϑ number to compare ϑ, Schrijver’s ϑ′, and the max d.c. bound.     

A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization

 In this paper, we present a nonlinear programming algorithm for solving semidefinite programs (SDPs) in standard form. The algorithm's distinguishing feature is a change of variables that replaces the symmetric, positive semidefinite variable X of the SDP with a rectangular variable R according to the factorization X=RR ^T . The rank of the factorization, i.e., the number of columns of R, is chosen minimally so as to enhance computational speed while maintaining equivalence with the SDP. Fundamental results concerning the convergence of the algorithm are derived, and encouraging computational results on some large-scale test problems are also presented. Received: March 22, 2001 / Accepted: August 30, 2002 Published online: December 9, 2002 Key Words. semidefinite programming – low-rank factorization – nonlinear programming – augmented Lagrangian – limited memory BFGS This research was supported in part by the National Science Foundation under grants CCR-9902010, INT-9910084, CCR-0203426 and CCR-0203113     

Thek-partitioning problem

Thek-partitioning problem is defined as follows: Given a set of items {I ₁,I ₂,...,I _n} where itemIj is of weightwj 0, find a partitionS ₁,S ₂,...,S _m of this set with ¦S _i ¦ =k such that the maximum weight of all subsetsS _i is minimal,k-partitioning is strongly related to the classical multiprocessor scheduling problem of minimizing the makespan on identical machines. This paper provides suitable tools for the construction of algorithms which solve exactly the problem. Several approximation algorithms are presented for this NP-hard problem. The worst-case behavior of the algorithms is analyzed. The best of these algorithms achieves a performance bound of 4/3.     

Absolutely continuous invariant measures for piecewise expandingC 2 transformations inR N

LetS be a bounded region inR ^N and let ℊ={S _i} _i ^=1/m be a partition ofS into a finite number of subsets having piecewiseC ² boundaries. We assume that whereC ² segments of the boundaries meet, the angle subtended by tangents to these segments at the point of contact is bounded away from 0. Letτ:S →S be piecewiseC ² on ℊ and expanding in the sense that there exists 0<σ< 1 such that for anyi=1, 2, ...,m, ‖Dτ _i ⁻¹ ‖<σ, whereDτ _i ⁻¹ is the derivative matrix ofτ _i ⁻¹ and ‖ ‖ is the euclidean matrix norm. The main result provides an upper bound onσ which guarantees the existence of an absolutely continuous invariant measure forτ. The research of the second author was supported by NSERC and FCAR grants.     

Conditions of nontrivial solvability of the homogeneous Dirichlet problem for equations of any even order in the case of multiple characteristics without slope angles

We consider the homogeneous Dirichlet problem in the unit disk K ⊂ R ² for a general typeless differential equation of any even order 2m, m ≥ 2, with constant complex coefficients whose characteristic equation has multiple roots ± i. For each value of multiplicity of the roots i and – i, we either formulate criteria of the nontrivial solvability of the problem or prove that the analyzed problem possesses solely the trivial solution. A similar result generalizes the well-known Bitsadze examples to the case of typeless equations of any even order.     

A MIP-CP based approach for two- and three-dimensional cutting problems with staged guillotine cuts

This work presents guillotine constraints for two- and three-dimensional cutting problems. These problems look for a subset of rectangular items of maximum value that can be cut from a single rectangular container. Guillotine constraints seek to ensure that items are arranged in such a way that cuts from one edge of the container to the opposite edge completely separate them. In particular, we consider the possibility of 2, 3, and 4 cutting stages in a predefined sequence. These constraints are considered within a two-level iterative approach that combines the resolution of integer linear programming and constraint programming models. Experiments with instances of the literature are carried out, and the results show that the proposed approach can solve in less than 500 s approximately 60% and 50% of the instances for the two- and three-dimensional cases, respectively. For the two-dimensional case, in comparison with the recent literature, it was possible to improve the upper bound for 16% of the instances.