A constraint-reduced variant of Mehrotra’s predictor-corrector algorithm

Consider linear programs in dual standard form with n constraints and m variables. When typical interior-point algorithms are used for the solution of such problems, updating the iterates, using direct methods for solving the linear systems and assuming a dense constraint matrix A, requires O(nm²)\mathcal{O}(nm^{2}) operations per iteration. When n≫m it is often the case that at each iteration most of the constraints are not very relevant for the construction of a good update and could be ignored to achieve computational savings. This idea was considered in the 1990s by Dantzig and Ye, Tone, Kaliski and Ye, den Hertog et al. and others. More recently, Tits et al. proposed a simple “constraint-reduction” scheme and proved global and local quadratic convergence for a dual-feasible primal-dual affine-scaling method modified according to that scheme. In the present work, similar convergence results are proved for a dual-feasible constraint-reduced variant of Mehrotra’s predictor-corrector algorithm, under less restrictive nondegeneracy assumptions. These stronger results extend to primal-dual affine scaling as a limiting case. Promising numerical results are reported.     

On the power and limitations of affine policies in two-stage adaptive optimization

We consider a two-stage adaptive linear optimization problem under right hand side uncertainty with a min–max objective and give a sharp characterization of the power and limitations of affine policies (where the second stage solution is an affine function of the right hand side uncertainty). In particular, we show that the worst-case cost of an optimal affine policy can be times the worst-case cost of an optimal fully-adaptable solution for any δ > 0, where m is the number of linear constraints. We also show that the worst-case cost of the best affine policy is times the optimal cost when the first-stage constraint matrix has non-negative coefficients. Moreover, if there are only k ≤ m uncertain parameters, we generalize the performance bound for affine policies to , which is particularly useful if only a few parameters are uncertain. We also provide an -approximation algorithm for the general case without any restriction on the constraint matrix but the solution is not an affine function of the uncertain parameters. We also give a tight characterization of the conditions under which an affine policy is optimal for the above model. In particular, we show that if the uncertainty set, is a simplex, then an affine policy is optimal. However, an affine policy is suboptimal even if is a convex combination of only (m + 3) extreme points (only two more extreme points than a simplex) and the worst-case cost of an optimal affine policy can be a factor (2 − δ) worse than the worst-case cost of an optimal fully-adaptable solution for any δ > 0.     

A strongly polynomial algorithm for solving two-sided linear systems in max-algebra

An algorithm for solving m×n systems of (max,+)-linear equations is presented. The systems have variables on both sides of the equations. After O(m⁴n⁴) iterations the algorithm either finds a solution of the system or finds out that no solution exists. Each iteration needs O(mn) operations so that the complexity of the presented algorithm is O(m⁵n⁵).     

Piecewise affine approximations for the control of a one-reservoir hydroelectric system

We analyze the computation of optimal and approximately optimal policies for a discrete-time model of a single reservoir whose discharges generate hydroelectric power. Inflows in successive periods are random variables. Revenue from hydroelectric production is represented by a piecewise linear function. We use the special structure of optimal policies, together with piecewise affine approximations of the optimal return functions at each stage of dynamic programming, to decrease the computational effort by an order of magnitude compared with ordinary value iteration. The method is then used to obtain easily computable lower and upper bounds on the value function of an optimal policy, and a policy whose value function is between the bounds.     

The correct proofs for the optimal ordering policy with?trade credit under two different payment methods in?a?supply chain system

Cheng et al. (Top, 2010. doi:10.1007/s11750-08-0062-3) consider the optimal ordering policy with trade credit under two different payment methods. Under Assumption (5) by Cheng et al., the annual total relevant cost TRC(T) is only defined on a finite interval. However, Cheng et al. treat the domain of TRC(T) to be the set of all positive numbers such that the formulation and optimal solution of TRC(T) cause some errors. So, the main purpose of this paper not only removes those shortcomings by Cheng et al. but also presents the correct proofs for Theorems?1 and?2 of Cheng et?al.     

Waiting time distribution of the MAP/D/k system in discrete time—a more efficient algorithm

We show that the discrete time MAP/D/k presented by Chaudhry et al. (Oper. Res. Lett. 30(3) (2002) 174) has a special structure which results in a simple and more efficient computational scheme than they have presented. Specifically, we show that the computational efforts for the matrix G at each iteration can be reduced from O(d³k³m³) to O(dk³m³) by rearranging the state space and then capitalizing on the resulting structure. This saving in computational effort is significant, especially when d is very large.     

Spectral analysis of the affine graph over the finite ring

