Convex separable optimization is not much harder than linear optimization
From MaRDI portal
linear constraintsnonlinear separable convex objective functionpolynomial algorithmpolynomial solvabilityproximity resultsscaling algorithms
Computational methods for problems pertaining to operations research and mathematical programming (90-08) Integer programming (90C10) Convex programming (90C25) Nonlinear programming (90C30) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)
Recommendations
- A unified approach to polynomially solvable cases of integer ``non-separable quadratic optimization
- Piecewise-Linear Approximation Methods for Nonseparable Convex Optimization
- A polynomial-time descent method for separable convex optimization problems with linear constraints
- Complexity and algorithms for nonlinear optimization problems
- Complexity and algorithms for convex network optimization and other nonlinear problems
Cited in
(89)- Convergent Lagrangian and domain cut method for nonlinear knapsack problems
- New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems
- Exact and approximate algorithms for high-multiplicity parallel machine scheduling
- Inverse optimization for linearly constrained convex separable programming problems
- A polynomial algorithm for an integer quadratic non-separable transportation problem
- Design of manufacturing systems using queueing models
- On polynomial solvability of the high multiplicity total weighted tardiness problem
- Optimizing flow rates in a queueing network with side constraints
- The empirical performance of a polynomial algorithm for constrained nonlinear optimization
- A capacity scaling algorithm for convex cost submodular flows
- Bounds for global optimization of capacity expansion and flow assignment problems
- Scheduling for electricity cost in a smart grid
- Quadratic M-convex and L-convex functions
- A unified approach to polynomially solvable cases of integer ``non-separable quadratic optimization
- Refined proximity and sensitivity results in linearly constrained convex separable integer programming
- A nonlinear knapsack problem
- A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables
- The symmetric quadratic knapsack problem: approximation and scheduling applications
- Analysis of a joint pricing and seat allocation model in a hub-to-hub airline network
- A unified approach for a 1D generalized total variation problem
- Proximity in concave integer quadratic programming
- The complexity of vector partition
- Improving the Cook et al. proximity bound given integral valued constraints
- Combinatorial \(n\)-fold integer programming and applications
- Computation and efficiency of potential function minimizers of combinatorial congestion games
- Graver basis and proximity techniques for block-structured separable convex integer minimization problems
- Distances between optimal solutions of mixed-integer programs
- Scheduling meets n-fold integer programming
- A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks
- Scaling, proximity, and optimization of integrally convex functions
- Balancing of agricultural census data by using discrete optimization
- Complexity and algorithms for nonlinear optimization problems
- Vector and matrix apportionment problems and separable convex integer optimization
- Maximum network flows with concave gains
- When is rounding allowed in integer nonlinear optimization?
- Optimal preemptive scheduling for general target functions
- Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
- Ameso optimization: a relaxation of discrete midpoint convexity
- Approximate separable multichoice optimization over monotone systems
- A polynomial-time descent method for separable convex optimization problems with linear constraints
- A decomposition algorithm for nested resource allocation problems
- A strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives
- Scheduling for electricity cost in smart grid
- Scheduling multiple products on parallel machines with setup costs
- Reduction of nonlinear integer separable programming problems∗
- Strongly polynomial algorithm for a production-transportation problem with concave production cost
- Using separation algorithms in fixed dimension
- A multi-stage stochastic programming approach in master production scheduling
- Polynomial Methods for Separable Convex Optimization in Unimodular Linear Spaces with Applications
- Efficient methods for selfish network design
- Tail mutual exclusivity and Tail-VaR lower bounds
- Sensitivity analysis for convex separable optimization over integral polymatroids
- A faster algorithm solving a generalization of isotonic median regression and a class of fused Lasso problems
- Improved randomized approximation algorithms for lot-sizing problems
- Selfish splittable flows and NP-completeness
- scientific article; zbMATH DE number 910862 (Why is no real title available?)
- A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
- Separable optimization. Theory and methods
- On a Reduction for a Class of Resource Allocation Problems
- Discrete midpoint convexity
- A polynomial time algorithm for solving the closest vector problem in zonotopal lattices
- scientific article; zbMATH DE number 4193457 (Why is no real title available?)
- Subdeterminants and concave integer quadratic programming
- On Proximity for k-Regular Mixed-Integer Linear Optimization
- Substitution with satiation: a new class of utility functions and a complementary pivot algorithm
- A Polyhedral Frobenius Theorem with Applications to Integer Optimization
- Integer Programming and Combinatorial Optimization
- The notion of a rational convex program, and an algorithm for the Arrow-Debreu Nash bargaining game
- Tensors in computations
- On the relationship between the integer and continuous solutions of convex programs
- Mathematical programming for network revenue management revisited
- Separable relaxation for nonconvex quadratic integer programming: Integer diagonalization approach
- High-multiplicity \(N\)-fold IP via configuration LP
- Minimizing a Low-Dimensional Convex Function Over a High-Dimensional Cube
- An approximation algorithm for indefinite mixed integer quadratic programming
- Slack allocation algorithm for parallel machines
- Using quadratic programming to solve high multiplicity scheduling problems on parallel machines
- (Near)-optimal algorithms for sparse separable convex integer programs
- A review of benchmark and test functions for global optimization algorithms and metaheuristics
- Scheduling kernels via configuration LP
- Separable convex mixed-integer optimization: improved algorithms and lower bounds
- Exact and approximate algorithms for high-multiplicity scheduling with rejection on parallel machines
- A brief history of parameterized algorithms for block-structured integer programs (invited talk)
- Mathematical programming approaches for social welfare maximization
- The nestedness property of the convex ordered median location problem on a tree
- Complexity and algorithms for convex network optimization and other nonlinear problems
- Tightness of sensitivity and proximity bounds for integer linear programs
- Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms
- Global optimization for first order Markov random fields with submodular priors
This page was built for publication: Convex separable optimization is not much harder than linear optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5753748)
