# Questions tagged [linear-programming]

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

428 questions
Filter by
Sorted by
Tagged with
20 views

1 vote
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
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. ...
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
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
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 ...
1 vote
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
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 ...
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
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 ...
85 views

• 113
1 vote
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
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
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
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
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 ...