Linear Programming

An infeasible interior-point arc-search method with Nesterov’s restarting strategy for linear programming problems

  • Einosuke Iida
  • Makoto Yamashita
    • Categories Linear Programming Tags , , ,

    An arc-search interior-point method is a type of interior-point methods that approximate the central path by an ellipsoidal arc, and it can often reduce the number of iterations. In this work, to further reduce the number of iterations and computation time for solving linear programming problems, we propose two arc-search interior-point methods using Nesterov’s restarting … Read more

    An easily computable upper bound on the Hoffman constant for homogeneous inequality systems

  • Javier F. Peña
    • Categories Linear Programming, Polyhedra, Second-Order Cone Programming Tags , ,

    \(\)Let $A\in \mathbb{R}^{m\times n}\setminus \{0\}$ and $P:=\{x:Ax\le 0\}$. This paper provides a procedure to compute an upper bound on the following {\em homogeneous Hoffman constant} \[ H_0(A) := \sup_{u\in \mathbb{R}^n \setminus P} \frac{\text{dist}(u,P)}{\text{dist}(Au, \mathbb{R}^m_-)}. \] In sharp contrast to the intractability of computing more general Hoffman constants, the procedure described in this paper is entirely … Read more

    Orbital Crossover

  • Ethan Deakins
  • Bernard Knueven
  • James Ostrowski
    • Categories Convex Optimization, Linear Programming, Optimization Software Benchmark Tags , ,

    Symmetry in optimization has been known to wreak havoc in optimization algorithms. Often, some of the hardest instances are highly symmetric. This is not the case in linear programming, as symmetry allows one to reduce the size of the problem, possibly dramatically, while still maintaining the same optimal objective value. This is done by aggregating … Read more

    Regularized Nonsmooth Newton Algorithms for Best Approximation

  • Yair Censor
  • Walaa M. Moursi
  • Tyler Weames
  • Henry Wolkowicz
    • Categories Convex Optimization, Linear Programming, Nonsmooth Optimization Tags , , , , ,

    We consider the problem of finding the best approximation point from a polyhedral set, and its applications, in particular to solving large-scale linear programs. The classical projection problem has many various and many applications. We study a regularized nonsmooth Newton type solution method where the Jacobian is singular; and we compare the computational performance to … Read more

    A binary linear programming approach for supporting administrative territorial consolidation

  • Radu Buzatu
  • Igor Mandric
    • Categories 0-1 Programming, Combinatorial Optimization, Linear Programming Tags , , ,

    The objective of this paper is to develop a scalable binary linear programming model for finding the optimal aggregation of communes into spatially contiguous administrative territorial units (ATUs) constrained on certain balancing criteria. The requirement for the ATUs to be contiguous represents the main computational bottleneck and, therefore, it prevents one from using such models … Read more

    COIL: A Deep Architecture for Column Generation

  • Behrouz Babaki
  • Sanjay Dominik Jena
    • Categories Linear Programming Tags , , ,

    Column generation is a popular method to solve large-scale linear programs with an exponential number of variables. Several important applications, such as the vehicle routing problem, rely on this technique in order to be solved. However, in practice, column generation methods suffer from slow convergence (i.e. they require too many iterations). Stabilization techniques, which carefully … Read more

    Polynomial worst-case iteration complexity of quasi-Newton primal-dual interior point algorithms for linear programming

  • Francisco N. C. Sobral
  • Jacek Gondzio
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , ,

    Quasi-Newton methods are well known techniques for large-scale numerical optimization. They use an approximation of the Hessian in optimization problems or the Jacobian in system of nonlinear equations. In the Interior Point context, quasi-Newton algorithms compute low-rank updates of the matrix associated with the Newton systems, instead of computing it from scratch at every iteration. … Read more

    Production Theory for Constrained Linear Activity Models

  • Somdeb Lahiri
    • Categories Finance and Economics, Linear Programming, Production and Logistics Tags , ,

    The purpose of this paper is to generalize the framework of activity analysis discussed in Villar (2003) and obtain similar results concerning solvability. We generalize the model due to Villar (2003), without requiring any dimensional requirements on the activity matrices and by introducing a model of activity analysis in which each activity may (or may … Read more

    A primal-dual majorization-minimization method for large-scale linear programs

  • Xin-Wei Liu
  • Yu-Hong Dai
  • Yakui Huang
    • Categories Linear Programming Tags , , , ,

    We present a primal-dual majorization-minimization method for solving large-scale linear programs. A smooth barrier augmented Lagrangian (SBAL) function with strict convexity for the dual linear program is derived. The majorization-minimization approach is naturally introduced to develop the smoothness and convexity of the SBAL function. Our method only depends on a factorization of the constant matrix … Read more