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
1 answer
29 views

Why it is not possible for both primal and dual LP to be unbounded?

I already read this post and its answers and I am still not satisfied. I want to know how to use weak duality to explain why it is not possible for both primal and dual LP to be unbounded. Here is one ...
John Davies's user avatar
0 votes
2 answers
56 views

Help with reformulating linear programming with rounding numbers

I have the following problem, abstracting away a few details from a real-world application, that I want to solve with linear programming (or any other mathematical optimization with constraints, ...
qalis's user avatar
  • 157
0 votes
0 answers
42 views

Given these constraints is class scheduling forecasting impossible? [closed]

We are trying to model/simulate and optimize class scheduling for a trade school. I am hoping for some direction to solve the puzzle described below. Context We have, say, 1000 active apprentices at ...
Evan's user avatar
  • 1
-3 votes
2 answers
84 views

Linear Programming: Minimize deviation and evenly maximize decisive variable [closed]

I came across linear programming while trying to find a solution to a problem. I didn't use LP before so pardon if it is naive question. I hope this forum can help. There are n tasks (x1, x2 .., xn) ...
R. V.'s user avatar
  • 7
0 votes
0 answers
60 views

Variation of Farkas’ Lemma

Given matrices $A \in \mathbb{R}^{m \times n}$, $B \in \mathbb{R}^{p \times n}$, and $H \in \mathbb{R}^{q \times n}$, I want to prove that exactly one of the following 2 systems has a solution: $Ax &...
엄익훈's user avatar
1 vote
1 answer
34 views

Task Assignment Problem using MILP (tasks >> agents)

I have a general assignment problem that assigns a set of payload tasks $T$ to a set of workers $A$, where $|T|$ >> $|A|$. Each task $T_i \in T$ consists of a tuple $(s_i, g_i)$, which represent ...
3690219115's user avatar
0 votes
0 answers
28 views

Lagrange Duality in Robust Optimization

I am learning Robust Optimization and been stuck on this example. I've brushed up on my knowledge of Lagrange duality and referred to a couple of textbooks on Linear Programming but not able to ...
stuckinlocal's user avatar
0 votes
0 answers
25 views

Linear programming: proof of existence of optimal basic feasible solution

I am working through a proof outlined in section 4.4 of Operations Research: Applications and Algorithms, by Wayne L. Winston. The objective is to show that if a linear program has an optimal solution,...
Michael Wheeler's user avatar
1 vote
1 answer
66 views

Examine whether the following set is a convex set [closed]

Examine if $\{(x, y)\in \Bbb R^2 \mid 2x+3y≤6,2x+3y≥6, x≥0, y≥0\}$ is a convex set After solving the constraints, we come to the conclusion that the set is basically a line segment joining points (3, ...
Amoeba_37's user avatar
0 votes
0 answers
30 views

Solving linear programming question with one constraint where constraint is same formula as objective function

Image for visualization I recently came across this variation of linear programming problem where given a set of 2-D points, we would like to find 1 point which maximizes certain objective function. ...
askyfullofstars's user avatar
0 votes
0 answers
14 views

Error Propagation from Linear Programming Constraints. Given $Ax = b$, $x \ge 0$, and $Cov(b)$, what is variance of $\min x_i$?

Given $Ax = b$, $x \ge 0$, and the covariance matrix $Cov(b)$, what is variance of $\min x_i$? Could there be an analytical solution? $x_i$ is the $i$-th element of $x$. $A$ is a $m \times n$ matrix ...
Augustin Pan's user avatar
-1 votes
0 answers
16 views

Check if Feasible solution is basic? [closed]

I was wondering if given a linear programming problem in canonical matrix form Ax = b ,if you have a point that is a feasible solution how would you determine if that point is a basic feasible ...
Roe's user avatar
  • 9
0 votes
0 answers
11 views

Optimal Table may change in LPP

If we solve a LPP with let's say 2 constraints with all slack starting variables with non negative right hand side. We get the optimal table. Now suppose we change the constraint coefficient of a ...
Upstart's user avatar
  • 2,637
0 votes
0 answers
34 views

Prove $Ax\leq b$ for $A=\begin{pmatrix} 1 & -1\\ 1 & 1\end{pmatrix}$ and $b=0$ is not total dual integral

I need to show that $Ax\leq b$ for $A=\begin{pmatrix} 1 & -1\\ 1 & 1\end{pmatrix}$ and $b=(0, 0)^T$ is not total dual integral. So I have calculated that $Ax\leq b$ holds only when $x_1\leq 0$ ...
toki's user avatar
  • 95
0 votes
0 answers
42 views

How is different unbounded and bounded?

#Here graph will be create most likely same but how Q1. will be Unbounded and Q2. will be Bounded Q1.-> How it is Unbounded LPP Max z = 30 x + 15 y Subject to 4 x + 6 y >= 12 4 x + 1 y >= 4 ...
Kuchh Bhi's user avatar
0 votes
1 answer
54 views

Linear programming constraint involving maximum

I am trying to formulate a much bigger problem as an integer linear program, but I am stuck with one particular constraint and am not sure how to formulate it. To put it shortly, the problem deals ...
AlaskaYoung's user avatar
0 votes
0 answers
49 views

Dual of LP representation of graph coloring

I have found a representation of the graph coloring problem as an ILP. Given a graph $G = (V, E)$. Let $C$ represent the set of colors. Let $w_c$ be a binary variable that is $1$ if the color $c$ is ...
mNugget's user avatar
  • 377
0 votes
0 answers
38 views

Method of Calculating Efficient Points and Corresponding Weight Vectors

I was doing exercises from Joel Franklin's Methods of Mathematical Economics out of personal interest and found myself a bit conflicted as to how I approached problem 8 in the Multiobjective Linear ...
Aman Shah's user avatar
  • 161
0 votes
1 answer
91 views

how can I maximize a minimum function?

Consider a maximin problem with $\lambda=[\lambda_1,\lambda_2,...,\lambda_n]$ $$\max_{\lambda}\min_{i\in\{1,2,3,...,M\}}{f_i(\lambda)}$$ subject to $\lambda$ is any vector locating in a standard ...
jerry's user avatar
  • 69
0 votes
0 answers
75 views

Does every positive real sequence whose series converges to $a$ have a "straight line" convex subsequence that also converges to $a?$

This question is possibly related to my previous question and it's answer. Suppose $a_n>0\ \forall\ n\in\mathbb{N}\ $ and $\displaystyle\sum_{n=1}^{\infty} a_n = a.$ Does there exist a subsequence $...
Adam Rubinson's user avatar
1 vote
1 answer
48 views

Application of Farkas Lemma

Let $A \in \mathbb R^{m \times n }, b \in \mathbb R^m$ and $0 \neq c \in \mathbb R^m$. Prove: Either the system $Ax = c$ or the system $A^T y = 0, c^T y = 1$ has a solution. Looks a bit like Farkas ...
ATW's user avatar
  • 689
0 votes
1 answer
71 views

How to find expression for the reduced cost?

I'd like to know how to obtain an expression for the reduced cost for each of my primal variables, after having formed the dual problem. I have the following dual problem, where the dual variables are ...
somewhere's user avatar
2 votes
0 answers
58 views

Reduction from a Chebyshev\minimax approximation to linear programming to find solution vector

For this question $i\in\{1,2,\dots k\} $ Given samples $$ x_{i}\in\mathbb{R}^{8},y_{i}\in\mathbb{R} $$ Assume a linear model such that $y_{i}=a^{T}x_{i}-b+\varepsilon_{i} $ where $\varepsilon_i$ is ...
Danny Blozrov's user avatar
1 vote
1 answer
32 views

Numerical Method for (Total Variation) TV Norm Minimization of Linear Combination of Matrices

I have a matrix $\mathbf{A} \in \mathbb{R}^{2000 \times 2000}$ represented in memory by an array of $2000 \times 2000$ float32 elements and I also have $10$ arrays $...
VojtaK's user avatar
  • 358
2 votes
1 answer
76 views

Mixed linear programming: why is big-M needed to set a variable to the max of other variables?

Let's say I want to set a variable $z$ to the maximum of other variables. We'll assume that the objective function is not of help, that is, the objective function doesn't try to minimize the maximum. ...
StefanoTrv's user avatar
0 votes
0 answers
25 views

Strategy for Minimizing Open Rows in Matrix/Graph Traversal

I have a problem involving the traversal of a binary matrix (which can also be conceptualized as a graph traversal problem) under specific constraints, aiming to minimize the maximum number of ...
user2697423's user avatar
1 vote
0 answers
64 views

Optimization/Constraint Solving on Graphs

I play video games, and it sounded like a fun exercise to try to find the optimal order in which to complete quests: There exist multiple quest trees There are some quests with inter-dependencies ...
Gavin Ray's user avatar
  • 111
0 votes
1 answer
54 views

Linear programming problem with extra condition

I am working on a problem that might be represented as a linear programming problem. I am just a bit stuck around one extra condition that is usually not part of a typical linear programming problem, ...
Attila's user avatar
  • 31
0 votes
1 answer
25 views

Minimize an N-dimensional vector dot product with <N constraints

I have a list of N variables $\vec{x}=(x_1, x_2, \cdots, x_N)$ where in my situation N will be around 10 and all of these variables must be nonnegative real numbers. I also have three linear ...
slabi's user avatar
  • 1
0 votes
1 answer
35 views

Initial basic feasible solution for LPP with 'greater than' constraints

While solving a linear programming problem with n variables in m equations (n > m) using the simplex method, an initial feasible solution is found by setting n - m variables to zero. Mostly when ...
Hari's user avatar
  • 3
-3 votes
0 answers
49 views

Solving equations for n variables when the number of equations are m(<n)

I am taking a linear programming course this sem and here's what I read, "In order to insure that basic solutions exist, it is usual to make certain assumptions: (a) that n > m; (b) that the ...
IvoryAlpaca's user avatar
1 vote
0 answers
46 views

Simple proof that an extreme point belongs to the boundary of a halfspace containing all other points

Definitions Let $\mathbf{A}\in \mathbb{R}^{m\times n}, \mathbf{b}\in \mathbb{R}^{m}$ and $\mathbf{a} \in \mathbb{R}^n\setminus\{ \mathbf{0} \}, b \in \mathbb{R}$. The set $\{ \mathbf{x} \in \mathbb{R}...
Yuumita's user avatar
  • 579
0 votes
0 answers
25 views

Why are shadow prices the optimal solution of the dual

Consider an LP $\max_x c^t x$ s.t. $Ax \leq b, x\geq 0$. Let the dual problem be $\min_v b^t v$ s.t. $A^\top v \geq c,v\geq 0$. It is stated in standard text book that the shadow prices of constraints ...
Yining Wang's user avatar
  • 1,279
0 votes
2 answers
100 views

Linear program with unknown coefficients in objective function

I was given the following linear program $ \begin{align} \alpha x_1 + \beta x_2 &\rightarrow \max \\ -3x_2 &\le -9 \\ -x_1-2x_2 &\le -12 \\ -x_1-x_2 &\le -8 \end{align} $ where $\alpha$...
user1195883's user avatar
0 votes
0 answers
21 views

KKT necessary conditions - applied to linear sum function

I'm having issues interpreting the KKT conditions. Consider a very simple problem (from e.g. Economics) $$ \max_{(x_1, x_2) \in \mathbb{R}^2_+} x_1 + x_2 \quad \text{s.t.} \quad p_1 x_1 + p_2 x_2 = w $...
mwaddoups's user avatar
0 votes
1 answer
74 views

Linearization of nested absolute value objective $|a-b-|c||$

I am trying to define an optimization problem that minimizes the distance between $a(x)$ and $b(x)$, where I need to adjust $b(x)$ downwards using the cost function $c(x)$ (hence, the cost must always ...
Jean-Paul's user avatar
  • 195
1 vote
1 answer
65 views

Zero dual variables

I am struggling to prove the following claim: Primal problem (1) $\max_{x \geq 0} c^Tx$ subject to $Ax \leq b$ and $Dx \leq d$ Primal problem (2) $\max_{x \geq 0} c^Tx$ subject to $Dx \leq d$ Suppose ...
Anna  Vakarova's user avatar
0 votes
0 answers
21 views

Linear programming model

I am writing a linear programming model with two decision variables for the follow scenario but am having trouble structuring it. Here is the set up: A company is going to rent machines that produce ...
gunsnfloyd's user avatar
0 votes
0 answers
32 views

Python Native Implementation of Mixed Integer Linear Programming

Is it possible to have pure Python implementation of Mixed Integer Linear Programming, something similar to mip, pulp, cvxpy, etc. - but such simple as https://github.com/ispaneli/lippy - it is ...
Kamil Islamov's user avatar
0 votes
0 answers
11 views

Why is $c^T_N$ non-empty when computing the reduced cost in the first iteration of column generation?

Given an LP: $$\min_x\,\, \{c^Tx | Ax=b, x\ge0\}$$ I understand the expression for the vector of reduced cost is the following (notation explained below): $$ c^T_N - c^T_B B^{-1} N$$ where $c$=cost ...
somewhere's user avatar
0 votes
0 answers
41 views

How to formulate this transportation problem?

I have been trying to formulate this as a transportation problem but I can't seem to do so: We have $3$ types of projects and $3$ types of evaluators. We need to evaluate $61,40$ and $21$ projects of ...
Pedro García's user avatar
0 votes
1 answer
55 views

How can linear programming condition check if variable is a multiple of number?

Let's say we have linear programming problem with x1 and x2 variables. Maximize x1 + x2 where (for example) 0.3x1 + 0.7x2 <= 2 0.2x1 + 0.3x2 <= 3 How can be added one more condition, so linear ...
Kamil Islamov's user avatar
0 votes
0 answers
26 views

Finding possible values of entries of a simplex tabeau

While solving a standard form problem, we arrive at the following tableau, with $x_3, x_4, and x_5$ being the basic variables: The entries α, β, γ, δ, η are unknown parameters. We have to determine ...
abc's user avatar
  • 497
-1 votes
1 answer
85 views

How to linearize a max function in a constraint? [closed]

I have linear program that has constraint as follows: $ \max(x,y) \geq 0 $ where $x$ and $y$ are variables. How to linearize this inequality? How to write this constraints in google or tools?
edhi wiyoto's user avatar
0 votes
0 answers
13 views

Obtaining tight edges from a graph to find an MST

As far as I understand, to obtain an optimal solution of the Dual of the MST, meaning: \begin{align} ~\max &~ z (|V|-1) + \sum_{S \subseteq V : |S| \neq \emptyset} (|S|-1) y_{s} \\ \label{DMST2} ...
Ragon's user avatar
  • 308
0 votes
1 answer
26 views

How to identify a CPF solution in an LP model?

"For any linear programming problem with n decision variables, each CPF solution lies at the intersection of n constraint boundaries; i.e., it is the simultaneous solution of a system of n ...
Junior 's user avatar
0 votes
0 answers
56 views

Reference Request: LP representation of problems

I am preparing for an exam on Linear optimisation and came across different problems where some apparently non linear problems can be modelled as LP (For example here, here and here). I was wandering ...
abc's user avatar
  • 497
2 votes
1 answer
78 views

Complexity of solving systems of linear inequalities with two variables per inequality with additional constraints

Consider a system $X$ of linear inequalities containing at most two variables. In the general case, finding a solution over $\mathbb{R}\cap[0,1]$ can be done deterministically in polynomial time due ...
Daniil Kozhemiachenko's user avatar
2 votes
1 answer
54 views

Pseudo if statements in LP programming

When designing LPs for exams I often run across problems where I would like to input an "if-statement". For example: $5\leq x_b$ if $p_a\geq 10$ I've tried dividing by itself and using floor ...
Aron Fredriksson's user avatar
1 vote
1 answer
95 views

Is it possible to transform a Linear Programming problem to a Signomial Problem?

I am an electrical engineer who is currently working with some optimization problem. From this "MM Algorithms for Geometric and Signomial Programming" paper, it seems that although signomial ...
Tuong Nguyen Minh's user avatar

1
2 3 4 5
102