Questions tagged [linear-programming]
Optimization with a linear objective function, subject to linear equality and linear inequality constraints.
357
questions
3
votes
1answer
101 views
Learn a system of linear inequalities given solutions
Instead of finding a solution to a system of linear inequalities (Ax + b >= 0), I want to find any system of linear inequalities that satisfy a set of feasible ...
1
vote
1answer
106 views
Is there an algorithm to solve the following point clustering problem?
According to this post
Given $n$ points $P=\{p_1,p_2,\dots,p_n\}$ in 2D space, and a matrix $D^{n\times n}$ with the distances between each pair of points, we want to partition the points into two ...
1
vote
1answer
68 views
Formulate a 2-clustering problem in LP
The problem:
Suppose there are $n$ points in plane, and we want to partition points into two clusters such that sum of diameter of clusters is minimized. The diameter of cluster is maximum distance ...
0
votes
0answers
39 views
Recommendations on where to learn and practice linear programming?
[CLOSED] Thanks!
I am studying Linear Programming in college but I am facing some difficulties to assimilate some concepts.
So do you have any recommendations of materials to learn or practice Linear ...
1
vote
0answers
146 views
Fixed Parameter Tractable for Special Vertex Cover using ILP
The problem I'm trying to solve reads as follows:
Given a graph $G=(V,E)$ ,a parameter $k$ and two values $U^\star, P^\star \in \mathbb N$, where every vertex $v\in V$ has a utility and a pollution $...
0
votes
0answers
28 views
Maximizing an integer Linear problem
i am taking a basic Linear programming class this semester and we've recently started solving integer linear problems. I have a question regarding how to solve one of these exercises.
$$
z = max\: 5x_{...
0
votes
0answers
15 views
Solving Multi-Objective Linear Programming Problem
I've read in Wikipedia for Multi-Objective Linear Programming Problems (MOLPPs) that there is a variant of the simplex method used to solve such problems. So, I was wondering if it can be solved using ...
0
votes
1answer
17 views
Linear programing modeling
I am trying to prepare for my Linear programing exam and i stumbled upon an exercice that i can't wrap my head around. It goes like this.
Seven days before the final match a tennis player is trying to ...
1
vote
1answer
42 views
Find optimal play by optimizing orders of each player alternatingly
A zero-sum game for two players allows a player to take no action during a turn. Can I reach optimal play (where both players always choose the best possible action in each turn) by the following ...
0
votes
1answer
63 views
Non-convex linear program optimisation with infinite number of OR constraints
I am aware that when we have a linear problem subject to OR constraints, the LP would be a non-convex optimisation problem. For example,
${x = 0}$ OR ${1<=x<=2}$.
My question is in such a ...
0
votes
0answers
22 views
Optimisation of workforce allocation
I am looking at a problem of cost optimisation by dynamic staff allocation.This could be for any public space like Airport/Railway Station etc. where the maintenance work is outsourced to other ...
0
votes
1answer
24 views
Solving linear programming problem with mixed type of constraints
I have a query in solving the problem below:
An automobile company has two factories. One factory has 400 cars (of a certain model)
in stock and the other factory has 300 cars (of the model) in stock. ...
0
votes
0answers
15 views
Linear programming infeasible problems
A part of ORCA local avoidance collision is calculating a linear program with an incremental approach - adding the constraints one by one. If the problem is determined to be infeasible, the ...
2
votes
1answer
30 views
1/2 Approximation to MAX-DICUT by rounding a linear program
Consider a graph $G=(V, A, w)$, where each arc $(u,v)\in A$ has a non negative weight $w_{u,v} \in \mathbb{R}^+$, partition $V$ into $U$ and $W$, $W=V-U$ such that $\sum_{(i,j)\in A} w_{i,j}z_{i,j}$ ...
0
votes
1answer
41 views
Finding lowest point in circles
Given n disks in the plane, i want to compute the lowest point in their intersection area, im looking for a simple randomized incremental algorithm.
There are some circles in the plane, these circles ...
1
vote
2answers
67 views
Linear program for min-length pair of edge-disjoint paths problem
Consider a problem: we have an undirected graph $G = (V, E)$, function $l: E \to \mathbb{Z}_{+}$ where $l(e)$ is edge's length $e \in E$, and two vertices $s$ and $t$. And we want to find a pair $(A, ...
1
vote
1answer
54 views
k-polynomial time approximation algorithm for set cover (k = max size of subsets)
Problem Definition: Given a universe set $U = \{1, 2, \dots, n\}$ and a collection of $m$ subsets $S_1, S_2, \dots S_m \subseteq U$, find the minimum collection of subsets that cover $U$.
I am ...
0
votes
0answers
15 views
Multi-Objective Implicit Hitting Set for Multi-Objective MaxSAT
MaxSAT is a problem related to SAT where there is a finite collection of hard and soft clauses which share boolean variables. The hard clauses must be satisfied while the soft clauses have a weight. ...
2
votes
1answer
39 views
Lower bound on positive coefficients of the optimum of 0,1-linear programming problem
I have an instance linear programming such that the coefficients and the constant terms are 0 or 1.
Formally, the set of variables is denoted as $V$ and $|V| = n$. There are $m$ constraints, formed as
...
1
vote
1answer
67 views
What happens when we increase or decrease capacities in the minimum flow?
I am confused from these 2 true-false questions on the max flow and am seeking clarity on the basics.
If in a network we increase the capacity of an edge in the minimum cut, the maximum
flow gets ...
0
votes
0answers
28 views
How to determine the number of active linearly independent constraints in a basic feasible solution for linear programming?
I am trying to determine if a given solution is a basic feasible solution. I am working with an $n-$dimension polyhedron $P$ defined by a set of $M$ inequalities $Ax \leq B$. I am running into an ...
0
votes
0answers
31 views
Linear Programming Problems with decimal solutions for problems requiring whole number solution
I have an LPP which asks for the maximum number of pairs of shoes that can be manufactured to maximize the profit. The LPP is:
$$
\begin{align}
\max\ Z&=1350x + 975y\\
\text{Subject to}:&\\
3x+...
5
votes
0answers
43 views
2-Dimensional interval scheduling problem
I have a problem that is similar to the conventional interval scheduling algorithm but it is two dimensional, so I have another metric to take into account. My dataset format:
Cars with the start and ...
0
votes
1answer
20 views
How/why is switch made from equation to inequality for certificate of optimality for dual problem in linear programming?
I am reading Chapter 7 Linear Programming in Algorithms by Dasgupta et al.
I don't get how they switch from an equation to an inequality specifically the part highlighted in red/pink regarding the ...
2
votes
2answers
146 views
Maximum weight perfect matching in general graphs
Let $G(V,E)$ be a graph (not necessarily bipartite), where edge $e \in E$ has weight $w_e$ (non-negative real). Then one can write the LP relaxation for maximum weight perfect matching as follows
$$
\...
2
votes
1answer
120 views
Efficient algorithm to compute the diameter of a convex set?
Is there a polynomial algorithm that can compute the diameter (the distance between the furthest points) of a convex set?
It is possible to do it efficiently for a set of points, but imagine that the ...
2
votes
1answer
48 views
When LP solution is ILP solution?
For many discrete problems, it's natural to consider their continuous relaxations. A common case is when instead of $x_i \in \{0, 1\}$ we allow $x_i \in [0, 1]$. In certain cases, the original problem ...
2
votes
1answer
35 views
Expressing a constraint of the form $\max(x_1,x_2) \ge q$ in a linear program
I am trying to solve an LP in which one of the constraints is mentioned below,
$$\max(x_1,x_2) \ge q,$$
where $x_1 \ge 0$ and $x_2 \ge 0$.
Is it possible to do in linear programming?
1
vote
0answers
47 views
Best algorithm/model to establish relevance between events utilizing mixed data type (Tags, Time, x_coordinate, y_coordinate)? [closed]
I'm building a relevance ranking system for incidents occurrence and prevention. My goal is to use four attributes to establish relevance: tag (About 500 tags), x_coordinate, y_coordinate and time. ...
1
vote
1answer
25 views
Finding optimal separating value
Problem description
We are given two sorted arrays of even numbers: A and B.
Values of A are generally supposed to be smaller than values of B. So we are asked to find a value X where X is an odd ...
0
votes
0answers
17 views
estimating optimal solution for LP with strict inequalities
I have an LP problem with strict inequalities that cannot be relaxed. I understand that most LP solvers require the problem to not have any strict inequalities as it is impossible to find an optimum ...
0
votes
1answer
33 views
Combinatorial optimization algorithm with constraints and objective function
I'm looking for an algorithm that will let me optimally select items from a set. These items have properties which are involved in defining constraints as well as the objective function.
.e.g
Say each ...
0
votes
0answers
62 views
What is the significance of Bellman-Ford and linear programming for scheduling and makespans?
CLRS exercise 24.4-9 says the following:
Show that the Bellman-Ford algorithm, when run on the constraint graph for a system $Ax \leq b$ of difference constraints, minimizes the quantity $\max_i\{x_i\...
2
votes
1answer
26 views
Linear separability
I have an assignment in linear programming and this question was asked:
given an input of two data sets $P_1,P_2$ containing points $(x,y)$, create a linear program that finds an equation of a line ...
0
votes
0answers
33 views
How to find the optimal assignment using the Kuhn-Munkres algorithm?
I managed to get through the Wikipedia article until the last step and I have implemented an algorithm that can reach the optimum.
Unfortunately the article does not say anything about how can I make ...
0
votes
2answers
52 views
Infeasible linear programming reduce errors to find solution
Most normal linear programming problems look like this:
We choose some point in the double shaded area that solves our optimizer and we're good to go.
However, I've come across a problem where it's ...
1
vote
1answer
32 views
Approximate LP for vertex cover problem
I am studying the topic of vertex cover on coursera and how it can be solved approximately by linear programming. Suppose the optimal solution for the vertex cover problem is $OPT$. I do not ...
0
votes
0answers
28 views
IF THEN condition in Linear Program
I have the following condition in an LP problem. I have a variable $x_i \in i = 1,2,..7$ and I need to constrain the problem via:
if $x_1$ >5 then $x_2 \leq 30$
I'm stumped on how to formulate that ...
2
votes
1answer
31 views
What is the best algorithm to find the optimal path in reducing company's real-estate footprint?
I was hoping someone could point me in the right direction in terms of what type of problem I am describing and what type of algorithm I should use to answer it.
Here is the problem: A company is in ...
1
vote
0answers
29 views
IP Programming - objective function ist not a function BUT a table
Here is a short description of my problem:
Part of my objective function is not a regular function. Instead it's a table.
You can see a short extract here:
So if the height is smaller or equal to 300 ...
0
votes
1answer
56 views
Integer programming with indicators
I have the following question, and I need to write it as an integer programming problem:
A manager of a company wants to by presents to his 100 employers. He can buy the presents from two different ...
1
vote
1answer
23 views
linear time nash equilibirum aproximations for two player zero sum games
I'm working on an AI for a game where I'd like the game where each player has hundreds of moves to select from and so the game matrix has 10s of thousands of entries. The game is however zero sum. ...
0
votes
0answers
27 views
Formulating if-then constraints in linear binary programming
From a stock of various computer accessories of different brands, the optimization problem requires deciding to keep or discard products. The decision should be made maintaining the following if-then ...
-1
votes
3answers
48 views
Which topics of mathematics should I need to learn to be a good app developer?
I'm 29 years old. I couldn't continue my studies after grade 10 due to some financial issues and I didn't have time to practice mathematics. It's been more than 11 years since I left studies. Now I ...
2
votes
0answers
241 views
Strong polynomial time algorithm for deciding LP feasibility
Let
$$A \cdot X + B \preceq 0$$ be a system of linear inequalities with $X \in \mathbb{R}^n$ $A\in \mathbb{R}^{m\times n}$ and $B \in \mathbb{R}^m$ where $m \geq n$. According to Farkas lemma, exactly ...
1
vote
2answers
59 views
Linear programming vs integer linear programming
Given $A,b$, let $Ax \le b$ be an instance of linear programming on the variables $x=(x_1,\dots,x_n)$. Assume that the constraints $0 \le x_i$ and $x_i \le 1$ are included in $A,b$.
Suppose that ...
0
votes
0answers
14 views
Integer Linear (ILP / MILP) Formulation for Collision Avoidance of Convex Polytopes / Polyhedra
I am looking for a possibility to avoid the collision of two convex polytopes using (mixed integer) linear programming. I know how I can detect a collision (Akgunduz, A., Banerjee, P., and Mehrotra, S....
2
votes
0answers
43 views
Randomized Assignment Problem
Given $x_1,...,x_n,y_1,...,y_n\in \mathbb{R}^d$ find a permutation matrix $P\in\mathbb{S}_d$ that minimizes $\sum_{ij}P_{ij}|x_i-y_j|$.
This is an assignment problem and can be solved in $O(n^3+n^2d)$ ...
3
votes
0answers
53 views
Algorithm to cut a sphere in half with a plane and maximize the number of points on the sphere surface on one side of the plane
Consider a sphere with a coordinate system like the earth. There are $N$ points on its surface at random positions. For all the infinite planes that cuts the sphere exactly in half (i.e. the sphere's ...
2
votes
1answer
35 views
In what cases is solving Binary Linear Program easy (i.e. **P** complexity)? I'm looking at scheduling problems in particular
In what cases is solving Binary Linear Program easy (i.e. P complexity)?
The reason I'm asking is to understand if I can reformulate a scheduling problem I'm currently working on in such a way to ...
