Questions tagged [linear-programming]
Optimization with a linear objective function, subject to linear equality and linear inequality constraints.
433 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
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,\\
&{\...
3
votes
1
answer
127
views
Assignment problem with dependencies between assignments
I've been working on a simulator for my grid based game in order to find optimal solutions. One heuristic I'm using to prune the search space is the distance to goals. There are n players and m goals ...
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 ...
1
vote
2
answers
87
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
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 ...
2
votes
1
answer
268
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
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
vote
0
answers
53
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
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 ...
2
votes
1
answer
106
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
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
0
answers
46
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
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 ...
0
votes
0
answers
82
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
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 ...