Many real-world optimization problems—spanning image processing, machine learning, network design, and logistics—are naturally governed by non-linear relationships. These can manifest as products of decision variables, fractional objectives, or non-smooth curves. Attempting to solve these problems directly using general non-linear solvers often leads to severe computational bottlenecks, local minima, or outright intractability.
In contrast, Linear Programming (LP) and Mixed-Integer Linear Programming (MILP) solvers are highly mature, capable of handling millions of variables, and mathematically guaranteed to find global optima. The core insight of this research direction is that many complex, non-linear optimization problems can be systematically reformulated into equivalent or tightly approximated linear frameworks. By shifting the complexity out of the non-linear functional forms and into a structured linear space, researchers can leverage high-performance commercial solvers to find exact or near-optimal solutions efficiently.
Higher-Dimensional Lifting via Auxiliary Variables
The most common strategy for eliminating non-linearity is "lifting" the problem into a higher-dimensional space. When an objective function or constraint contains a non-linear combination of variables, that entire combination can be replaced by a single auxiliary variable. The relationship between the original variables and the new auxiliary variable is then enforced using a set of linear inequalities.
This technique is highly effective for managing non-smooth penalties or complex interactions:
- Quadratic and Non-Submodular Terms: In computer vision, Lopamudra Mukherjee et al. demonstrate this in image cosegmentation. By lifting quadratic objective terms into a linear space using auxiliary variables, the authors transform non-submodular energy functions into a linear programming format, making a notoriously difficult image-matching problem solvable via standard LP methods.
- Non-Smooth Component Functions: For sparse machine learning models, Sally Dong et al. introduce auxiliary variables to represent the outputs of individual non-smooth convex functions. This maps the problem into a higher-dimensional space where each constraint depends on only a limited subset of variables, allowing the algorithm to exploit the underlying sparsity of the system.
- Logical and Conditional Penalties: In scheduling and routing, non-linearities often arise from conditional logic. Francesco Leofante et al. convert non-linear robot routing objectives into linear constraints by combining auxiliary variables with ordering constraints. Similarly, Anne-Elisabeth Falq et al. address single-machine scheduling by linearizing non-linear earliness and tardiness penalties. The authors use auxiliary variables alongside boolean logic to distinguish between early and tardy tasks, embedding the conditional penalties directly into a standard MILP framework.
Transforming Fractional and Ratio Objectives
Fractional programming deals with optimizing ratios, such as maximizing efficiency (output divided by input) or balancing metrics. Ratios are inherently non-linear because the decision variables appear in the denominator, which warps the optimization landscape. Linearization typically works by clearing the denominator through coordinate transformations or solving a sequence of linear subproblems.
- Sequence of Linear Subproblems: In community detection, Atsushi Miyauchi et al. accelerate the maximization of modularity density by reformulating the fractional objective function into a sequence of 0-1 linear programming problems. This allows highly optimized linear solvers to handle exact optimization without facing quadratic or non-linear overhead.
- Exact Linear Inequalities: For causal inference in political and social sciences, Cynthia Rudin et al. convert fractional objectives representing balance metrics into linear forms using specialized transformations, drastically improving the speed of match assignments. In graph theory, Tomomi Matsui et al. tackle the vertex coloring problem by converting a fractional objective function (representing partition counts) into a piece-wise linear convex form. This exact representation via linear inequalities allows commercial solvers to bypass the symmetry problems that typically plague traditional non-linear formulations.
Piecewise Approximations and Algebraic Transformations
When dealing with continuous non-linear curves—such as logarithms, exponents, or physical curves like velocity—exact algebraic elimination may be impossible. Instead, researchers employ algebraic tricks to change the operations or use piecewise linear segments to approximate the curve.
The Logarithmic Trick
When an objective function involves maximizing the product of several terms, it creates a highly non-linear landscape. However, because the logarithm is a monotonically increasing function, maximizing a product is mathematically equivalent to maximizing the sum of the logarithms of those terms ($\log(A \cdot B) = \log A + \log B$).
Ewa Andrejczuk et al. leverage this transformation to solve the Synergistic Team Composition Problem. By maximizing the sum of the logarithms of the terms rather than their raw product, the authors linearize the social objectives, allowing standard integer linear programming tools to handle complex team-balancing requirements.
Piecewise Linearization
For more complex curves, the continuous function can be discretized into a series of connected linear segments.
Continuous Curve Piecewise Linear Approximation
^ ^
| /---\ | /---\
| / \ | /_ _ _\
|/ \ |/ \
+---------> +--------->
- Outer Approximations: In community detection within stochastic block models, Breno Serrano et al. handle the logarithmic terms of a maximum likelihood estimation objective by applying a piecewise outer approximation. This transforms the intractable non-linear formulation into a solvable mixed-integer linear program.
- Discretizing Physical Curves: In logistics, Sergey Polyakovskiy et al. study a non-linear knapsack variant where vehicle speed decreases as weight increases. To handle large-scale instances, the authors apply a piecewise linear approximation to the reciprocal velocity curve, discretizing the continuous speed-weight relationship into linear segments that standard MILP solvers can process efficiently.
Linearizing the Feasible Space
Sometimes the objective function itself is linear, but the problem is rendered non-linear by its constraints or by probabilistic uncertainty. Linearizing these boundaries simplifies the feasible region, ensuring that the optimization path remains clear.
- Constraint Simplification: In wireless communications, Wei Xu 0001 simplifies power allocation and user clustering in downlink NOMA systems by transforming non-linear rate constraints into an equivalent set of linear rate constraints. Similarly, Jian Zhou et al. isolate the non-linearity of fuzzy optimization problems by linearizing underlying bipolar fuzzy relational equations, reducing the complex feasible region into a standard 0-1 mixed-integer space.
- Bounding Expectations: In mobile device-to-device caching networks, Lei You et al. address the non-linearities introduced by expected network loads under user mobility. The authors replace the expectation of a maximum value with the maximum of an expectation, creating a linear lower bound that makes the delay minimization problem computationally tractable.
- Discrete Selection and Topology: This strategy of simplifying the underlying space also enables efficient discrete selection under max-min fairness constraints, as shown by Songyuan Li et al., and allows for robust network design under localized failure constraints, as demonstrated by Peng Jiao et al..
Key Foundational Work
Recourse problem of the 2-stage robust location transportation problem (2010) — contributed 1 concept elements to this direction.
Half-integrality based algorithms for cosegmentation of images (2009) — contributed 1 concept elements to this direction.