Polyhedra with the Integer Carathéodory Property

A polyhedron P has the Integer Carathéodory Property if the following holds. For any positive integer k and any integer vector w∈kP, there exist affinely independent integer vectors x₁,…,xt∈P and positive integers n₁,…,nt such that n₁+?+nt=k and w=n₁x₁+?+ntxt.In this paper we prove that if P is a (poly)matroid base polytope or if P is defined by a totally unimodular matrix, then P and projections of P have the Integer Carathéodory Property. For the matroid base polytope this answers a question by Cunningham from 1984.     

Computable Carathéodory Theory

The conformal Riemann mapping of the unit disk onto a simply-connected domain W is a central object of study in classical Complex Analysis. The first complete proof of the Riemann Mapping Theorem given by P. Koebe in 1912 is constructive, and theoretical aspects of computing the Riemann map have been extensively studied since. Carathéodory Theory describes the boundary extension of the Riemann map. In this paper we develop its constructive version with explicit complexity bounds.     

Carathéodory selections for multivalued mappings

We prove the existence of a Carathéodory selection for a set-valued mapping satisfying standard conditions. Also, an application to random fixed point for random operators is established.     

Controlled extensions of Carathéodory functions

In this paper we present two theorems on controlled extensions of Carathéodory functions. We obtain our results from corresponding ones for continuous functions by means of the Marczewski function.     

A new algorithmic method for finding the Carathéodory extremal maps

In this paper we construct a new algorithmic method for finding Carathéodory extremal maps for some balanced domains including complex ellipsoids.     

Carathéodory's method for a class of dynamic games

The method of equivalent variational methods, originally due to Carathéodory for free problems in the calculus of variations is extended to investigate feedback Nash equilibria for a class of n-person differential games. Both the finite-horizon and infinite-horizon cases are considered. Examples are given to illustrate the presented results.     

Invariant subspaces for operators whose spectra are Carathéodory regions

In this paper it is shown that if an operator T satisfies ‖p(T)‖?‖p_‖σ(T) for every polynomial p and the polynomially convex hull of σ(T) is a Carathéodory region whose accessible boundary points lie in rectifiable Jordan arcs on its boundary, then T has a nontrivial invariant subspace. As a corollary, it is also shown that if T is a hyponormal operator and the outer boundary of σ(T) has at most finitely many prime ends corresponding to singular points on ∂D and has a tangent at almost every point on each Jordan arc, then T has a nontrivial invariant subspace.     

A random Euler scheme for Carathéodory differential equations

We study a random Euler scheme for the approximation of Carathéodory differential equations and give a precise error analysis. In particular, we show that under weak assumptions, this approximation scheme obtains the same rate of convergence as the classical Monte–Carlo method for integration problems.     

Estimates of the Carathéodory metric on the symmetrized polydisc

Estimates for the Carathéodory metric on the symmetrized polydisc are obtained. It is also shown that the Carathéodory and Kobayashi distances of the symmetrized three-disc do not coincide.     

Carathéodory's method for a class of second order differential equations on the half-line

The method of equivalent variational methods, originally due to Carathéodory for free problems in the calculus of variations is extended to investigate boundary value problems for a class of second order differential equations on the half-line. Some applications are presented to illustrate the potential of this method.     

On the bin packing problem with a fixed number of object weights

We consider a bin packing problem where the number of different object weights is fixed to C. We analyze a simple approximate approach and show that it leads to an asymptotically exact polynomial algorithm with absolute error 0 if C = 2, at most 1 if 1 < C ? 6, and at most 1 + ⌊(C − 1)/3⌋ if C > 6. A consequence of our analysis is a new upper bound on the gap between the optimal value of the problem at hand and the round-up of the optimal value of the linear relaxation of its Gilmore–Gomory formulation.     

A higher order analogue of the Carathéodory-Julia theorem

A higher order analogue of the classical Carathéodory-Julia theorem on boundary derivatives is proved.     

On bounded solutions of nonlinear first- and second-order equations with a Carathéodory function

