Questions tagged [linear-programming]
Optimization with a linear objective function, subject to linear equality and linear inequality constraints.
435 questions
0
votes
0
answers
12
views
A generalisation of Theorem 9.3 from Chvatal’s Linear programming
Disclaimer: this question was originally posted on MSE at the end of December, but there have been no answers since then. Cf.: https://math.stackexchange.com/questions/5116936/a-generalisation-of-...
1
vote
1
answer
26
views
Common/standard language for Linear Programming / Constraint Programming / Optimization tasks?
If I wanted to describe the context-free grammar of a programming language, I'd use BNF to increase the chance that other folks immediately recognize my intent, and so I do not have to waste many ...
- 1,313
1
vote
0
answers
43
views
Sparse Kaczmarz with inequalities
Input:
A system of equalities of the form $Ax = b$
A system of inequalities of the form $Ax \le b$
where $x$ is subject to a sparsity objective using a minimized L1-norm.
Output:
$x$ such that its ...
0
votes
1
answer
34
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
4
votes
1
answer
151
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 ...
- 43
3
votes
0
answers
133
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
100
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 ...
- 23
2
votes
1
answer
89
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
2
votes
1
answer
297
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 ...
- 121
1
vote
0
answers
57
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 ...
- 11
2
votes
1
answer
127
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 ...
- 229
2
votes
1
answer
117
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)\...
- 31
0
votes
1
answer
86
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
51
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 ...
- 111
1
vote
1
answer
251
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