Questions tagged [linear-programming]
Optimization with a linear objective function, subject to linear equality and linear inequality constraints.
409
questions
2
votes
1
answer
57
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
30
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
13
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
61
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
51
views
Solving the Double-Choco Puzzle: Matching Sub-Matrices with Rotation and Mirroring
I'm working on implementing a solver for Double-Choco puzzle which published by Nikoli magazine. starting by representing the board cells as matrix containing cells with values 1 or 0, where 1 ...
- 111
0
votes
0
answers
18
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}^...
- 291
0
votes
3
answers
36
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
36
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
23
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
53
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
0
votes
0
answers
32
views
Algorithm to maximize generated maze score
I need to generate maze with 100x100 rooms. Each room connected only with 1 other room.
Here are example of correct 2x2 mazes:
+-+-+
|...|
+-+.+
|...|
+-+-+
And ...
- 1
0
votes
0
answers
22
views
How to solve MAB by linear program?
To solve multi-armed bandit problem, the common approaches are UCB or TS and there are many variants of these algorithms. I am wondering if it is possible to model and solve this problem as a linear ...
- 101
5
votes
1
answer
218
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 ...
- 127
1
vote
0
answers
100
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
40
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
137
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)$ ...
- 5,790
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 ...
- 53
0
votes
1
answer
102
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
71
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
23
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
34
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.
...
- 21
0
votes
1
answer
113
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
43
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) \...
2
votes
1
answer
69
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 ...
- 5,790
5
votes
1
answer
386
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
34
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
67
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
340
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
104
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
99
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
47
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 ...
- 21
1
vote
0
answers
76
views
Why is the ellipsoid method for linear programming only weakly polynomial time?
I am trying to understand why the ellipsoid method is not a strongly polynomial time algorithm for linear programming. Using wikipedia's definition, an algorithm runs in strongly-polynomial time if:
...
- 111
1
vote
0
answers
49
views
How to find optimizers with computer in this kind of minimax problem [closed]
I have a minimax problem of the form $$\max_{\substack{u_1,\dots,u_n \ge 0 \\ u_1+\dots+u_n = 1}} \min_{\substack{v_1,\dots,v_m \ge 0 \\ v_1+\dots+v_m = 1 \\ v_{j_1} \le v_{j_2} \hspace{1mm} \forall (...
- 156
0
votes
0
answers
29
views
Identifying the parameters and finding an optimal solution to a problem
I work in the Computer Graphics field, and I have a problem where I need to find the optimal solution for, but I'm not sure how to best formulate the problem mathematically, how to define the ...
0
votes
0
answers
21
views
Cutting stock problem upper bound with gilmore and gomory
I am trying to implement this article https://arxiv.org/pdf/1905.04897.pdf (the article is there only for information, no need to read it to answer my question)
At some point they say when talking ...
- 1
1
vote
0
answers
35
views
Papadimitriou's pseudopolynomial algorithm for m x n integer program with fixed m
Consider the following proof from Papadimitriou's "On the Complexity of Integer Programming":
Corollary 1. There is a pseudopolynomial algorithm for solving m x n integer programs, with ...
- 2,240
2
votes
1
answer
119
views
Integer linear programming formulation of boolean selection
Given a boolean variable $x$ and nonnegative integer variable $s$, I want to select $y = \begin{cases}
0 & \text{if} \ x = 0 \\
s & \text{if} \ x = 1
\end{cases}$.
Currently in the ...
- 21
1
vote
2
answers
641
views
Prove that a quadratically-constrained linear program (QCLP) is NP-Complete
Show that if we strengthen linear programming by also allowing constraints of the form $$ \sum_{i,j = 1}^n a_{ij} x_i x_j = b,
$$ for integers $b$ and $a_{ij}$, then the problem becomes NP-complete.
...
- 113
1
vote
1
answer
48
views
Why do we round from 1/2 when converting the LP to ILP for the weighted vertex cover problem?
I understand that to approximate a solution to the weighted vertex cover, we need to relax the integer linear program to a linear program which can be solved in polynomial time, but why do we round ...
- 13
2
votes
1
answer
40
views
How can I best represent my 2D thrust problem as a linear programming problem?
While my question stems from game dev, the problem itself isn't as much about the game, but more about correctly representing my problem as a linear programming problem that I can solve with a linear ...
- 123
1
vote
0
answers
37
views
Dual Linear Program of the Densest-Subset Problem
In the densest-subset problem, given an undirected graph $G = (V, E)$, the goal is to
maximise the “edge-density” ratio $|E(S)|/|S|$
over all non-empty sets $S ⊆ V$ , where $E(S)$ denotes the
set of ...
- 413
1
vote
0
answers
17
views
What are the locally optimal points in an LP formulation of the max flow problem?
I'm taking a grad level algorithms course and we just ended the course talking about linear programming, and we had previously talked about the max flow/min cut problem. Our professor said that the ...
- 111
3
votes
0
answers
23
views
Advantages of Integral over Non-integral Linear Program?
I have a linear program over real variables for which it can be shown that all the vertices of the polytope describing its feasible region are integral.
Obviously I can just solve this using a ...
- 131
0
votes
1
answer
87
views
MAX-LP: maximize number of linear inequalities satisfied
Consider the following variant of linear programming, where we want to maximize the number of linear inequalities that are satisfied:
Input: linear inequalities $A_1x\le b_1$, ..., $A_nx \le b_n$; an ...
D.W.♦
- 154k
1
vote
1
answer
93
views
Proof that using residual network from Ford-Fulkerson will get you min-cut
So I'm following this article and they use the following algorithm to find the min-cut.
Algorithm:
Run Ford-Fulkerson algorithm and consider the final residual graph.
Find the set of vertices that ...
- 141
1
vote
1
answer
36
views
Linear encoding of a feed forward neural network
I was reading [1] about reachability analysis of a feed forward neural network (FFNN). The paper encodes a FFNN as a linear programming problem. Suppose $x^{(i)}$ is the vector output of the ith layer,...
- 13
1
vote
1
answer
672
views
If greater than or equal to zero then binary variable equals 1: integer linear program
I have a variable $d_{i} \in \mathbb{Z}$ with an upper and lower bound. I also have a binary variable $v_{i}$ which I want to $=1$ if $d_{i} \geq 0$; else $v_{i} = 0$. How do I enforce this as a ...
- 23
1
vote
1
answer
41
views
Can't figure out decision variable
Good Evening, I am trying to solve an exercise related to my algorithm designing course. I have understood the question and what it asks. I am required to formulate an ILP and then relax it to ...
- 25
0
votes
0
answers
67
views
ILP - Maximize the number of pairs of variables with the same value
I have a 0-1 integer linear program for a set of $2n$ variables $S = \{x_1, ..., x_n, y_1, ..., y_n\}$. My objective is to maximize the number of pairs $(x_i, y_i)$ such that $x_i = y_i$, $i = 1, ..., ...
- 143
0
votes
0
answers
25
views
minimizing std. dev. in linear programming
I'm new to Linear Programming and trying to create an automated scheduling algorithm, and am having trouble defining the objective function and decision variables. Any help would be appreciated:
Let ...
- 11