Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 2,509 papers for “Linear programming relaxation”

Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation

Manuel Bodirsky, Marcello Mamino, Caterina Viola · CINECA IRIS Institutial research information system (University of Pisa) · 2021

Valued constraint satisfaction problems (VCSPs) are a large class of combinatorial optimisation problems. The computational complexity of VCSPs depends on the set of allowed cost functions in the input. Recently, the computational complexity of all VCSPs for finite sets of cost functions over finite domains has been classified. Many natural optimisation problems, however, cannot be formulated as VCSPs over a finite domain. We initiate the systematic investigation of the complexity of infinite-domain VCSPs with piecewise linear homogeneous cost functions. Such VCSPs can be solved in polynomial time if the cost functions are improved by fully symmetric fractional operations of all arities. We show this by reducing the problem to a finite-domain VCSP which can be solved using the basic linear program relaxation. It follows that VCSPs for submodular PLH cost functions can be solved in polynomial time; in fact, we show that submodular PLH functions form a maximally tractable class of PLH cost functions.

Cited by 1

On Relaxation of Infeasibility of Linear Programming Constraints

ITAKURA, Hidekiyo, NISHIKAWA, Yoshikazu · Kyoto University Research Information Repository (Kyoto University) · 2023

In an optimization of a real system planning or design, when a prescribed set of constraints is found infeasible, it needs to be modified somehow. This paper presents a method for making an in feasible set of linear programming constraints feasible. Infeasibility is detected in phase I of the two-phase simplex procedure. Numerical data in the final simplex tableau of phase I are used for relaxing in feasibility. The relaxation is carried out by modifying some upper or lower bounds of the constraints. A sufficient condition for the relaxation is derived. The method allows a wide variety of modifications of the constraints. Thus, it could effectively be used in a practical linear programming design.

Cited by 0

Neural network design using linear programming and relaxation

Xiang Jiang, M.V. Hegde, Mort Naraghi‐Pour · 2002

Two new approaches to designing Hopfield neural networks using linear programming and relaxation are presented. These approaches are shown to be the natural ones given the form of the network dynamics. Computer simulations show that linear programming and relaxation are more effective than the sum of outer products rule in that they provide a larger capacity for the network. The new approaches are also shown to make the design process very flexible: they can guarantee that the given memories are all fixed points, they can incorporate a minimum radius of attraction, and they can accommodate restricted connectivities or regular network topologies. Statistical experiments are presented to illustrate these claims.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

Cited by 8

Integrality Gap of the Vertex Cover Linear Programming Relaxation

Mohit Singh · arXiv (Cornell University) · 2019

We give a characterization result for the integrality gap of the natural linear programming relaxation for the vertex cover problem. We show that integrality gap of the standard linear programming relaxation for any graph G equals $\left(2-\frac{2}{χ^f(G)}\right)$ where $χ^f(G)$ denotes the fractional chromatic number of G.

Cited by 0Open access

Lagrangian Relaxation Score-based Generation for Mixed Integer linear Programming

Ruobing Wang, Xin Li, Yujie Fang et al. · arXiv (Cornell University) · 2026

Predict-and-search (PaS) methods have shown promise for accelerating mixed-integer linear programming (MILP) solving. However, existing approaches typically assume variable independence and rely on deterministic single-point predictions, which limits solution diversityand often necessitates extensive downstream search for high-quality solutions. In this paper, we propose \textbf{SRG}, a generative framework based on Lagrangian relaxation-guided stochastic differential equations (SDEs), with theoretical guarantees on solution quality. SRG leverages convolutional kernels to capture inter-variable dependencies while integrating Lagrangian relaxation to guide the sampling process toward feasible and near-optimal regions. Rather than producing a single estimate, SRG generates diverse, high-quality solution candidates that collectively define compact and effective trust-region subproblems for standard MILP solvers. Across multiple public benchmarks, SRG consistently outperforms existing machine learning baselines in solution quality. Moreover, SRG demonstrates strong zero-shot transferability: on unseen cross-scale/problem instances, it achieves competitive optimality with state-of-the-art exact solvers while significantly reducing computational overhead through faster search and superior solution quality.

Cited by 0Open access

Surrogate “Level-Based” Lagrangian Relaxation for mixed-integer linear programming

Mikhail A. Bragin, Emily L. Tucker · Scientific Reports · 2022

Mixed-Integer Linear Programming (MILP) plays an important role across a range of scientific disciplines and within areas of strategic importance to society. The MILP problems, however, suffer from combinatorial complexity. Because of integer decision variables, as the problem size increases, the number of possible solutions increases super-linearly thereby leading to a drastic increase in the computational effort. To efficiently solve MILP problems, a "price-based" decomposition and coordination approach is developed to exploit 1. the super-linear reduction of complexity upon the decomposition and 2. the geometric convergence potential inherent to Polyak's stepsizing formula for the fastest coordination possible to obtain near-optimal solutions in a computationally efficient manner. Unlike all previous methods to set stepsizes heuristically by adjusting hyperparameters, the key novel way to obtain stepsizes is purely decision-based: a novel "auxiliary" constraint satisfaction problem is solved, from which the appropriate stepsizes are inferred. Testing results for large-scale Generalized Assignment Problems demonstrate that for the majority of instances, certifiably optimal solutions are obtained. For stochastic job-shop scheduling as well as for pharmaceutical scheduling, computational results demonstrate the two orders of magnitude speedup as compared to Branch-and-Cut. The new method has a major impact on the efficient resolution of complex Mixed-Integer Programming problems arising within a variety of scientific fields.

Cited by 11Open access