Questions tagged [linear-programming]
Optimization with a linear objective function, subject to linear equality and linear inequality constraints.
432 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
2
votes
0
answers
97
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 ...
1
vote
2
answers
70
views
How to invert feasibility of an ILP without solving it
Given an ILP, e.g., $Ax\leq b,ドル is there some transformation you can apply to it to obtain another ILP that's feasible iff $Ax\leq b$ is infeasible? In particular, a transformation that doesn't ...
2
votes
1
answer
53
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 ...
2
votes
1
answer
227
views
Assignment problem, but minimise the greatest individual cost, rather than the aggregate cost
https://en.wikipedia.org/wiki/Hungarian_algorithm
In the assignment problem as described above, the goal is to find an assignment that minimizes the total cost, and the Hungarian Algoirthm is a ...
0
votes
0
answers
13
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
vote
0
answers
38
views
Is it possible to modify the transportation problem to enforce that each destination is supplied by only one source?
Problem Description:
I have a standard transportation problem with:
m sources, each with a given supply capacity.
n destinations, each with a specific demand.
A cost associated with transporting ...
2
votes
1
answer
104
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 ...
0
votes
0
answers
25
views
LP duality for approximate bounded degree
$\begin{align*}
&\text{min } \epsilon \\
&|f(x) - \sum_{|S|\leq d} c_S \chi_S(x)| \leq \epsilon, \ \ \ x \in D \\
&|\sum_{|S| \leq d} c_S \chi_S(x)| \leq 1 + \epsilon, \ \ \ x \in \{-1,...
2
votes
1
answer
93
views
Constrained optimization with batches/chunks?
Suppose I have $n$-dimensional real vectors $\mathbf u,ドル $\mathbf v,ドル $\mathbf w,ドル with $\mathbf v>0$. I'd like to maximize the following function $f$:
$$
f(\mathbf x)=\sum_{i}(u_ix_i-v_ix_i^2)\...
0
votes
1
answer
60
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
0
answers
30
views
Find a basis of a vector space minimizing the numbers of nonzero coordinates for a bunch of vectors
I've got a (to be a bit specific) 84-dimensional rational vector space, and as many as 1197 vectors in it. In the basis of the space that I've got, numbers of nonzero coordinates for these vectors ...
1
vote
1
answer
217
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 ...
0
votes
0
answers
62
views
Solving a problem with linear programming
Suppose we wish to create a speech. Assume we have $n$ words to choose from numbered from 1ドル$ to $n$. Every word holds a list of words that can come after it $S_i$. For example: if 2ドル \in S_1$ then ...
1
vote
1
answer
54
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 ...
3
votes
1
answer
101
views
Maximum distance between two points of a polyhedron
Given a (bounded and feasible) polyhedron, $P=\{x\mid Ax\le b\}$ and a number $\gamma > 0,ドル decide if there are two points $x, y \in P$ such that $\Vert x - y\Vert_p \ge \gamma$.
Is there an $\...