We’re rewarding the question askers & reputations are being recalculated! Read more.

# Questions tagged [linear-programming]

Optimization with a linear objective function, subject to linear equality and linear inequality constraints.

86 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
155 views

### Formulating shortest path as submodular minimization

I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function. The answer ...
250 views

30 views

### Goemans' Extended Formulation of the Permutahedron And Comparator Networks that are not Sorting Networks

I am interested in using Michel Goemans' extended formulation first developed for the permutahedron to study comparator networks that are not sorting networks. In his paper "Smallest Compact ...
36 views

I came across an LP with two covering problems, and I wonder how to find a good approximation. For the relevant part of the LP: We have a set $E$ , for each $e\in E$ we have a corresponding set $Y_{e}\... 0answers 29 views ### Time complexity: Using linear programming to solve a system of linear equations As far as I know, most direct methods for solving linear systems of equations have time copmlexity$O(n^3)$(where$n$is the number of variables), with the few methods being faster having huge ... 0answers 85 views ### Confusion about the geometric interpretation of the simplex method for linear programming In Section 7.6.2 of the textbook "Algorithms" by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani, the authors provide a geometric interpretation of the two main tasks of each iteration of ... 0answers 21 views ### Given a set of solutions, find an IP formulation with the same solution set Input: A list of integer variables$x_1, ..., x_n$. A finite set of feasible solutions$S \subset \mathbb{Z}^n$. Task: Find an integer linear program (IP) on the integer variables$x_1,...,x_n$... 0answers 39 views ### Optimizing library dimensions Say I have a library that looks like that: ... 0answers 58 views ### Big M method for continuous variables Is there any way to model the big M method for continuous variables? Something similar to this but$B, C \in \mathbb{R}_{\geq 0}$and$A\in\{0,1\}$. Due to the precision problem, when the$B$and$C$... 0answers 213 views ### maximizing absolute value in linear programming I know that similar questions have been answered several times, and based on the answers, I attempted a solution to my problem. But I simply do not get the right results. The problem is as follows. I ... 0answers 22 views ### Sparse feasible solution$|x|_0\le k$for system of linear inequalities$A x \le b$Suppose the set of linear inequalities$Ax\le b$, in which$A\in\mathbb{R}^{m\times n},x,b\in\mathbb{R}^n$is given. Is it possible to determine in polynomial time with regard to$m$and$n$if there ... 0answers 99 views ### How to solve this optimization problem with logarithmic objective function? I have this optimization problem I have no idea how to solve it. Is Lagrange suitable for this problem? Thank you 0answers 710 views ### Restriction for greater than constraint in linear programming I have a model that considers real values and that uses a binary variable$x$. In this model, the following conditions should apply: \begin{equation} x= \begin{cases} 0, & \text{if}\... 0answers 172 views ### LP realaxation for multicut problem with polynomial number of constraints The integer linear programming formulation for the multicut problem for the given graph$G = (V,E)$and distinguished source-sink pairs of vertices$(s_1,t_1),...,(s_k,t_k)is: \begin{alignat}{3} \... 0answers 34 views ### Time complexity bounds for the approximation of optimal values of bounded linear programs Assume we are given a LP maximization problem defined by a linear functionalc^Tx$and a non-empty feasible region$\{x:Ax\leq b\}$that is known to be bounded by a hypercube of side$R>0$, say$[...
I am having to solve integer programming problem that has the following property: For feasible solution $x$ maps to a large set $S(x)$ or other admissible solutions and I can find the best solution ...