Questions tagged [linear-programming]

Questions on linear programming, the optimization of a linear function subject to linear constraints.

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

1
2 3 4 5
89