We apply two methods to the block diagonalization of the adjacency matrix of the Cayley graph defined on the affine group. The affine group will be defined over the finite ring Z/pⁿZ. The method of irreducible representations will allow us to find nontrivial eigenvalue bounds for two different graphs. One of these bounds will result in a family of Ramanujan graphs. The method of covering graphs will be used to block diagonalize the affine graphs using a Galois group of graph automorphisms. In addition, we will demonstrate the method of covering graphs on a generalized version of the graphs of Lubotzky et al. [A. Lubotzky, R. Phillips, P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988) 261-277].     

The Euclidean Distortion of the Lamplighter Group

We show that the cyclic lamplighter group C ₂ ? C _n embeds into Hilbert space with distortion $\mathrm{O}(\sqrt{\log n})We show that the cyclic lamplighter group C ₂ ≀ C _n embeds into Hilbert space with distortion O(?{logn})\mathrm{O}(\sqrt{\log n}) . This matches the lower bound proved by Lee et al. (Geom. Funct. Anal., 2009), answering a question posed in that paper. Thus, the Euclidean distortion of C ₂ ≀ C _n is \varTheta(?{logn})\varTheta(\sqrt{\log n}) . Our embedding is constructed explicitly in terms of the irreducible representations of the group. Since the optimal Euclidean embedding of a finite group can always be chosen to be equivariant, as shown by Aharoni et al. (Isr. J. Math. 52(3):251–265, 1985) and by Gromov (see de Cornulier et. al. in Geom. Funct. Anal., 2009), such representation-theoretic considerations suggest a general tool for obtaining upper and lower bounds on Euclidean embeddings of finite groups.     

On finding most uniform spanning trees

We consider the following problem. Given a graph G and a real valued weight for each edge in G, find a spanning tree T of G such that the difference in weight between the most and least weighted edge in T is minimized. We show an O(m log n) algorithm for this problem, where m is the number of edges and n is the number of vertices in G. This algorithm improves the algorithm given by Camerini et al. [1] for the same problem.     

Domain decomposition for a finite volume method on non-matching grids

We are interested in a robust and accurate domain decomposition method with Robin interface conditions on non-matching grids using a finite volume discretization. We introduce transmission operators on the non-matching grids and define new interface conditions of Robin type. Under a compatibility assumption, we show the equivalence between Robin interface conditions and Dirichlet–Neumann interface conditions and the well-posedness of the global and local problems. Two error estimates are given in terms of the discrete H¹-norm: one in O(h^1/2) with operators based on piecewise constant functions and the other in O(h) (as in the conforming case) with operators using a linear rebuilding. Numerical results are given. To cite this article: L. Saas et al., C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

Unboundedness properties of smoothness Morrey spaces of regular distributions on domains

We study unboundedness of smoothness Morrey spaces on bounded domains ? ? R~n in terms of growth envelopes. It turns out that in this situation the growth envelope function is finite—in contrast to the results obtained by Haroske et al.(2016) for corresponding spaces defined on R~n. A similar effect was already observed by Haroske et al.(2017), where classical Morrey spaces M_(u,p)(?) were investigated. We deal with all cases where the concept is reasonable and also include the tricky limiting cases. Our results can be reformulated in terms of optimal embeddings into the scale of Lorentz spaces L_(p,q)(?).     

Pruning method for optimal solutions of int–int decision making scheme

This paper aims to find a faster method for optimal solutions of Feng et al.’s int^m–intⁿ decision making scheme. We first give theoretical characterizations of optimal decision sets. Then we develop a pruning method which filters out those objects that cannot be elements of any optimal decision sets in the beginning. Experimental results have shown that our method has higher efficiency in computing the optimal solutions of this scheme, particularly when we are processing soft sets with a great quantity of data.     

A note on optimal ordering policies when the supplier provides a progressive interest scheme

Goyal et al. [Goyal, S.K., Teng, J.T., Chang, C.T., 2007. Optimal ordering policies when the supplier provides a progressive interest scheme. European Journal of Operational Research 179, 404–413] explore optimal ordering policies when the supplier provides a progressive interest scheme. The main purpose of this paper is fourfold:

(1)

This paper simplifies the total relevant cost per year Z(T) of Goyal et al. (2007) such that we can locate the optimal solutions of Z(T) by an easier way.     

Minmax regret location–allocation problem on a network under uncertainty

We consider a robust location–allocation problem with uncertainty in demand coefficients. Specifically, for each demand point, only an interval estimate of its demand is known and we consider the problem of determining where to locate a new service when a given fraction of these demand points must be served by the utility. The optimal solution of this problem is determined by the “minimax regret” location, i.e., the point that minimizes the worst-case loss in the objective function that may occur because a decision is made without knowing which state of nature will take place. For the case where the demand points are vertices of a network we show that the robust location–allocation problem can be solved in O(min{p, n − p}n³m) time, where n is the number of demand points, p (p < n) is the fixed number of demand points that must be served by the new service and m is the number of edges of the network.     