In the paper we study the existence and uniqueness of bounded solutions for differential equations of the form: x^′−Ax=f(t,x), x^″−Ax=f(t,x), where A∈L(Rm), is a Carathéodory function and the homogeneous equations x^′−Ax=0, x^″−Ax=0 have nontrivial solutions bounded on R. Using a perturbation of the equations, the Leray-Schauder Topological Degree and Fixed Point Theory, we overcome the difficulty that the linear problems are non-Fredholm in any reasonable Banach space.     

On existence of integrable solutions of a functional integral equation under Carathéodory conditions

We study the solvability of a functional integral equation in the space of Lebesgue integrable functions on an unbounded interval. Using the conjunction of the technique of measures of weak noncompactness with the classical Schauder fixed point principle we show that the equation in question is solvable in the mentioned function space. Our existence result is obtained under the assumption that functions involved in the investigated functional integral equation satisfy Carathéodory conditions. Moreover, that result generalizes several ones obtained earlier in many research papers and monographs.     

Sequential pairing of mixed integer inequalities

We investigate a scheme, called pairing, for generating new valid inequalities for mixed integer programs by taking pairwise combinations of existing valid inequalities. The pairing scheme essentially produces a split cut corresponding to a specific disjunction, and can also be derived through the mixed integer rounding procedure. The scheme is in general sequence-dependent and therefore leads to an exponential number of inequalities. For some important cases, we identify combination sequences that lead to a manageable set of non-dominated inequalities. We illustrate the framework for some deterministic and stochastic integer programs and we present computational results showing the efficiency of adding the new generated inequalities as cuts.     

A note on the approximability of cutting stock problems

Cutting stock problems and bin packing problems are basically the same problems. They differ essentially on the variability of the input items. In the first, we have a set of items, each item with a given multiplicity; in the second, we have simply a list of items (each of which we may assume to have multiplicity 1). Many approximation algorithms have been designed for packing problems; a natural question is whether some of these algorithms can be extended to cutting stock problems. We define the notion of “well-behaved” algorithms and show that well-behaved approximation algorithms for one, two and higher dimensional bin packing problems can be translated to approximation algorithms for cutting stock problems with the same approximation ratios.     

Sandwich-type theorem for Carathéodory multifunctions

In this paper we present a sandwich-type theorem for Carathéodory multifunctions. We obtain our result by means of the Marczewski function.     

An integer programming approach to b-coloring

In the b-coloring problem, we aim to assign colors from a set $C$ to the vertices of a graph $G$ in such a way that adjacent vertices do not receive the same color, and for every $c\in C$ we have a $c$-colored vertex $v$ in $G$ such that every color in $C\setminus \left\{c\right\}$ is assigned to at least one of $v$’s neighbors. It has been shown that b-coloring is NP-complete, so we propose in this article an approach for the problem under integer programming techniques. To this end, we give an integer programming formulation and study the associated polytope. We provide several families of valid inequalities, and analyze facetness conditions for them. Finally, we show computational evidence suggesting that the given inequalities may be useful in a branch-and-cut environment.     

Cutting planes for integer programs with general integer variables

We investigate the use of cutting planes for integer programs with general integer variables. We show how cutting planes arising from knapsack inequalities can be generated and lifted as in the case of 0–1 variables. We also explore the use of Gomory's mixed-integer cuts. We address both theoretical and computational issues and show how to embed these cutting planes in a branch-and-bound framework. We compare results obtained by using our cut generation routines in two existing systems with a commercially available branch-and-bound code on a range of test problems arising from practical applications. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.This research was partly performed when the author was affiliated with CORE, Université Catholique de Louvain.     

Alternative configurations for cutting machines in a tube cutting mill

In a steel tube mill where an endless stream of steel tube is supplied from a manufacturing facility, trim waste is never made regardless of cutting patterns used and the standard cutting stock problem seems meaningless. Therefore, the continuous stock cutting problem with setup is introduced to minimize the sum of cutting time and pattern changing time to meet the given demand. We propose a new configuration of cutting machines to achieve higher production efficiency, namely the open-ended configuration as opposed to the traditional closed-ended configuration, thereby two variants of the problem are defined. We propose linear formulations for both problems using binary expansion of the number of pieces of different types in a pattern. Furthermore, we define the time for pattern change as a linear function of the number of knives used in the pattern to be more realistic. Computational studies suggest that the open-ended cutting machine may improve the production time by up to 44% and that our linear formulations are more efficient than the existing ones.