Questions tagged [linear-programming]
Optimization with a linear objective function, subject to linear equality and linear inequality constraints.
433 questions
0
votes
1
answer
29
views
Linear programming question
In the book of Papadimitriou. Combinatorial optimization, there is the instance of Linear Programming (LP) s.t.
\begin{equation}
\begin{split}
&{\rm minimize:\;} c_1x_1 + c_2x_2 + c_3x_3,\\
&{\...
- 129
3
votes
0
answers
126
views
Complexity of solving (very simple) systems of linear inequalities
It is known that solving systems of linear (in)equalities over rational or real numbers takes polynomial time. In some cases, it is $\mathsf{P}$-complete. I wonder whether solving the following type ...
2
votes
1
answer
75
views
Baseball elimination problem with draws
Here is a quick run-down of the baseball elimination problem:
https://en.wikipedia.org/wiki/Maximum_flow_problem#Baseball_elimination
This however is usually only used with a win-loss system. But ...
- 21
0
votes
0
answers
25
views
Adam gradients for least squares approaches?
Least squares leads to an n-dimensional "parabola" in the parameters. I assume the same is valid for other constrained least squares like non-negative least-squares.
This may be a wrong ...
- 1
2
votes
1
answer
121
views
About complexity of Polynomial time (Karp) reduction
[Resource/information request]
I would like to know if, in literature, there exist two languages $L_1$ and $L_2 \in NP$-complete set such that reducing $L_1$ to $L_2$ amounts to solving an instance of ...
- 209
0
votes
1
answer
79
views
Optimization of resources allocation
Simplified problem:
Let's say we sell chicken. There are an order for today for 10 pieces from KFC that requires chicken to be good for at least 1 month and an order for tomorrow for 5 pieces from ...
1
vote
1
answer
231
views
Can this Integer Linear Programming problem be solved in polynomial time?
I have $n$ binary variables, and $m$ constraints. Each constraint can be stated as: "exactly $b$ of the variables in $S$ are equal to 1", for some positive integer $b$ and subset of the ...
- 13
1
vote
1
answer
72
views
Poly Time Algorithm for (0/1) Basic Feasible Solution
I have an LPP where the basic feasible solution is a vector in $\{0,1 \}^n$. I am not very well versed in linear programming and would like to know if poly-time algorithms exist to find such a basic ...
- 135
1
vote
2
answers
136
views
Is there a linear programming method that is polynomial in the number of variables, constraints and bitlength of numbers?
AFAIK, Interior Point method for solving a system of linear inequations is polynomial in the number of variables and constraints. Probably there are others. I don't need to optimize any function (...
- 165
5
votes
2
answers
159
views
Run-time complexity of solving a system of integer linear equations
Given an integer $n$-by-$n$ matrix $A$ and an integer $n$-by-$1$ vector $b$, what is the run-time complexity of finding an integer solution $x$ to the system $A x = b$?
In general, integer linear ...
- 6,087
0
votes
2
answers
172
views
Decision-Version of Linear Programming not in P?
Linear programming is the very common problem of computing
$$\min_{Ax\leq b}c^\top x,$$
where $A\in\mathbb{R}^{n\times m}$, $b\in\mathbb{R}^n$, and $c\in\mathbb{R}^m$. This is an optimization problem, ...
- 178
3
votes
1
answer
56
views
How can I model this optimization problem?
We're looking to model the following problem as a standard optimization problem (or even a non-standard one). We can come close, but nothing seems to fit exactly. We have a working algorithm coded, ...
- 133
2
votes
1
answer
70
views
Parametrized threshold for LP Approximation in Vertex Cover Problem
I would like to have a formal description on how parametrizing the threshold in the approximation of vertex cover using LP would impact the approximation factor of the problem.
The linear programming ...
- 21
0
votes
1
answer
168
views
Should I use linear programming for my timetable generator?
I am creating a timetabling software for a school, which given parameters for teachers/class sizes will output a timetable. There will be a list of classrooms per subject and a list of teachers per ...
- 1
3
votes
2
answers
768
views
Find max total revenue in a directed graph
Problem:
Imagine you are an agent with a knapsack, who travels a known route of cities. All cities are different: $C_1 \rightarrow C_2 \rightarrow \dots \rightarrow C_n$. Each city offers you to buy ...
- 125
1
vote
1
answer
156
views
Why is infeasibility of linear programming considered to be an NP problem?
I recently came across this question, and the way I think people usually go about this is to find a certificate that answers 'yes' to the decision problem 'Is this LP infeasible?' Or, given a ...
0
votes
0
answers
104
views
Getting a V-representation from an H-Representation of a polytope
I am trying to find an easy to follow resource on implementing any (reasonable) algorithm to find a V-represnetation of a polytope from its h-representation. I only need this to work for $\mathbb{R}^...
- 341
0
votes
1
answer
127
views
Can a linear programming method be used to solve systems of inequalities with OR (disparate) compound inequalities?
I recently discovered linear programming and it seemed perfect for a CS problem I wanted to solve a few months ago. This task involved solving a large quantity of inequalities at once.
For example, ...
- 13
8
votes
2
answers
400
views
Can we compute in polynomial time, an upper bound on an optimal solution of an integer linear program?
Consider the following integer linear program (where $A$ is an integer matrix, $b$ an integer vector, and $c$ a positive integer vector):
$$
\text{minimize}~~~ c\cdot x
\\
\text{subject to}~~~ A\cdot ...
- 269
-2
votes
1
answer
70
views
How to solve a linear programming problem
Given a problem (D, c, Min) with admissible set
D={(x,y)∈R2 : |y+√3x|≤2√3,|y-√3x|≤2√3,|y|≤3}
and the price function c(x, y) = x + 2y.
Translate the given problem to a linear program in standard form. ...
2
votes
0
answers
64
views
Designing Shortest Route
Suppose we have a metric space $(X,d)$ and we call $r$ to be a root vertex and then there are $n$ clients(i.e. $n$ vertices/nodes) who need packages delivered to them from $r$. The $i$th client ...
- 73
1
vote
1
answer
342
views
Boolean Integer Linear Optimization/Programming
Trying to solve an ILP optimization problem with a number of potential boolean variables and then express constraints on these variables based on those boolean results.
Let's say I am doing 5 coin ...
- 11
2
votes
0
answers
56
views
A covering problem -- find $n$ triangles to cover $m$ points and minimize the total area of the $n$ triangles
Suppose we are given $m$ points on $\mathbb{R}^2$. Consider $n=1, 2, 3, \dotsc$; we want to cover the $m$ points with $n$ triangles (of any shape) while minimizing the total area of the $n$ triangles.
...
- 31
0
votes
1
answer
127
views
LP Approximation for Vertex Cover Problem
In Cormen's Introduction to Algorithms, he states the the LP relaxation for the minimum vertex cover approximation problem is $ \begin{align*}
&\sum\limits_{v \in V}w(v)x(v) \...
- 302
5
votes
1
answer
1k
views
Nesting algorithm for rectangular-based, fixed-orientation polygons
I'm looking for an algorithm that is closely related to the 2-dimensional nesting problem (also known as lay planning, bin packing, and the cutting stock problem).
The main differences between this ...
- 151