Skip to main content

Questions tagged [linear-programming]

Optimization with a linear objective function, subject to linear equality and linear inequality constraints.

Filter by
Sorted by
Tagged with
2 votes
1 answer
25 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)\...
queen's user avatar
  • 31
0 votes
1 answer
39 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 ...
GeorgeKarlinzer's user avatar
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 ...
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 ...
demyutin's user avatar
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 ...
MathStudent101's user avatar
0 votes
0 answers
35 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, ...
Huang Frank's user avatar
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 ...
Rishabh Kothary's user avatar
3 votes
1 answer
67 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 $\...
Lisa E.'s user avatar
  • 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 (...
Serge Rogatch's user avatar
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\}$
Subhankar Ghosal's user avatar
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 ...
Erel Segal-Halevi's user avatar
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\}...
minnie's user avatar
  • 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, ...
Firavox's user avatar
  • 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 ...
Nathaniel's user avatar
  • 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, ...
Ted Hopp's user avatar
  • 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 ...
bsha's user avatar
  • 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}...
wsz_fantasy's user avatar
2 votes
1 answer
27 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 ...
Dar954826's user avatar
0 votes
3 answers
85 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 &...
Möbius's user avatar
  • 21
0 votes
1 answer
63 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 ...
Freddie's user avatar
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 ...
Grigori's user avatar
  • 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 ...
Grigori's user avatar
  • 105
2 votes
1 answer
251 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 ...
user161190's user avatar
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 ...
Namrata Banerji's user avatar
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. ...
ShoutOutAndCalculate's user avatar
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}^...
Makogan's user avatar
  • 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 ...
Ed_Silver's user avatar
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, ...
Ed_Silver's user avatar
0 votes
0 answers
84 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 ...
Zig302's user avatar
  • 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. \...
Junyan Su's user avatar
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 ...
Samuel Bismuth's user avatar
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....
Reema's user avatar
  • 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. ...
Klara Lampret's user avatar
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)$ ...
Erel Segal-Halevi's user avatar
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 ...
Sandra's user avatar
  • 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 ...
ConScience's user avatar
1 vote
1 answer
162 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 ...
B.D.'s user avatar
  • 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 ...
Mantas Kandratavičius's user avatar
2 votes
0 answers
41 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. ...
ltl's user avatar
  • 31
0 votes
1 answer
223 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 ...
ikerdc's user avatar
  • 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) \...
codeing_monkey's user avatar
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 ...
Erel Segal-Halevi's user avatar
5 votes
1 answer
917 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 ...
bjornte's user avatar
  • 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 \...
kram1032's user avatar
  • 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 ...
3nondatur's user avatar
  • 457
1 vote
2 answers
730 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: ...
MvB's user avatar
  • 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 ...
Tobi's user avatar
  • 33
-1 votes
2 answers
161 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 ...
Jash Shah's user avatar
  • 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 ...
SRichoux's user avatar
  • 121
1 vote
0 answers
110 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: ...
Nick Bishop's user avatar

1
2 3 4 5
9