Questions tagged [linear-programming]
Questions on linear programming, the optimization of a linear function subject to linear constraints.
4,425
questions
0
votes
0answers
3 views
Eliminating a free variable in a linear programming problem
Consider the following linear model.
\begin{align}
\min&\quad z = c^{t}x\\
\mathrm{s.t.}&\quad Ax = b\\
&\quad e^{t} x = 1 \\
&\quad x_{i}\geqslant0 \quad \forall i \in \{1,...,n-1\}
\...
1
vote
1answer
36 views
Why do we need specific linear programming methods now?
I've recently studied different methods of solving linear programming (LP) problems, like simplex method, Dantzig–Wolfe decomposition, Kornai–Liptak decomposition. I suppose all these methods were a ...
0
votes
0answers
25 views
Integer LP - Connected Components [duplicate]
Say we had a network $G(N,E)$ and I wanted to formulate a binary integer LP to find all connected components of the network.
I know that we can define binary variables as $x_{i,j}=\begin{cases}
1&...
-2
votes
1answer
37 views
Dimension of the vector space and kernel set [closed]
if $V$ is finite dimension vector space and if $F : V → V$ is linear map if $\text{Im}(F) ⊆ \ker(F)$ then $\text{dim(im(F))} ≤ 1/2\text{dim(V)}$
0
votes
0answers
15 views
How can I compute the dual function of the following problem?
I'm trying to find the dual linear program of the following linear program
$$\text{Min} \, a^{T} x$$
$$ s.t. Bx\le b $$
$$Dx=d$$
where x, b, d, and a are vectors and B, D are matrices.
According ...
0
votes
0answers
48 views
Does the argmin operator commute with the sum operator?
Under what conditions on $f$ is the following true?
$$\arg\min_{\alpha_1,\ldots,\alpha_d\in\mathbb{R}^d}\sum_{i=1}^d f(x,\alpha_i)=\{ \arg\min_{\alpha_i\in\mathbb{R}} f(x,\alpha_i)\}_{i=1}^d=\{\hat\...
1
vote
0answers
11 views
Why do the penalties of the Vogel method work?
Vogel's method selects the corresponding variable through a penalty. There is a penalty for each row and column and is the subtraction between the two lowest costs (in absolute value).
We must select ...
2
votes
1answer
189 views
Integer Linear Programming: Connected Nodes
Given a network $G = (V, E)$, how do I formulate a binary integer linear program to find all connected components of general G?
Since it's binary, I know that $x_{ij} \in \{0,1\}$, $0$ if node $i$ and ...
-1
votes
0answers
20 views
Constraining valid relationships between two indices [closed]
If I have two sets, $I$ and $J$ with elements $i \in I, j \in J$, and I have continuous variables $X_{ij}$. How can I generically write that $X_{ij}$ exist only for certain combinations of of $i$ and ...
0
votes
1answer
47 views
Almost symmetric infinite (linear) program
Consider a linear optimization program like the following
$\max \frac{\sum_{i=1}^{T} x_i}{T}$
s.t. $a x_i+bx_{i+1}\leq 1, \forall i\geq 1, x_i\geq 0$
Assume that we take $T\rightarrow \infty$. Say ...
0
votes
0answers
30 views
Is there a way to minimize the standard deviation in linear programming
Here is the scenario:
There are n boxes with $C_{a}$ of capacity at the beginning of each box before assigning.
I want to fit x parcels into the boxes, letting the capacity left for each boxes are as ...
0
votes
0answers
18 views
How can I solve the following problem using the complementary slackness property?
Prove that for every matrix $A \in \mathbb{R}^{m \times n}$ exactly one of the following statements is true:
$\exists x \in \mathbb{R}^n : Ax > 0$
$\exists y \in \mathbb{R}^m : A^T y = 0 \wedge y \...
1
vote
1answer
37 views
LP with n free variables can be replaced by n + 1 nonnegative variables
I need to prove that if an LP has n free variables, that these n free variables can be replaced by n + 1 nonnegative variables.
If an LP has one free variable $x_1$ this is clear to me, write $x_1 = ...
0
votes
0answers
10 views
Prove or disprove this statement about Basic Feasible Solution.
Prove or disprove:
In every linear programming problem in a standard form, the basic feasible solution that gives the highest value of the object function is the optimal solution.
My thoughts:
I ...
0
votes
0answers
19 views
(LP Duality) What is the dual of this linear-programming
My question is pretty simple and I'm just asking because I'm confused. I don't know what should I do if a variable is not present in the constraints.
What is the dual of this? (note that we have both ...
2
votes
0answers
10 views
Show linear program in canonical form that may be bounded doesn't necessarily contain an optimal solution which is a vertex. [closed]
I'm trying to show that linear program in canonical form that may be bounded doesn't necessarily contain an optimal solution which is a vertex.
I'm searching a detailed/specific Linear program in ...
4
votes
1answer
111 views
Optimum of linear program from graph
Given a connected (undirected) graph $G$ with vertex set $V$ of size at least $2$, we are allowed to put a real number $x_v$ on each $v\in V$. The constraint is that, for any $W\subseteq V$ such that ...
1
vote
1answer
25 views
How to find the range of the parameters using the basic feasible solutions I have found?
Given the problem:
maximize $a_1x_1+a_2x_2$
s.t. $2x_1-x_2\ge 2$
$x_1+x_2\le 4$
$x_1,x_2\ge 0$
a) Given that $a_1=1,a_2=2$, solve the problem graphically.
b) Find all the basic feasible ...
2
votes
1answer
19 views
Resources to learn about modeling within the scope of Linear/Integer programming?
I'm currently taking a course in OR, and I'm facing some major difficulties trying to formulate my LP/IP problems. I understand most of the topics just fine, but I just get lost trying to formulate ...
2
votes
1answer
60 views
Linear programming: Modelling a problem
Exercise. A forest is in flames and the government is planning a firefighter operation. The fire is of small dimensions and is progressing slowly and it must be extinct after $3$ hours of operations. ...
0
votes
0answers
10 views
In a standard-form linear optimization problem, is $b_{\perp} \in null(A^*)$?
I was trying to show that if we have a non-degenerate basic feasible solution to the primal, that complementary slackness implies there is a unique solution for the dual vector. I understand there are ...
0
votes
0answers
25 views
I've followed the simplex method and have found out the MaxZ. How to proceed ahead? How do I make (x1,x2) correspond to dual variables?
Max $z = 2x_1 + 4x_2 + 4x_3 - 3x_4$
Subject to $x_1 + x_2 + x_3 = 4, x_1 + 4x_2 + x_4 = 8$
$x_1, x_2, x_3, x_4 \geq 0$ Use the dual problem to verify the basic solution $x_1, x_2$ is not optimal.
...
0
votes
0answers
10 views
Linear Program Phase 1 first pivot doesn't provide a starting dictionary
I have the LP and need to solve it using the two phase simplex algorithm, not the dual two phase;
...
0
votes
1answer
17 views
Clustering data using mixed integer linear programming
I am trying to understand if it is possible to use mixed integer linear programming (MILP) in order to perform a basic clustering operation to a dataset $D$. I know there exists standard algorithms ...
2
votes
1answer
40 views
Transforming a Linear Program into the equality constrained standard form.
[Transform LP to equality constrained standard form][1]
THE PROBLEM: [1]: https://i.stack.imgur.com/JKUlj.png
Rather than using the standard LP form we saw in class, some prefer using a form where ...
0
votes
0answers
10 views
Two stage Stochastic LP with upper and lower bound
I need to formulate a problem with two stage stochastic LP and the following conditions:
I don't have multi scenarios for the second stage of the problem, but instead, I know the lower-bound and ...
0
votes
1answer
43 views
How do I formulate this linear programming problem? (especially the second restriction)
A factory creates different types of oils and mixes them together. There exists two types of vegetarian oils (veg1,veg2) and three types of non-vegetarian oils (oil1,oil2,oil3), the price of each oil (...
0
votes
1answer
16 views
Linear Programming Constraint Percentages
I have a homework about linear programming. I have to formulate the constraint of the following:
A company produces two products, Deluxe and Special. The company decided that the Special must ...
2
votes
1answer
57 views
Turning a piecewise affine optimization problem into an equivalent linear program
$$\begin{array}{ll} \underset{x \in \mathbb{R}^4}{\text{minimize}} & x_1 + 6 x_2 - \min\{10x_3, 5x_4\} + \left| \displaystyle\sum_{i=1}^{4}x_i \right| \\ \text{subject to} & \displaystyle\sum_{...
2
votes
1answer
29 views
Is this how this question supposed to be solved? (Writing a system of constraints that represents this connection between variables).
Given that $x,y,z,w,v\in \{0,1\}$. The connection between the variable is given by:
$\max\{\min\{x,y\},z,v\}=w$.
Write a system of linear constraints that represents this connection.
My Work:
Let $...
0
votes
0answers
37 views
Formulating problem in CVX
Crossposted on Stack Overflow
I am new to CVX and I have to solve the following optimization problem.
I have written the code for it and also changed the equalities to make it convex but I think ...
0
votes
0answers
29 views
How do I set up the initial simplex tableau?
Maximize: Z = x1 + 3x3
Subject to:
x1 + 2x2 + 7x3 = 4
x1 + 3x2 + x3 = 5
x1, x2, x3 $\ge$ 0
I am confused on how to put it into a simplex tableau because the constraints are already equations.
I know ...
1
vote
1answer
32 views
Linear Programming - Job Scheduling Domain Mapping To Binary Decisions
I am trying to maximise machine profit subject to a repair plan (job schedule), but cannot seem to map between the integer domain from the job schedule to the binary domain for the revenue model in ...
1
vote
0answers
20 views
Basic feasible solutions with a continuum of variables
Consider the following linear program, where $x$ is a vector of $n$ variables, $c$ is a constant vector of size $n$, $A$ is an $m\times n$ matrix, and $b$ is a constant vector of size $m$:
$$
\text{...
-1
votes
0answers
19 views
how to obtain a tableau with lexicographically positive rows
Suppose that a feasible tableau is available. Show how to obtain
a tableau with lexicographically positive rows. Hint: Permute the columns.
-3
votes
0answers
39 views
Computing basic solutions
Consider the following LP in standard form.
Minimize $4x_1 + 3x_2 −2x_3 + x_4$
Subject to: $x_1 + x_2 + x_3 + x_4 = 8$
$2x_1 −x_2 + x_3 −2x_4 = 4$
$x_1,x_2,x_3,x_4 ≥0$
For each choice of a basic/...
0
votes
1answer
21 views
infinite set of constraints involving vector norms
Suppose that we are given $$\overline{a} \in \mathbb{R}^2$$ and let $$D=\{u \in \mathbb{R}^2 : ||u||_1 \leq 1 \}$$ Let $\beta$ be some fixed constant and consider $$a^Tx \leq \beta, (a-\overline{a} \...
0
votes
0answers
14 views
Help in expressing in McCormick Envelope
The statement which I want to express in McCormick envelope is
$\sum_ix_iM_{ij}\leq F_j$ for all $j$
The initial McCormick envelope I wrote where $w_{ij}=x_iM_{ij}$, is:
$\sum_iw_{ij}\leq F_j$ for all ...
0
votes
0answers
32 views
Representation of polyhedra
Suppose that $P = \{ x \in \mathbb{R}^n| Ax \leq b \}$ is an non-empty polyhedron and rank$(A) = n$(i.e. $P$ has at least one extreme point). Let $S$ be the set of extreme points of $P$ and $Q = conv(...
0
votes
0answers
16 views
Question regarding Primal simplex method
Hi quick question regarding the primal simplex method. How do you use the primal simplex method when you have to start with a specific basis? I'll give a quick example of what I mean. If we wish to ...
0
votes
1answer
38 views
Maximise $\sum_{i=1}^nf_i\omega_i$ over $\omega_i$ where $\sum_{i=1}^nf_i=\sum_{i=1}^n\omega_i=1$ and $\omega_i,f_i\geq0$
Let $i\in 1,\dots n$.
Let $f_i\geq0$ be real numbers such that $\sum_{i=1}^nf_i=1$. Then what is the maximum of $B\left(\omega_i\right)=\sum_{i=1}^nf_i\omega_i$ over $\omega_i$ such that $\omega_i\...
0
votes
1answer
18 views
Name of Particular Constrained Optimization Problem
I am writing to ask if any of you know what is the name in the research literature of a particular constrained optimization problem I am facing. I would like to find a general name so that I can ...
0
votes
1answer
44 views
Linear Optimization with Ratio of Constraint Variables
I found a similar question at https://math.stackexchange.com/q/413317 but I could not comprehend the explanation. I am required to optimize the sale for the following question:
There are two kinds of ...
4
votes
0answers
467 views
Transforming inequality constraints into equality constraints
Intro: Suppose we want to find whether the feasibility region of this linear programming is non-empty:
$$
(1) \quad
Ax \leq b\\
\quad \quad C x = 0
$$
Suppose that verifying the feasibility of (1) is ...
1
vote
2answers
32 views
Mixed Integer Linear Programming problem maximizing projects but they can share resources
I need help with this optimization problem. I'm sharing a simplified version for easier discussion.
For example, I have projects $x_i$ where $i=1,2,...5$.
Each project has factors $a_i, b_i, c_i$ with ...
1
vote
1answer
29 views
Hungarian algorithm / assignment problem with cost function depending on resultant matching
The standard Hungarian algorithm solves the problem of assigning n workers to n jobs with a given cost function.
In my variant, the cost function depends on the final matching produced by the ...
0
votes
1answer
34 views
Is this a max-flow min-cut problem? [Reference needed!]
I've been searching for a while now, but did not succeed in finding whether the problem I have is actually a max-flow min-cut problem or it can be deduced to it, i.e. the algorithms that are used to ...
0
votes
0answers
58 views
vector subset problem for linear approximation
Let $V = \{v_1,v_2,..,v_n\}$ be a set of vectors in $\mathbb{R}^n$, $t$ be the target vector in $\mathbb{R}^n$ and a natural number $m > 1$.
Properties about $V$ and $t$:
$cos\phi(t,v_i) \geq \...
5
votes
1answer
45 views
Are packing (i.e., independence) numbers arbitrarily smaller than fractional packing (i.e., Rosenfeld) numbers?
Take a graph $G=(V,E)$.
One of the equivalent ways of defining its independence number (also known as $1$-packing number) is
$$\alpha = \max\left\{ \sum_{v\in V}f(v) : \forall v\in V, f(v) \in \{0,1\}\...
1
vote
1answer
31 views
Maximum of Lagrange function
I am trying to understand if the following holds
$$\max_{\lambda \succeq 0} L(x, \lambda) =\max_{\lambda \succeq 0} \left( f_0(x) + \sum_{i=1}^m \lambda_i f_i (x)\right) =\begin{cases}
f_0(x), \quad ...
