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
20 views

How to interpret complementary slackness and the role it plays in proving optimality?

Here's the definition of Complementary Slackness from Bertsimas (1997). Let $\textbf{x}$ and $\textbf{p}$ be feasible solutions to the primal and the dual problems, respectively. The vectors $\textbf{...
1
vote
0answers
40 views

How or which solver find solution that holds strictly complementary slackness condition

So as theoretical I know interior point generate a solution in which the solution satisfies strictly complementary slackness condition. but when i use solver like linprog (by specifying 'interior-...
0
votes
0answers
42 views

Is the Linear Program below unfeasible, unlimited or does it have an optimal solution? ...

Is the Linear Program below unfeasible, unlimited or does it have an optimal solution? Properly justify your answer, making use of the dual program if it makes sense – if it doesn't, justify why \...
2
votes
0answers
36 views

understanding Simplex algorithm

I am trying to understand the relation between two different presentations of the simplex algorithm. Let $x,c \in \mathbb{R}^{n}$, $A \in \mathbb{R}^{n \times m}$, $b \in \mathbb{R}^{m}$. Let us ...
0
votes
1answer
52 views

Extreme point theorem of linear programming

So I was told to find a counterexample to this linear programming extreme point theorem: "If $S$ is nonempty and not bounded and if an optimal solution to the problem exists, then an optimal ...
1
vote
1answer
55 views

Subsystem of infeasible system of linear inequalities

Suppose that we have a system of linear inequalities described by $$Ax \leq b$$ where $A$ is $m \times n$ matrix. I want to show that if the system is infeasible then it has a subsystem of at most $\...
0
votes
0answers
47 views

Upper Bound on Minimum Number of Inequalities that Determines Infeasibility

Let us have $m$ inequalities in $n$ variables, expressed by the form $Ax \leq b$ where $A \in \mathbb{R}^{m \times n}$, $x \in \mathbb{R}^{n \times 1}$, and $b \in \mathbb{R}^{m \times 1}$. Suppose ...
0
votes
1answer
57 views

Version of Farkas Lemma

In lecture we had this version of Farkas lemma: Let $A\in \mathbb{R}^{m\times n}$, $b\in \mathbb{R}^n$. The system $Ax\leq b$ has no solution $\Leftrightarrow$ $\exists y\in \mathbb{R}^m_+$ so that $$...
0
votes
0answers
48 views

Frobenius norm minimization with inequality constraint

Let $A \in \mathbb R^{n \times m}$, $B \in \mathbb R^{n\times r}$, $X \in \mathbb R^{m\times r}$, and $Y\in \mathbb{R}^{n\times m}$. Let $\|\cdot\|_F$ be the Frobenius norm of a matrix. How can we ...
0
votes
1answer
45 views

Linear problem with min of hyperbolic functions as the objective [closed]

I am trying to convert the problem below to linear programming problem and solve it with simplex algorithm. I am aware that converting max and min in goal function usually means adding proper ...
1
vote
1answer
37 views

Linear programming with two maxes in a min function

Suppose $A, B, C$ are sets such that $B,C$ are disjoint. Let $f : A\times (B\cup C) \rightarrow \mathbb{R}$ where for fixed $y\in B\cup C$, we have that $f(a, y)$ is linear in $a$. Then is it true ...
2
votes
1answer
37 views

Fixing a minimal number of variables in linear programming problem to worsen objective

Consider a fairly standard linear program with $A\in \mathbb{R}^{m\times n}$ and cost vector $c\in \mathbb{R}^n_{\geq 0}$ such that $\begin{align*}\text{maximize}&& c^Tx\\\text{such that} &...
0
votes
1answer
18 views

Chosing an objective function to avoid optimal values having variables as zeros

Let's assume I have a sequence of non-overlapping tasks of type X and Y mixed. I have various runs of such sequences where it is known how many times Xs and Ys were executed as well as the approximate ...
1
vote
1answer
46 views

Change in the optimal value of a linear program after relaxing one of the constraints

We have a linear program \begin{align} \max_{x} f:= c^T x ~~~\text{subject to}~~~ h_i(x)= 0, ~i=1,\ldots,m ~~~\text{and}~~~ x\geq \epsilon_1 \end{align} with optimal solution $x_1^*\in\mathbb{R}^n$, ...
0
votes
0answers
35 views

Optimizing $\arg\min_{U}||R-UMU^\dagger|| $

Consider the optimization problem $$\arg\min_{U}||R-UMU^\dagger|| $$ with R and M hermitian matrix and U unitary and ||.|| is the Frobenius norm. Are there known numerical method to solve it ? I ...
0
votes
0answers
18 views

LP - Artifical variable necessary or not for greater than sign

I am current studying LP and also the simplex method. However, the slides from my professor are not that detailed so I was trying to search for online resources. Particularly about how to convert an ...
2
votes
0answers
172 views

Show that if $n-m=2$, then the simplex method will not cycle, no matter which pivoting rule is used

Here $n$ is the number of variables and $m$ is the number of constraints. This is the Exercise 3.10 (with asterisk) in the classical textbook Introduction to Linear Optimization by Dimitris Bertsimas ...
1
vote
1answer
69 views

Linear Programming Simplex Method: What exactly are the basic and non-basic variables?

I'm having a little bit of confusion understanding what exactly are the basic and non-basic variables in a linear programming problem when using the Simplex Method. From my understanding and reading ...
0
votes
0answers
13 views

Why does quantile regression interpolate $p$ observations?

I'm currently reading Quantile Regression (2005) by Roger Koenker. In section 2.2 page 33, it mentions that These vertex solutions, as we will show in more detail in Chapter 6, correspond to points ...
3
votes
1answer
55 views

Determining whether an LP program is a minimization or maximization problem given its objective values for certain parameters.

I am completely stuck on the following question: Consider the LP program $Extr\{c^T x|Ax≤pb+d\}$,where $Extr$ is either $min$ or $max$, and $p$ is a real parameter. It is known that the optimal ...
1
vote
0answers
94 views

Linear programming: Find feasible basic solution for the Simplex Method

My question is related to this question. Given a Linear Program (LP) $max\{c^Tx: Ax \leq b, x \geq 0\}$ with $x,c \in \mathbb{R}^n$ and $A \in \mathbb{R}^{m \times n}$. The Simplex Method needs a ...
0
votes
0answers
58 views

Show that an absolute value optimization problem has a local minimum that is not a global minimum

Consider a linear optimization problem, with absolute values, of the following form: \begin{align} \textrm{minimize} \ c′x+d′y \\ \textrm{subject to } Ax+By≤b \\ y_i=|x_i|, \end{align} Assume that ...
0
votes
1answer
59 views

Minimizing combinatoric sum of piecewise-linear functions

A convex piecewise-linear function can be defined as $f_i(x) = \textbf{max}_{j=1,\cdots,m} a_jx+b_j$ where $a_j, b_j, x \in \mathbb{R}$. To find its minimum, I can construct a linear program using ...
1
vote
1answer
37 views

LP Duality. What is the correct dual to this linear program?

Suppose a linear program that is defined as follows with decision variables $x_i, y_i z$ and parameters $a, b, c_i$. $\min \sum_{I}^{} a x_{i} + \sum_{I}^{} b y_{i}$ $s.t.$ $x_{i} \geq z - c_i \ \...
0
votes
1answer
32 views

Linear objective involving intersection point

Let $L$ be a line in $\mathbb{R}^n$, that is, $\dim L = 1$ ($L$ arises as the face of a polytope/intersection of halfspaces). We're given a fixed objective vector $\mathbf{c}\in\mathbb{R}^n$. Consider ...
0
votes
2answers
29 views

Demonstrate using first-order conditions

A quadratic function of the form function $ f:\mathbb{R}^n\rightarrow \mathbb{R} $ , given by $ f(x)=(1/2)x^T P x + q^T x + r$, where $P\succeq 0$ and $x, q \in \mathbb{R}^n$ and $r \in\mathbb{R}$. ...
0
votes
0answers
30 views

How can I find the correlated equilibrium probability distribution with the help of linear programming algorithm?

The following matrix is the so called battle of sexes game, which has two Nash Equilibria in pure strategies, that is $(F,F)$ and $(C,C)$ with payoff $(2,1)$ and $(1,2)$ respectively and one in mixed ...
0
votes
1answer
64 views

Formulating absolute values as linear programming models

If we have multiple absolute values, how do we proceed to solve the problem by reformulating as a linear programming model? F.ex assume we have the following problem: Minimize $x_1 + 2|2x_2 + 5|$ ...
0
votes
0answers
24 views

Need help in framing the generic linear equations with following constraints.

I have a binary variable array: $Y(i,j)$. Where $i=1,\dots,I$ and $j=1,\dots,K$. Here $K$ and $I$ need not to be same. In other words, the matrix formed $Y(i,j)$ is not necessarily be a squared ( but ...
2
votes
0answers
30 views

IBM ILOG CPLEX is 'optimal with unscaled infeasabilities'?

The problem being solved is finding the truss with the least weight, exactly done as on this website: https://www.layopt.com/truss/. This method is also called the ground structure method. I am aiming ...
0
votes
1answer
43 views

Second order conditions in linear programming problems?

I know, that in linear programming problems, in order to find maxima or minima, you search for corner solutions of a polyhedron. So, there is a system of linear equations, that you are trying to solve ...
0
votes
1answer
54 views

Need help in framing the set of linear equations for a binary variable as per following conditions [closed]

I have a binary variable array: $Y(i,j)$. Where $i=1,\dots,I$ and $j=1,\dots,K$. Here $K$ and $I$ need not to be same. In other words, the matrix formed $Y(i,j)$ is not necessarily be a squared ( but ...
0
votes
0answers
12 views

Constructing an infeasible primal linear program whose dual is also infeasible.

I could come up with an example where the linear program in infeasible and its dual is unbounded but I cannot create an example where the 2 of them are infeasible.
0
votes
0answers
22 views

In TSP problem, can integer constraint of edge variable in DFJ formula be removed

We wsually regard TSP problem as a MIP problem, however the book "In Pursuit of the Travelling Salesman" illustrates Dantzig's process of solving the problem of travelling among America. He ...
2
votes
1answer
39 views

Stuck at making a constraint for given LP problem where a machine can make one product or the other.

This is the text for following linear problem: In one factory there is a production machine which is available 170 hours a month. Using this machine it is possible to produce 50 pieces of product A ...
1
vote
0answers
33 views

Minimize the length of a linear transformation of a vector by permuting its components

Let $A\in\mathbb{R}^{n\times n}$ invertible, and $b:=(0, \alpha, 2\alpha, \ldots, (n-1)\alpha)\in\mathbb{R}^n$ where $\alpha>0$ is such that $\|b\|_2=1$. Are you aware of a way to estimate the ...
0
votes
3answers
96 views

If $A$ has independent rows, is the set $\{x \mid Ax \preccurlyeq b\}$ an unbounded set?

Let's say we look at the set $S = \{x\mid Ax\preccurlyeq b\}$ where $A\in \mathbb{R}^{m\times n}$ has independent rows, $x\in \mathbb{R}^n$, and $ b\in \mathbb{R}^m$. Can we prove that set $S$ is ...
0
votes
1answer
57 views

Optimising class assignment based on test score and class choice?

Suppose some students enrol themselves onto a course. The course has 6 available classes, A,B,C,D,E,F, each at a different time and/or day. All the classes have the same upper limit on size, say some ...
0
votes
1answer
45 views

interpretation of independent linear inequalities

Let $Ax\leq b$ be a system of linear inequalities where $A\in R^{m\times n}$, $x\in R^n$ and $b\in R^m$. Suppose $A$ is a matrix with linearly independent rows. I wonder what would be the geometric ...
1
vote
1answer
18 views

Example of the equivalence of two desrciption of polyhedra

This is an extract from a linear optimization book: However, I do not understand why both of these conditions describe the same polyhedra? The linear equation results in a set $$\left\{\begin{bmatrix}...
0
votes
0answers
72 views

Want to form the linear equations for conditions given below: [duplicate]

I want to formulate the set of linear equations for the following conditions: $Q(i) = 0$ if $y(i)=1$ for $i = 1,2,...,n$ $Q(i) = P(i)$, if $\sum_{j=1}^{n}{y(j)}=0$ for $j \le i$. $Q(i) = P(i-r)$, if $...
1
vote
1answer
193 views

I want help in formulating a mixed integer linear problem formulation

I want the following help in linear fashion (In my previous question, I asked the same but the solution was not generic. Please check it : Prev.Question). I have an arbitrary vector: $P(n) = [1, 2, 3,...
2
votes
1answer
81 views

I want help in formulating a mixed integer linear problem formulation.

I want the following help in linear fashion: I have a vector: $P(n) = [1, 2, 3, 4, 5,...,n]$ I have binary variables with length of $P:y(1),y(2).....y(n)$. These variables, y(i) can only take $0$ or $...
1
vote
1answer
15 views

Linear program, entering/leaving variables & exit conditions

I'm trying to implement my own Simplex solver and I'm encountering some issues. When choosing the leaving variable, one is supposed to pick the element with the smallest positive $b_i/x_{i,j}$ where $...
2
votes
1answer
21 views

Linear Programming: At least two different (integer) values

Let's assume I have multiple tools $T=\{t_1,\dots,t_n\}$ (binary decision variables) and each tool has an efficiency, $E=\{e_1,\dots,e_n\}$. For a given $k$ I now want to maximize the efficiency: $$\...
1
vote
0answers
41 views

TDI systems of integral polyhedron

There is a theorem by Giles and Pullybank that states the following: "For each rational polyhedron $P$ there exists a rational TDI-system $Ax \leq b$ with $A \in \mathbb{Z}^{m \times n}$ and $P = ...
2
votes
1answer
38 views

Reinterpret maximin as LP

I have the following problem For $L,T \in \mathbb{R}^n$ and $G \in \mathbb{R}^{n\times n}$ $$\mathsf{max}_L \;\mathsf{min}_T \sum_{j = 1}^n T_j$$ Subject to \begin{align*}\forall i,j &&T_j \...
-2
votes
1answer
24 views

For vectors $u, v \in \mathbb{R}^n$ with $\|v\|_\infty \leq \ 1$, prove that $u^{T}v \ \leq \ \|u\|_1$ [closed]

I get that this is intuitive but I am struggling to get a proper proof for the same.
0
votes
1answer
32 views

Possible to reduce problem to linear problem?

I've been trying my hand at using the Google OR Tools (GLOP) solver, and I've successfully modeled all needed constraints save for one. Given an array of rational numbers, p of length n. I want to ...
2
votes
1answer
58 views

How to write dual form of $ \min \sum_{i=1}^{n} \mathbf{x}_i\mathbf{y}_i$ with $\sum_{i=1}^n \mathbf{y}_i = 1, \mathbf{y}_i \ge0$

$$\begin{array}{ll} \text{minimize}_{\mathbf{y} \in \mathbb R^n} & \sum_{i=1}^{n} \mathbf{x}_i\mathbf{y}_i \\ \text{subject to} & \ \sum_{i=1}^n \mathbf{y}_i = 1, \mathbf{y}_i \ge0 \end{...

1 2 3
4
5
90