The Hamiltonian problem on distance-hereditary graphs

In this paper, we first present an O(n+m)-time sequential algorithm to solve the Hamiltonian problem on a distance-hereditary graph G, where n and m are the number of vertices and edges of G, respectively. This algorithm is faster than the previous best known algorithm for the problem which takes O(n²) time. We also give an efficient parallel implementation of our sequential algorithm. Moreover, if G is represented by its decomposition tree form, the problem can be solved optimally in O(logn) time using O((n+m)/logn) processors on an EREW PRAM.     

Problem F2∥Cmax with forbidden jobs in the first or last position is easy

Saadani et al. [N.E.H. Saadani, P. Baptiste, M. Moalla, The simple F2∥C_max with forbidden tasks in first or last position: A problem more complex that it seems, European Journal of Operational Research 161 (2005) 21–31] studied the classical n-job flow shop scheduling problem F2∥C_max with an additional constraint that some jobs cannot be placed in the first or last position. There exists an optimal job sequence for this problem, in which at most one job in the first or last position is deferred from its position in Johnson’s [S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly 1 (1954) 61–68] permutation. The problem was solved in O(n²) time by enumerating all candidate job sequences. We suggest a simple O(n) algorithm for this problem provided that Johnson’s permutation is given. Since Johnson’s permutation can be obtained in O(n log n) time, the problem in Saadani et al. (2005) can be solved in O(n log n) time as well.     

On representations by determinants of P(n) and Pm(n)

P(n) and P_m(n) denote the number of (unordered) partitions of n and the number of partitions of n into m parts, respectively. For P(n), there exists a recursion formula which is shown in Eq. (3) and a complicated formula indicated in J. L. Doob et al. (“Hans Rademacher: Topic Analytic Number Theory,” Springer-Verlag, Berlin/New York, 1973, p. 275, which is accompanied with the error term. For P_m(n), there is no general rule known covering all m (Doob et al., p. 222). In this article, P(n) and P_m(n) are represented by determinants. Note that the determinant of the former agrees with the above recursion formula and the finite product of binomials analogous to Euler identity, which is indicated in (5), leads to the representation of the latter. The computation of determinant is a little troublesome, but it is very important that the representations themselves of the number of partitions are simple, if we make use of the determinant.     

A fourth‐order H1‐Galerkin mixed finite element method for Kuramoto–Sivashinsky equation

A H¹‐Galerkin mixed finite element method is applied to the Kuramoto–Sivashinsky equation by using a splitting technique, which results in a coupled system. The method described in this article may also be considered as a Petrov–Galerkin method with cubic spline space as trial space and piecewise linear space as test space, since the second derivative of a cubic spline is a linear spline. Optimal‐order error estimates are obtained without any restriction on the mesh for both semi‐discrete and fully discrete schemes. The advantage of this method over that presented in Manickam et al., Comput. Math. Appl. vol. 35(6) (1998) pp. 5–25; for the same problem is that the size (i.e., (n + 1) × (n + 1)) of each resulting linear system is less than half of the size of the linear system of the earlier method, where n is the number of subintervals in the partition. Further, there is a requirement of less regularity on exact solution in this method. The results are validated with numerical examples. Finally, instability behavior of the solution is numerically captured with this method.     

A projected Weiszfeld algorithm for the box-constrained Weber location problem

The Weber problem consists of finding a point in Rⁿ that minimizes the weighted sum of distances from m points in Rⁿ that are not collinear. An application that motivated this problem is the optimal location of facilities in the 2-dimensional case. A classical method to solve the Weber problem, proposed by Weiszfeld in 1937, is based on a fixed-point iteration.In this work we generalize the Weber location problem considering box constraints. We propose a fixed-point iteration with projections on the constraints and demonstrate descending properties. It is also proved that the limit of the sequence generated by the method is a feasible point and satisfies the KKT optimality conditions. Numerical experiments are presented to validate the theoretical results.     

Computing homotopic shortest paths in the plane

We address the problem of computing homotopic shortest paths in the presence of obstacles in the plane. Problems on homotopy of paths received attention very recently [Cabello et al., in: Proc. 18th Annu. ACM Sympos. Comput. Geom., 2002, pp. 160–169; Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411–423]. We present two output-sensitive algorithms, for simple paths and non-simple paths. The algorithm for simple paths improves the previous algorithm [Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411–423]. The algorithm for non-simple paths achieves O(log²n) time per output vertex which is an improvement by a factor of O(n/log²n) of the previous algorithm [Hershberger, Snoeyink, Comput. Geom. Theory Appl. 4 (1994) 63–98], where n is the number of obstacles. The running time has an overhead O(n²⁺) for any positive constant . In the case k<n²⁺, where k is the total size of the input and output, we improve the running to O((n+k+(nk)^2/3)log^O(1)n).