Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
1 vote
2 answers
50 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
38 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
3 votes
2 answers
30 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
18 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
73 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
  • 111
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
  • 15.7k
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
22 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
21 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
2 answers
55 views

compute the intersection of two polytopes and it's 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
46 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
82 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
660 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
181 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
55 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
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 ...
ShoutOutAndCalculate's user avatar
2 votes
1 answer
86 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
56 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 ...
Muhammad Z's user avatar
0 votes
0 answers
38 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
51 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
51 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
59 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
152 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
0 votes
0 answers
35 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 ...
Redwill's user avatar
0 votes
0 answers
24 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 ...
Amin's user avatar
  • 101
6 votes
1 answer
249 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
117 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
43 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
  • 63
0 votes
1 answer
112 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
96 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
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 ...
Mantas Kandratavičius's user avatar
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. ...
ltl's user avatar
  • 31
0 votes
1 answer
208 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
77 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
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 ...
Erel Segal-Halevi's user avatar
5 votes
1 answer
759 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
39 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
75 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
620 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
139 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
143 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
60 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
103 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 vote
0 answers
54 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 (...
mathworker21's user avatar
0 votes
0 answers
36 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 ...
tfreifeld's user avatar
  • 101
0 votes
0 answers
29 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 ...
Qarmagod's user avatar
1 vote
0 answers
39 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 ...
user1868607's user avatar
  • 2,194

1
2 3 4 5
9