Tightening the mixed integer linear formulation for the piecewise linear approximation in general dimensions

• URL: http://arxiv.org/abs/2508.09395v2
• Date: Thu, 14 Aug 2025 13:17:48 GMT
• Title: Tightening the mixed integer linear formulation for the piecewise linear approximation in general dimensions
• Authors: Quentin Ploussard, Xiang Li, Matija Pavičević,
• Abstract summary: This paper addresses the mixed-integer programming (MILP) formulation for continuous piecewise linear (CPWL) approximations of data sets in arbitrary dimensions.
• Score: 4.566850249315913
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper addresses the problem of tightening the mixed-integer linear programming (MILP) formulation for continuous piecewise linear (CPWL) approximations of data sets in arbitrary dimensions. The MILP formulation leverages the difference-of-convex (DC) representation of CPWL functions. We introduce the concept of well-behaved CPWL interpolations and demonstrate that any CPWL interpolation of a data set has a well-behaved version. This result is critical to tighten the MILP problem. We present six different strategies to tighten the problem, which include fixing the values of some variables, introducing additional constraints, identifying small big-M parameter values and applying tighter variable bounds. These methods leverage key aspects of the DC representation and the inherent structure of well-behaved CPWL interpolations. Experimental results demonstrate that specific combinations of these tightening strategies lead to significant improvement in solution times, especially for tightening strategies that consider well-behaved CPWL solutions.

Related papers

• Mixed-Integer Programming for Change-point Detection [8.644610122423993]
  We present a new mixed-integer programming (MIP) approach for offline multiple change-point detection.<n>We extend the framework to two settings of active research interest: (i) multidimensional PWL models with shared change-points, and (ii) sparse change-point detection.
  arXiv  Detail & Related papers  (2026-02-12T13:43:56Z)
• Integrating Reinforcement Learning and Model Predictive Control with Applications to Microgrids [14.389086937116582]
  This work proposes an approach that integrates reinforcement learning and model predictive control (MPC) to solve finite-horizon optimal control problems efficiently.<n>Our approach aims to mitigate this issue by decoupling the decision on the discrete variables from the decision on the continuous variables.<n>In the proposed approach, reinforcement learning determines the discrete decision variables and simplifies the online problem of the MPC controller from a mixed-integer linear program to a linear program.
  arXiv  Detail & Related papers  (2024-09-17T15:17:16Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
  We analyze smoothed (perturbed) policies, adding controlled random perturbations to the direction used by the linear oracle.<n>Our main contribution is a generalization bound that decomposes the excess risk into perturbation bias, statistical estimation error, and optimization error.<n>We illustrate the scope of the results on applications such as vehicle scheduling, highlighting how smoothing enables both tractable training and controlled generalization.
  arXiv  Detail & Related papers  (2024-07-24T12:00:30Z)
• A unified consensus-based parallel ADMM algorithm for high-dimensional regression with combined regularizations [3.280169909938912]
  parallel alternating multipliers (ADMM) is widely recognized for its effectiveness in handling large-scale distributed datasets. The proposed algorithms serve to demonstrate the reliability, stability, and scalability of a financial example.
  arXiv  Detail & Related papers  (2023-11-21T03:30:38Z)
• SIGMA: Scale-Invariant Global Sparse Shape Matching [50.385414715675076]
  We propose a novel mixed-integer programming (MIP) formulation for generating precise sparse correspondences for non-rigid shapes. We show state-of-the-art results for sparse non-rigid matching on several challenging 3D datasets.
  arXiv  Detail & Related papers  (2023-08-16T14:25:30Z)
• Regularized Multivariate Functional Principal Component Analysis [3.4238565157486187]
  This paper introduces a novel approach called regularized theCA (ReCA) to address the issue of controlling the roughness of Principal Components. The proposed method generates multivariate functional PCs, providing a concise and interpretable representation of the data.
  arXiv  Detail & Related papers  (2023-06-24T14:22:25Z)
• High-probability sample complexities for policy evaluation with linear function approximation [88.87036653258977]
  We investigate the sample complexities required to guarantee a predefined estimation error of the best linear coefficients for two widely-used policy evaluation algorithms. We establish the first sample complexity bound with high-probability convergence guarantee that attains the optimal dependence on the tolerance level.
  arXiv  Detail & Related papers  (2023-05-30T12:58:39Z)
• Tightening Discretization-based MILP Models for the Pooling Problem using Upper Bounds on Bilinear Terms [2.6253445491808307]
  Discretization-based methods have been proposed for solving non optimization problems with bi-linear terms. This paper shows that discretization-based MILP models can be used to solve the pooling problem.
  arXiv  Detail & Related papers  (2022-07-08T05:28:59Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  inductive biases are central in preventing overfitting empirically. This work considers this issue in arguably the most basic setting: constant-stepsize SGD for linear regression. We reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares.
  arXiv  Detail & Related papers  (2021-03-23T17:15:53Z)
• Square Root Bundle Adjustment for Large-Scale Reconstruction [56.44094187152862]
  We propose a new formulation for the bundle adjustment problem which relies on nullspace marginalization of landmark variables by QR decomposition. Our approach, which we call square root bundle adjustment, is algebraically equivalent to the commonly used Schur complement trick. We show in real-world experiments with the BAL datasets that even in single precision the proposed solver achieves on average equally accurate solutions.
  arXiv  Detail & Related papers  (2021-03-02T16:26:20Z)
• A Flexible Optimization Framework for Regularized Matrix-Tensor Factorizations with Linear Couplings [5.079136838868448]
  We propose a flexible algorithmic framework for coupled matrix and tensor factorizations. The framework facilitates the use of a variety of constraints, loss functions and couplings with linear transformations.
  arXiv  Detail & Related papers  (2020-07-19T06:49:59Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.