Questions tagged [linear-programming]
Optimization with a linear objective function, subject to linear equality and linear inequality constraints.
289
questions
-1
votes
1answer
77 views
Help with designing the following algorithm to prepare chocolate
Mr X is a spy. He has recently found some very important information.
Now he has to secretly send it to his boss. He plans to hide the
information in a chocolate bar which can be later exported
...
0
votes
1answer
36 views
Integer Linear programming formulation if then condition
I want to create constraints such that I can implement the following condition:
Let A be an integer variable >= 0 with an upper bound of 12
I want to introduce the following variable B also an ...
6
votes
0answers
88 views
Time complexity of linear programming with small number of variables
I have a linear program with $n$ variables, $m$ constraints and $O(nm)$ bit total length (the constraint matrix contains only zeros and ones). I am interested in finding a polynomial time algorithm ...
0
votes
1answer
20 views
Bin Packing variant
I am currently struggling with a bin packing variant, where we have fuel and compartments of a tank truck. Some industry constraints apply, but the whole picture is that you must fit the total volume ...
2
votes
0answers
23 views
LP - Dual variable is zero implies primal constraint unnecessary?
Say I have a primal program P with n variables and c constraints.
Let's say that I have an optimal solution for the dual program D, in which the y1, the variable related to the first constraint in P, ...
0
votes
2answers
41 views
LP - given m constraints for 2 variables find maximal radius of circle
Given $m$ constraints for 2 variables $x_1,x_2$ :
$d_ix_1 + e_ix_2 \leq b_i$ for $i = 1,...m$
need to create a linear program that finds the maximal radius of a circle such that all the points ...
3
votes
2answers
162 views
Examples of Analysis of Branch and Bound Method
I am solving a graph problem, which can be formulated as an integer programme. Based on computer experiments, it seems that the branch and bound method works well. I would like to analyse the running ...
0
votes
1answer
21 views
Writing a linear program to model balanced bin packing
Say we want to write a (MI)LP to model the following problem:
Find a parking plan for a set of cars $K=\{1, ..., k\}$ with lengths
$\lambda_i$. Parking is organised in lanes $P=\{1, ..., p\}$. ...
2
votes
1answer
66 views
Integrality gap and LP-rounding
I have a doubt about integrality gap.
If I know that there is no integrality gap for a given problem, i.e.:
$$\frac{\mathrm{OPT}(\mathrm{ILP})}{\mathrm{OPT}(\mathrm{LP})} = 1 \text{ (right?)},$$
...
2
votes
2answers
52 views
Linear programming: reduce a contstraint that includes minimun
I have an almost linear programme. However one of the constraints has a form $z = min(x,y)$ (all the other things are linear in the model). Is there a way to substitute this with something (or ...
0
votes
0answers
74 views
Computing an optimal integer assignment given an optimal LP-solution
I modeled an ILP where I have a set of outfits and a set of friends with , all these friends should take one outfit with the lowest effort , considering the fact that these outfits differ in size, ...
1
vote
0answers
17 views
Why maximum-matching algorithm falls into the category of fill-reducing algorithms?
My understanding is that "maximum matching" (or "maximum transversal") are algorithms to pre-order matrix to increase the numerical stability. In Timothy Davis' book Direct Methods for Sparse Linear ...
2
votes
1answer
36 views
Determine aproximation factor in a greedy algorithm
Suppose we have n food dishes associated to a cost c, and we have i guests such that each one of them has a certain number of preferences.
We want to choose a menu such that we minimize the cost and ...
2
votes
3answers
161 views
Linear programming maximizes the minimum distance problem
I have a problem with creating an equation for linear programming solver.
Company wants to open stores in k cities. For the purpose of even coverage of the entire ...
0
votes
0answers
18 views
Formulate the mathematical model to find the optimal solution
A, B, C and D are standing on the east bank of a river and wish to cross to the west side using a boat. The boat can hold at most two people at a time. A, being the most athletic, can row across the ...
1
vote
0answers
61 views
Can this graph-ordering problem be solved with LP?
I have a modelling problem that I am trying to solve with LP. (More specifically, in Python using PuLP or Pyomo). I am not terribly knowledgeable in this area and have been struggling to find the ...
2
votes
0answers
35 views
Finding a non negative combination of integers that adds up to a certain number [duplicate]
I have a set of positive numbers: ${n_1,n_2,...n_k}$ s.t. $n_1>n_2>\dots >n_k$.
I want to find an array of non-negative integers $c_1,c_2,\dots,c_k$ such that
$$n_1c_1 + n_2c_2 + \dots + ...
2
votes
1answer
87 views
Minimum Clique Cover - Mixed Integer Programming
I have a general (undirected) graph with a set of nodes, a set of edges, and a weight for each edge. I want to find a minimum clique cover of the vertices of the graph, that is, a partition of the ...
0
votes
0answers
25 views
Knapsack Problem Via Column Generation
If I were to solve the linear relaxation of a knapsack problem via column generation how could I model the master problem and pricing subproblem? Given a set $N$ of items with value $v_{i}$ and weight ...
3
votes
2answers
52 views
On the hardness of satisfying K number of linear constraints
Background: Normally in linear programing we have some objective function
$$\text{maximize}\sum_{i = 1}^n a_i x_i $$
$$\text{subject to} \sum_{i =1}^n b_{ji}x_i \leq c_j \text{ for all } 1 \leq j \leq ...
1
vote
0answers
36 views
About Steiner tree problem in graphs
In the
paper (p. 3)
and the
slides
presents the formulation of the Steiner problem on graphs
via so called Steiner cuts.
But according to the definition, the number of Steiner cuts and so the ...
1
vote
0answers
20 views
Minimal subset of rows that generate smaller polyhedron
Given a matrix $[A|B]$ I want to find a minimal matrix $[A'|B'] \subseteq [A|B]$ (i.e. the rows in $[A'|B']$ are also in $[A|B]$) such that $A'x < B' \Rightarrow Ax < B$.
Geometrically, I want ...
0
votes
0answers
9 views
Linear Programming with constrained sum of rows and sum of columns
Is there a structure to the solution of the following linear program?
$\min_{x_{ij} } \sum_{i,j} x_{ij} \mu_{ij}$
$s.t. \forall j, \sum_{i} x_{ij} = \beta_j,$ row sum
$\forall i, \sum_{j} x_{ij} D_{...
1
vote
1answer
48 views
Can an optimization algorithm be “universal”?
I am wondering if a Bayesian Optimization framework (e.g. Google's Vizier) can be used in lieu of a traditional solver like Gurobi or CPLEX.
In trying to answer this question, I realized that I don'...
3
votes
1answer
72 views
Linear programs with strict inequalities and supremum objectives
Linear programming can solve only problems with weak inequalities, such as "maximize $c x$ such that $A x \leq b$". This makes sense, since problems with strict inequality often do not have a solution....
0
votes
1answer
60 views
“Greater than AND smaller than” condition in integer linear program with a binary variable
I found this related question, but that's not quite it
Is it possible to model this with integer programming:
$$A = \begin{cases} 1 & \text{if } B \geq C \geq D \\ 0 & \text{otherwise}\end{...
0
votes
0answers
14 views
Given a primal LP p, and another LP d, how can i formally prove that d is the dual problem of p?
Given a primal LP p, and another LP d, how can i formally prove that d is the dual problem of p?
Specifically, i'm talking about the shortest s-t path:
where:
And the dual LP:
0
votes
0answers
7 views
How to input random values (constraints) of any variables in case of formulating Linear Programming Problem?
Suppose,
Min 2x+3y
Subject to, x=2,x=5,x=7
y=5, y=9
is a linear program. Where x holds the values 2 or 5 or 7 and y holds the values 5 or 9. Then what should the correct ...
0
votes
0answers
22 views
How is ellipsoid method a polynomial-time algorithm for LP?
I have always thought that the ellipsoid algorithm is an algorithm which can be used to solve LP in polynomial-time. However, what confuses me is the dependence on the ratio of volumes of the balls (...
0
votes
0answers
20 views
Creating a waste-optimizing algortihm for cutting a 1d block
I have a one-dimensional block of material. I run an analysis that divides the material into usable and unusable regions.
In a manufacturing process, said material is cut and the unusable regions ...
1
vote
1answer
30 views
Relaxation of the knapsack constraints
A set $\mathcal{A}$ is the relaxation of another set $\mathcal{B}$, if $\mathcal{B} \subseteq \mathcal{A}$.
I have a set of points defined as the knapsack constraint
$$
\mathcal{X} = \{x \in \...
0
votes
0answers
24 views
How can I quickly find the dual of a linear program?
In linear programming, the standard maximum form of a program (which we will call the "primal") is
max $c^{tr}x$ subject to
$Ax \le b$, $x \ge 0$
and the standard minimum form, the dual, is
...
1
vote
0answers
32 views
Solving a linear program with simplex algorithm, matrix not full rank
I need to solve the following LP
$$\begin{array}{ll} \text{minimize} & c^T x\\ \text{subject to} & A x = b\end{array}$$
where
$$A = \begin{bmatrix} 1 & 3 &1&0&0 \\ -2&...
4
votes
1answer
125 views
Mistake in a proof of termination phase of Simplex algorithm in CLRS?
There is a pseudo-code for Simplex algorithm in CLRS:
The proof consists from three-part loop invariant:
Proof We use the following three-part loop invariant:
At the start of each iteration ...
1
vote
1answer
29 views
Linear programing, objective function. variable depending on the sign of another variable
I have the variable Si. How to express a variable Di in LP that satisfies:
Di=100*Si if Si>=0
...
3
votes
0answers
235 views
Minimum clique cover
How can the problem of finding the minimal clique cover be solved using linear/integer programming in a reasonable amount of time?
Having an undirected graph, I am trying to partition all its ...
2
votes
0answers
49 views
Goemans' Extended Formulation of the Permutahedron And Comparator Networks that are not Sorting Networks
I am interested in using Michel Goemans' extended formulation first developed for the permutahedron to study comparator networks that are not sorting networks. In his paper "Smallest Compact ...
1
vote
0answers
42 views
An LP with two covering constraints - how to round
I came across an LP with two covering problems, and I wonder how to
find a good approximation. For the relevant part of the LP: We have
a set $E$ , for each $e\in E$ we have a corresponding set $Y_{e}\...
4
votes
2answers
106 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
35 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
101 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
48 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
61 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
27 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 ...
1
vote
1answer
43 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
50 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?
0
votes
0answers
49 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
56 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
30 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
27 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 ...
