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
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 ...
user161190's user avatar
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 ...
Namrata Banerji's user avatar
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 ...
ShoutOutAndCalculate's user avatar
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. ...
ShoutOutAndCalculate's user avatar
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 ...
Muhammad Z's user avatar
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}^...
Makogan's user avatar
  • 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 ...
Ed_Silver's user avatar
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, ...
Ed_Silver's user avatar
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 ...
Zig302's user avatar
  • 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. \...
Junyan Su's user avatar
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 ...
Redwill's user avatar
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 ...
Amin's user avatar
  • 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 ...
Samuel Bismuth's user avatar
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....
Reema's user avatar
  • 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. ...
Klara Lampret's user avatar
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)$ ...
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
  • 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 ...
ConScience's user avatar
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 ...
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
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. ...
ltl's user avatar
  • 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 ...
ikerdc's user avatar
  • 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) \...
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
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 ...
bjornte's user avatar
  • 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 \...
kram1032's user avatar
  • 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 ...
3nondatur's user avatar
  • 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: ...
MvB's user avatar
  • 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 ...
Tobi's user avatar
  • 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 ...
Jash Shah's user avatar
  • 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 ...
SRichoux's user avatar
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: ...
Nick Bishop's user avatar
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 (...
mathworker21's user avatar
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 ...
tfreifeld's user avatar
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 ...
Qarmagod's user avatar
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 ...
user1868607's user avatar
  • 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 ...
Wentinn Liao's user avatar
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. ...
hexaquark's user avatar
  • 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 ...
Insanit's user avatar
  • 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 ...
Nathan K's user avatar
  • 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 ...
SVMteamsTool's user avatar
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 ...
Aphyd's user avatar
  • 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 ...
Richard Forrest's user avatar
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.'s user avatar
  • 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 ...
Gooby's user avatar
  • 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,...
Vanessa's user avatar
  • 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 ...
Alex Pharaon's user avatar
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 ...
ConScience's user avatar
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, ..., ...
Null_Space's user avatar
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 ...
Jason's user avatar
  • 11

1
2 3 4 5
9