On some difficult linear programs coming from Set Partitioning

We deal with the linear programming relaxation of set partitioning problems arising in airline crew scheduling. Some of these linear programs have been extremely difficult to solve with the traditional algorithms. We have used an extension of the subgradient algorithm, the volume algorithm, to produce primal solutions that might violate the constraints by at most … Read more

A New and Efficient Large-Update Interior-Point Method for Linear Optimization

Recently, the authors presented a new large-update primal-dual method for Linear Optimization, whose $O(n^\frac23\,\log\frac{n}{\e})$ iteration bound substantially improved the classical bound for such methods, which is $O\br{n\log\frac{n}{\e}}$. In this paper we present an improved analysis of the new method. The analysis uses some new mathematical tools developed before when we considered a whole family of … Read more

Optimal location of intermodal freight hubs

Attempts at reducing the externalities of freight transport in Europe are generally focused on the incorporation of a more significant use of rail into freight itineraries. One new scenario for increasing the share of rail in intermodal transport involves the development of a dedicated subnetwork of freight rail lines. Within this European Union project, the … Read more

Convex optimization problems involving finite autocorrelation sequences

We discuss convex optimization problems where some of the variables are constrained to be finite autocorrelation sequences. Problems of this form arise in signal processing and communications, and we describe applications in filter design and system identification. Autocorrelation constraints in optimization problems are often approximated by sampling the corresponding power spectral density, which results in … Read more

Handling Nonnegative Constraints in Spectral Estimation

We consider convex optimization problems with the constraint that the variables form a finite autocorrelation sequence, or equivalently, that the corresponding power spectral density is nonnegative. This constraint is often approximated by sampling the power spectral density, which results in a set of linear inequalities. It can also be cast as a linear matrix inequality … Read more

An Interior-Point Approach to Sensitivity Analysis in Degenerate Linear Programs

We consider the interior-point approach to sensitivity analysis in linear programming (LP) developed by the authors. We investigate the quality of the interior-point bounds under degeneracy. In the case of a special degeneracy, we show that these bounds have the same nice relationship with the optimal partition bounds as in the nondegenerate case. We prove … Read more

Non Convergence Result for Conformal Approximation ofVariational Problems Subject to a Convexity Constraint

In this article, we are interested in the minimization of functionals in the set of convex functions. We investigate the discretization of the convexity through various numerical methods and find a geometrical obstruction confirmed by numerical simulations. We prove that there exist some convex functions that cannot be the limit of any conformal $P_1$ Finite … Read more

Optimal Control of Distributed Proceses using Reduced Order Models

The open loop optimal control (dynamic optimization) of distributed parameter systems is considered here. These problems are usually solved by the Control Vector Parameterization (CVP) approach, which transforms the original dynamic optimization method into an outer nonlinear programming problem, which requires the solution of an inner initial value problem (IVP). The solution of this IVP … Read more

Reducing the number of AD passes for computing a sparse Jacobian matrix

A reduction in the computational work is possible if we do not require that the nonzeros of a Jacobian matrix be determined directly. If a column or row partition is available, the proposed substitution technique can be used to reduce the number of groups in the partition further. In this chapter, we present a substitution … Read more

Newton Algorithms for Large-Scale Strictly Convex Separable Network Optimization

In this work we summarize the basic elements of primal and dual Newton algorithms for network optimization with continuously differentiable (strictly) convex arc cost functions. Both the basic mathematics and implementation are discussed, and hints to important tuning details are made. The exposition assumes that the reader posseses a significant level of prior knowledge in … Read more