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
0 answers
9 views

What does the complementary slackness theorem say intuitively/in layman's terms?

In layman's terms: weak duality theorem states that all feasible solutions to the primal LP is less than or equal to all feasible solutions to the dual LP. strong duality theorem states that the ...
user avatar
0 votes
0 answers
27 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 ...
user avatar
0 votes
0 answers
10 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 ...
user avatar
1 vote
0 answers
29 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 ...
user avatar
  • 2,220
2 votes
1 answer
26 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 ...
user avatar
1 vote
2 answers
471 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. ...
user avatar
  • 113
1 vote
1 answer
18 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 ...
user avatar
  • 13
2 votes
1 answer
26 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 ...
user avatar
  • 123
1 vote
0 answers
25 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 ...
user avatar
1 vote
0 answers
11 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 ...
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 ...
user avatar
0 votes
1 answer
25 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 ...
user avatar
  • 141k
1 vote
1 answer
27 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 ...
user avatar
  • 141
0 votes
0 answers
16 views

Convert Linear Program to Network Flow

Given the following network flow problem: $$max \sum_{p \in P}x_p$$ $$s.t. \sum_{x_p \in c_e} x_p \leq c_e, \forall e\in E$$ $$x_p \geq0$$ $P$: All paths from a start node $s$ to end node $t$ $E$: Set ...
user avatar
  • 141
1 vote
1 answer
23 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,...
user avatar
  • 13
0 votes
1 answer
86 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 ...
user avatar
1 vote
1 answer
20 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 ...
user avatar
0 votes
0 answers
39 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, ..., ...
user avatar
0 votes
0 answers
22 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 ...
user avatar
  • 11
1 vote
0 answers
81 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)$ ...
user avatar
1 vote
1 answer
25 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 \...
user avatar
  • 361
0 votes
1 answer
235 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 ...
user avatar
1 vote
0 answers
51 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 ...
user avatar
  • 11
10 votes
0 answers
67 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 ...
user avatar
1 vote
0 answers
32 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, ...
user avatar
1 vote
1 answer
112 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 ...
user avatar
  • 115
0 votes
1 answer
253 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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
0 votes
1 answer
28 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 ...
user avatar
  • 1
0 votes
0 answers
25 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 ...
user avatar
3 votes
1 answer
121 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 ...
user avatar
1 vote
1 answer
130 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 ...
user avatar
  • 1
1 vote
1 answer
84 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 ...
user avatar
  • 1
0 votes
0 answers
43 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 ...
user avatar
1 vote
0 answers
169 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 $...
user avatar
  • 317
0 votes
0 answers
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_{...
user avatar
  • 1
0 votes
1 answer
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 ...
user avatar
  • 3
1 vote
1 answer
44 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 ...
user avatar
0 votes
1 answer
74 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 ...
user avatar
0 votes
2 answers
106 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. ...
user avatar
1 vote
1 answer
91 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 ...
user avatar
  • 111
2 votes
1 answer
123 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}$ ...
user avatar
0 votes
1 answer
48 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 ...
user avatar
1 vote
2 answers
119 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, ...
user avatar
1 vote
1 answer
61 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 ...
user avatar
2 votes
1 answer
48 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 ...
user avatar
  • 587
1 vote
1 answer
688 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 ...
user avatar
0 votes
0 answers
81 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 ...
user avatar
5 votes
0 answers
67 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 ...
user avatar
  • 51
0 votes
1 answer
24 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 ...
user avatar

1
2 3 4 5
8