Questions tagged [linear-programming]
Optimization with a linear objective function, subject to linear equality and linear inequality constraints.
368
questions
0
votes
1answer
14 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 ...
0
votes
0answers
32 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, ..., ...
0
votes
0answers
21 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 ...
1
vote
0answers
46 views
Shortest path as a linear program
I just encountered this formulation of the shortest $s$-$t$ path problem as a linear program in a homework. I don't understand exactly the meaning of the variables and restrictions. Here, $G = (V, E)$ ...
1
vote
1answer
22 views
Linear programming for prefix of graph
Question: Consider an arbitrary directed graph $G$ with weighted vertices, the weights can be positive, negative or $0$. The prefix of $G$ is a subset of vertices $P$ such that there's no edge $(u \...
0
votes
1answer
40 views
How are vertex capacities defined in a flow network?
I'm new to network flows and I'm reading this topic from Cormen's Algorithms book (3rd edition) from 26 chapter. I came across this problem from the 26.1 section
Suppose that, in addition to edge ...
1
vote
0answers
39 views
Linear Program, minimize maximum distance
Given: Set $N = \{0, \ldots, n-1\}, k \in \mathbb{N}, d_{ij} \geq 0$ with $d_{ii} = 0$.
Task: Find subset $C \subseteq N, |C| \leq k$ that minimizes $\max_{i \in N} \min_{j \in C} d_{ij}$.
Idea: I ...
10
votes
0answers
61 views
Maximum matching with social distancing
Let $G = (X\cup Y, E)$ be a bipartite graph. Suppose $X$ contains people, $Y$ contains seats in a theatre, and each edge $(x,y)$ has a weight representing how much person $x$ is willing to pay for ...
1
vote
0answers
28 views
Linear programming and network flow
I would like some hint in this homework question. I have to write the max-flow problem (with souce $s$ and sink $t$) as a linear program. I have to do this by defining variables on each $s - t$ path, ...
1
vote
1answer
81 views
How to get the highest score in this game?
I would like some advice in this homework question. There is a three players game, in which each player ($A, B$, and $C$) is given a $n$-length array of integer values. There are $n$ rounds in this ...
0
votes
1answer
131 views
LP formulation for minimum edge covering
Given a simple graph $G(V,E)$, what is the LP formulation for the minimum edge covering? Minimum weight edge covering would also work here. If there are none, then that is an answer too.
I took a ...
0
votes
0answers
33 views
how do i formulate this assignment optimisation problem?
Individual i, associated with organization k, are to be deployed at facility j.
Each individual has a cost cij of being deployed at j, and each facility has a minimum number of men required bj. In ...
0
votes
1answer
27 views
Encoding a binary sequence with shift in MILP
I would like to know if it's actually possible to encode a (binary) sequence with rotations in MILP/MIP.
Given a binary sequence $(0,1,1,0,0,0,0,1)$ and variables $x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7$
I ...
0
votes
0answers
23 views
Finding all k-partitions with additional constraints
The partition problem is a very well known one. To partition an integer array into k equal sum partitions.
My problem is I want to partition them in such a way that the sum of their partitions equals ...
3
votes
1answer
114 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
119 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
72 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
41 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
156 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
30 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
17 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
20 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
43 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
23 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
59 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. ...
1
vote
1answer
76 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
61 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
45 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
98 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
57 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
18 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
43 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
332 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
45 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
35 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
47 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
23 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
160 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
131 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
97 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
38 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
49 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
26 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
1answer
40 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
106 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
44 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
2answers
54 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 ...
2
votes
1answer
82 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 ...
