Questions tagged [linear-programming]
Optimization with a linear objective function, subject to linear equality and linear inequality constraints.
428
questions
2
votes
1
answer
20
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
38
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 ...
- 103
1
vote
0
answers
21
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
160
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
0
votes
0
answers
50
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 ...
- 171
0
votes
0
answers
34
views
Are there any ways to reduce the space complexity of the simplex method when dealing with totally unimodular (TU) matrices?
I am try to solve a problem with a strict space complexity and time complexity(60mb and 1s). I use the simplex method, but it requires significant space complexity, reaching up to $O(nm)$.
However, ...
1
vote
1
answer
33
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
3
votes
1
answer
65
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 $\...
- 555
1
vote
2
answers
56
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 (...
- 155
0
votes
1
answer
40
views
Suppose we have two variables $x,y \in [1,n]$. How can we write $x \neq y$ in integer-linear constraint?
If $x,y \in [1,n]$, how to write $x \neq y$ in integer-linear constraint?
Possible Answer:
$x−y\geq 1−(1−t)\times n$ and $y−x \geq 1−t\times n$ where $t \in \{0,1\}$
- 328
4
votes
2
answers
40
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,152
0
votes
1
answer
20
views
Assigning classes to nodes in a graph to minimise intra-class distance
I have an complete undirected graph with n vertices, and the edge $(u,v)$ has weight $d(u,v)$ for some distance function.
I also have $m<n$ elements, each of which belongs to a category $\{1...i\}...
- 1
0
votes
2
answers
82
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, ...
- 121
16
votes
4
answers
3k
views
Why is Integer Linear Programming in NP?
The decision version of the problem Integar Linear Programming is the following:
Input: two matrices $A\in \mathcal{M}_n(\mathbb{Z})$ and $B\in \mathcal{M}_{n,1}(\mathbb{Z})$.
Question: is there a ...
- 16k
3
votes
1
answer
28
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
0
votes
0
answers
26
views
Placement of Tasks from Dataflow Graph on a Physical Graph
I have a dataflow graph where a set of different types of tasks are placed in corresponding types of nodes.
Say the task types are called A, B, and C.
A-type tasks are placed in all the leaf nodes of ...
- 1
0
votes
0
answers
16
views
Given objective value for ILP find parameter is NP hard?
For an integer linear program: Given a matrix $A \in \mathbb{Z}^{n\times d}$ and two vectors $b \in \mathbb{Z}^{n}$, $c \in \mathbb{Z}^{d}$, compute $max\{ c^{\top}x|Ax \leq b, x\geq 0, x\in \mathbb{Z}...
- 113
2
votes
1
answer
25
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
3
answers
84
views
Compute the intersection of two polytopes and its corner points
I am looking for a method in Python/MATLAB to calculate the corner points of polytope which is an intersection of a polytope with half spaces.
I have a polytope P1 of the form
-1 <= x0 <= 1
-1 &...
- 21
0
votes
1
answer
62
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
0
votes
1
answer
91
views
Matching points on a plane with maximum total weight
I have a set of points $P = \{p_1, \dots, p_m \}, \; 0 \le m \le 10^4$ on a plane of two colors (red and green). Each point has integer x-coordinate (all x-coordinates are different), and non-negative ...
- 105
3
votes
2
answers
672
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 ...
- 105
2
votes
1
answer
245
views
Are integer linear *feasibility* problems NP-hard?
I know that Integer Linear Programming problems are NP-hard. But it seems like this answer is only applicable to Integer Linear optimization problems.
It seems like integer linear feasibility problems ...
- 25
1
vote
1
answer
75
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
17
views
From the boundary description to the lattice description of the David Avis & Komei Fukuda's convex hull algorithm
This is a continued question from: The updated convex hull algorithms in 2023?
From Handbook of Computational Geometry (Third edition, 2018) section 26.3, Seidel mentioned the boundary and the lattice ...
2
votes
1
answer
109
views
The updated convex hull algorithms in 2023?
I'm studying the convex hull algorithms in the high dimensions. There were two papers by Bernard Chazelle and T.M. Chan from the 90s, to have achieved the at then the state of the art complexity. ...
0
votes
0
answers
52
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
3
answers
54
views
Which algorithms could be suitable for solving my disjunctive programming problem?
Following a previous post on the cs stack exchange (link to question), I have been searching to no avail for an implementation of a disjunctive programming solver in C# (or wrapped in C#). In this ...
0
votes
1
answer
59
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, ...
0
votes
0
answers
81
views
Minimum set cover problem and dual, the maximum set packing
Just like in This thread that was posted here before, I came upon the same issue where I do not understand how are the relaxed maximum set packing problem and the minimum set cover problem are dual to ...
- 1
1
vote
1
answer
169
views
Solving shortest path with negative weights with linear program. What is the underlying problem we want to solve?
Let us consider a shortest path problem with weights $w_e$ for each edge $e$. It can be formulated as a (integer) linear program (ILP).
\begin{align}
\min \quad &\sum_{e \in E} w_e x_e \\
s.t. \...
- 13
6
votes
1
answer
258
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 ...
- 247
1
vote
0
answers
125
views
Preference based assignment problem to maximize utility
I am studying an optimization problem which can be recast as an LP I have described below. I wish to understand the structure of optimizers of the original problem by studying the optimizers of the LP....
- 11
-2
votes
1
answer
46
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. ...
3
votes
1
answer
141
views
Does a problem remain tractable If a single discrete variable becomes continuous?
Let $\mathcal{F}$ be a family of pairs of the form $(A,b)$, where $A$ is an integer matrix and $b$ is an integer vector with the same number of rows. For every integer $k$, define $L(\mathcal{F}, k)$ ...
- 6,152
2
votes
0
answers
45
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
0
votes
1
answer
113
views
To write an IP and relax it to LP for finding a multi-set in a graph
I am new to Linear Programming and Approximation algorithms. and I am trying to do this exercise for writing an IP and relax it to LP. What I am given:
A digraph ...
- 25
1
vote
1
answer
154
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
1
vote
1
answer
25
views
An algorithm to evaluate the strength of Quiz Participants
As a side-project, I had the idea to write some kind of an algorithm that would evaluate all participations in our weekly Pub quiz, to then calculate the average strength of the participants.
This is ...
2
votes
0
answers
40
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
222
views
Algorithm to distribute group of connected nodes in a graph
Given something similar to this.
Where you have blocks (the squares) and entries (the circles). Each block has a rating (the number inside the blocks) and is connected to other blocks. This topology ...
- 1
0
votes
1
answer
85
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) \...
- 306
2
votes
1
answer
70
views
The set of possible values of linear programs
Consider the set of all linear programs of the form:
maximize $c x$
subject to $A x \leq b$
$x \geq 0$
where there are $m$ variables, $n$ constraints, and all coefficients in $A, b, c$ are integers ...
- 6,152
5
votes
1
answer
914
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
1
vote
1
answer
42
views
Efficiently finding/ sampling from all solutions to a constrained linear problem
Start with $N>3$ vectors $\vec{v}_I$ in $\mathbb{R}^3_+$, any $3$ of which are linearly independent. $I$ here ranges from $0$ to $N-1$.
Let $v_{\left[abc\right]}$ be a matrix in $\mathbb{R}^{3 \...
- 113
1
vote
1
answer
78
views
The length of the shortest $s$-$t$ path equals the maximum tension between $s$ and $t$
I am stuck at the following exercise:
Consider a directed graph $G = (V, A)$ with start vertex $s ∈ V$, target vertex $t \in V$ and weights $w_{ij} \in \mathbb{R}$ for each arc $(i, j)\in A$. For any ...
- 457
1
vote
2
answers
721
views
How does the SMT solver Z3 handle conditional statements in a constraint?
I have a constraint system which I seek to find solutions for.
The constraints consist of lesser/equal inequalities which have a difference of two minimum expressions on their right side, for example:
...
- 33
3
votes
2
answers
147
views
Maximize enclosed area of given figures on 2d grid
I need to solve an optimization problem for a given set of polyominoes, for example the five Tetrominoes known from Tetris. The goal is to place each one of the figures on the 2d grid, so the area ...
- 33
-1
votes
2
answers
160
views
How to prove feasibility?
Let's say I have a optimization problem P1, where the constraints are linear but the objective function is not. Let's say I have another optimization problem which is linear in constraints and linear ...
- 111
2
votes
0
answers
65
views
Balanced Assignment Problem with updatable cost
I have a problem that can be reduced to an assignment problem. (this is related to some cryptography problems)
Which means we have a set $A$ of $n$ agents and an equal size set $T$ of tasks as well as ...
- 121