Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5
8