Questions tagged [linear-programming]
Optimization with a linear objective function, subject to linear equality and linear inequality constraints.
1
vote
1answer
12 views
Does real linear programming produce bipartite perfect matching using maxflow reduction?
Given a bipartite graph the standard reduction to max flow is with the construction similar to following diagram:
We can formulate max flow as an linear programming problem with integer variables in ...
2
votes
1answer
24 views
Linear programming IFF with equality constrain
Is it possible to write the following logical constrain in linear programming?
Let $v$ be an integer variable and $k$ an integer constant. Let $y$ be a binary variable. The logical constraint is
$y=...
1
vote
1answer
26 views
If-Then with disjunctions (OR) in Integer Linear Programming (ILP)
I have the following constraints I'm trying to model in Linear Integer Programming. I will try out diverse solvers for this later, but first I need to model the problem.
Given the integer variables: ...
1
vote
1answer
39 views
Partitioning a boolean circuit for automatic parallelization
tl;dr: I have a problem where I have a Boolean circuit and need to implement it with very specific single-thread primitives, such that SIMD computation is significantly cheaper after a threshold. I'm ...
0
votes
1answer
21 views
How to model equality in Integer Linear Programming
How to implement v=(a==b) using Linear Programming?
$$
v=
\begin{cases}
True, a=b\\
False, a≠b\\
\end{cases}
$$
Until now I tried the big M-Method.
To show a≤b:
$$a-b+Mv≤M$$
$$-a+b-Mv≤-1$$
To show ...
1
vote
1answer
19 views
Is there any advantage of using an Integer Linear Program over Backtracking in a combinatorial optimization problem?
Is there any advantage of using an Integer Linear Program over Backtracking in a combinatorial optimization problem?
I saw this Gurobi post that uses Integer Linear Programming to solve the traveling ...
0
votes
0answers
22 views
What is the most efficient way to test whether a set $X \subset \{0, 1\}^n$ and its complement $\{0, 1\}^n \setminus X$ are linearly separable?
I am interested in algorithms that have optimal running time, and ideally which are also very easy to implement. If you can also give some tips on how to implement the algorithm(s) you mention in the ...
2
votes
1answer
33 views
Logic of multiple variables in ILP
Is there a better way to represent an AND of $n$ variables together other than creating $O(n)$ new variables and constraints?
-1
votes
0answers
13 views
Swapping operation in convex programming where one variable is binary
Suppose I have two variables $x\in\{0,1\}$ and $y\in[0,1]$ and I want to have variables $u=max(x,y)$ and $v=min(x,y)$ is it possible to do this with a convex real program with no additional integer ...
0
votes
0answers
23 views
Traveling Salesman Problem with profit and time limit as ILP formulation
How to formulate the following problem?
The salesman gains a profit $p_{i}$ when visiting a city i, trip between city i and city j costs $c_{ij}$ and takes $t_{ij}$ time. The trip must not exceed a ...
1
vote
1answer
46 views
ILP representation of the number of maximal 1 sequences in a row
I am currently using an ILP to model events which occur on some input sequence from $1...n$. These events modify the input sequence in order to obtain a desired sequence. Each event can happen on some ...
0
votes
0answers
13 views
Linear Programming Formulation for Weighted Max-Cut
I am wondering if this Integer Linear Programming model I came up with as an exercise for my algorithms class is correct.
The Problem
Given a graph $G=(V, E)$, with a set of weights $W = \{w_{ij} \...
2
votes
1answer
18 views
Determine image of hypercube under linear map
Let $A$ be an $3\times N$ matrix (where $N$ is large) with nonnegative real entries. I'd like an algorithm for determining when a vector $v\in\Bbb R^3$ can be written as $Aw$ for some vector $w\in\Bbb ...
1
vote
0answers
25 views
Time complexity: Using linear programming to solve a system of linear equations
As far as I know, most direct methods for solving linear systems of equations have time copmlexity $O(n^3)$ (where $n$ is the number of variables), with the few methods being faster having huge ...
1
vote
1answer
38 views
Where's the flaw in my algorithm? (Linear program to solve NP-hard problem)
The problem (copy-pasted from this question on cs.stackexchange):
Given a connected, directed graph $G=(V,E)$, vertices $s,t \in V$ and a coloring, s.t. $s$ and $t$ are black and all other vertices ...
2
votes
1answer
48 views
Approximation algorithm for weighted set cover, using multiplicative weights
It is known that the problem of fractional set cover
can be rephrased as a linear programming problem and be approximated using the multiplicative weights method, for instance this lecture note shows ...
0
votes
1answer
27 views
Sanity check about a linear programming problem
given the linear program:
minimize $x+y$
subject to,
$ax+by \leq 1$
$x,y \geq 0$
I need to find real numbers $a,b \in \mathbb{R}$ such that the program (a) is infeasible, (b) is unbounded, and (c)...
0
votes
1answer
49 views
Minimal paths as solution of a linear program of a special network flow
Let $G= (V,E)$ be a given directed weighted graph, and $s,t$ two specified nodes, so that there is no negative cycle reachable from $s$, and $t$ is reachable from $s$.
We're looking for the shortest ...
0
votes
0answers
26 views
Handling $AND$ and $OR$ cases in MILP?
Suppose I want to have an integer program for handling the cases
$x_1>1\wedge x_2>1\wedge x_3>1\wedge\dots\wedge x_n>1\iff\delta=1$
$x_1>1\vee x_2>1\vee x_3>1\vee\dots\vee x_n&...
0
votes
0answers
11 views
Please help to convert conditional expressions to linear [duplicate]
I have an expression:
if A≤X1-X2≤B, than Y=1, Otherwise Y=0
where A and B are constants, and X1, X2 are variables.
Please help to convert this to linear expressions.
1
vote
0answers
30 views
general question about linear algebra [closed]
have new discoveries been made in linear algebra since the dawn of AI or was it all "laid out" for the computer scientists by former mathematicians?
1
vote
1answer
24 views
Check a variable within a range with a binary variable [closed]
I have a value, a, it can be any value from 0 to 1. In an integer linear program, how can I formulate a constraint that uses a binary variable, y, to determine whether a is within a range of 0 and 1 ...
2
votes
1answer
42 views
Boolean variable that captures whether an inequality holds
I have an integer linear program with variables $x_1,\dots,x_n$. I have an inequality $a_1 x_1 + \dots + a_n x_n \ge b$ that I care about; it may or may or not hold.
I want to introduce a boolean ...
1
vote
0answers
56 views
“Greater than 0” condition in integer linear program with a binary variable [duplicate]
How can one model the following condition in an integer linear program?
$$
y = \begin{cases} 1 & \text{if } x > 0\\ 0 & \text{otherwise}\end{cases}
$$
Where $y \in \{0,1\}$ and $x \in \...
1
vote
0answers
50 views
Confusion about the geometric interpretation of the simplex method for linear programming
In Section 7.6.2 of the textbook "Algorithms" by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani, the authors provide a geometric interpretation of the two main tasks of each iteration of ...
1
vote
1answer
47 views
What is the intuition behind the way of reading off a dual optimal solution from simplex primal tabular in CLRS?
Section 29.4 "Duality" of CLRS (3rd Edition) describes the way of reading off an optimal dual solution from the last slack form of the primal as follows:
Suppose that the last slack form of the ...
4
votes
1answer
132 views
Maximum matching using linear programming
In a bipartite graph $G = (V,E)$, there is a neat algorithm for finding a maximum matching (or even a maximum-weight matching) using linear programming. It is explained here. The first step is to ...
2
votes
1answer
42 views
How to efficiently specify a MILP constraint with nested AND and ORs
Let's say I want to set x1=1 if (x2=1 AND x3=1 AND x4=1) or (x5=1 and x6=1) or (x7=1) else x1=0
All of the xs are binary ...
0
votes
0answers
16 views
When does total unimodularity implies integrality of solutions?
In Gartner & Matousek's book on linear programming, they prove the following lemma (Lemma 8.2.4, page 145):
Let us consider a linear program with $n$ nonnegative variables and $m$ inequalities ...
2
votes
1answer
73 views
Using LP to prove the max matching - min cover theorem
Konig's theorem says that, in a bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover. This theorem has several proofs; I would like to know if the following ...
2
votes
0answers
31 views
Relaxations for MILP with logical constraints
I have an LP with a (non-fixed) number of logical constraints in the form of $X_1 \rightarrow X_2$ (where $X_1$ and $X_2$ are linear functions inequalities of the $n$ input variables). To express ...
1
vote
0answers
16 views
Given a set of solutions, find an IP formulation with the same solution set
Input:
A list of integer variables $x_1, ..., x_n$.
A finite set of feasible solutions $S \subset \mathbb{Z}^n$.
Task:
Find an integer linear program (IP) on the integer variables $x_1,...,x_n$ ...
1
vote
0answers
37 views
7
votes
2answers
147 views
Reducing linear programming to positive linear programming
Suppose we have an oracle that solves problems of the form
\begin{align*}
\text{maximize} ~~ & c^T x
\\
\text{subject to} ~~ & A x = b, x\geq 0
\end{align*}
when $c\geq 0$ (all coefficients ...
0
votes
0answers
30 views
Branch and bound Dual Gap
Let's suppose we want to solve the knapsack problem using the Branch and Bound algorithm.
I know that the algorithm ends when the optimality gap is = 0. However i have not understood how the dual ...
0
votes
0answers
16 views
How to formulate initial costs in linear programming?
Consider this example problem:
Suppose the cost for setting up a factory to generate a pencil is 1000 and to generate a pen is 2000. The profit for each pencil is 10 and the profit for each pen is 12....
0
votes
1answer
26 views
How to formulate constraints in zero-one linear programming
There is a factory which produces 5 types of ice cream. If the $i_{th}$ ice cream is produced then $b_i=1$ otherwise $b_i=0$
How can I express the following constraints:
The simultaneous production ...
0
votes
1answer
31 views
Complexity of linear programming with restricted quadratic constraints
A problem instance is a linear program with the following kind of quadratic inequalities allowed: For some of the variables $x_i$, there is a variable $s_i$ (intuitively for approximating $x_i^2$, and ...
0
votes
0answers
19 views
Reducing weighted linear threshold gate to unweighted one
Reading "On the power of threshold circuits with small weights" by Siu and Bruck I have faced several problems understanding how unweighted linear threshold element can be built efficiently from the ...
1
vote
0answers
43 views
Big M method for continuous variables
Is there any way to model the big M method for continuous variables?
Something similar to this but $B, C \in \mathbb{R}_{\geq 0}$ and $A\in\{0,1\}$.
Due to the precision problem, when the $B$ and $C$ ...
1
vote
0answers
42 views
(M)ILP overlap of two intervals
I got an ILP Model where $c_i$ represents the starting time for a visit$_i$.
$c_i$ is already constraint by a number of constraints, one is $c_i > 0$.
I have now outside of my model 0 or multiple ...
2
votes
1answer
126 views
What is the right term/theory for prediction of Binary Variables based upon their continuous value?
I am working with a linear programming problem in which we have around 3500 binary variables.
Usually IBM's Cplex takes around 72 hours to get an objective with a gap of around 15-20% with best ...
1
vote
1answer
120 views
LP Relaxation of Maximum Coverage Problem
So I know from some research I've done that the OPT-IP <= OPT-LP for the maximum coverage problem, however I'm having some difficulty following the explanations I find. Does an example exist where ...
0
votes
0answers
10 views
How to understand the separation phrase for generalized subtour constraints?
Suppose the constraints of our integer programming model consist of two parts:
the polynomial-size formulations, that have a size (number of variables and constraints) which is polynomial w.r.t. the ...
0
votes
1answer
85 views
How to write an if then logical constraint given part of the input related to a decision variable?
I am trying to solve an assignment problem-like from a bi-objective persepctive where I have a marketplace of vendors proposing different machines with different types and specs. The goal is to select ...
2
votes
3answers
106 views
Need Help Understanding MST Cutset Formulation
I just started learning about linear programming in my class, and I'm having some trouble understanding the MST Formulation Integer Linear Programming (Cutset Formulation).
This is the definition:
...
0
votes
0answers
14 views
LIP - Minimum Spanning Tree Cutset Formulation [duplicate]
I just started learning about linear programming in my class, and I'm having some trouble understanding the MST Formulation Integer Linear Programming (Cutset Formulation).
This is the definition:
$...
1
vote
0answers
126 views
maximizing absolute value in linear programming
I know that similar questions have been answered several times, and based on the answers, I attempted a solution to my problem. But I simply do not get the right results. The problem is as follows. I ...
2
votes
1answer
22 views
Positioning items to maximize separation
Say we want to place n items on the real line. Let us denote the position of item i by $p_i$. We have interval constraints on the position $p_i$, i.e. we are given $l_i, r_i$ such that $l_i \le p_i \...
1
vote
0answers
12 views
Sparse feasible solution $|x|_0\le k$ for system of linear inequalities $A x \le b$
Suppose the set of linear inequalities $Ax\le b$, in which $A\in\mathbb{R}^{m\times n},x,b\in\mathbb{R}^n$ is given. Is it possible to determine in polynomial time with regard to $m$ and $n$ if there ...
