Questions tagged [linear-programming]

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

1,444 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2
votes
0answers
250 views

Big M constraint question

I have a question regarding using Big M constraints to solve the following problem: Given: $a, b \ge 0$ and integers. $$2a + 5b \le 17\\ a + b \le 5\\ 3a + 6b \le 20$$ For at least two of the ...
2
votes
1answer
325 views

Integral Farkas Lemma

The context of this question is commutative algebra, however the question itself is more related to convex geometry. All necessary information is given. In the proof of Lemma 3.1.1 in the book "...
2
votes
0answers
287 views

Is simplex method weaker than other methods?

Given linear program: $$ \text{min } x_1 - x_2 + 2 x_3 $$ s.t.: $$ -3x_1 + x_2 + x_3 = 4 $$ $$ x_1 - x_2 + x_3 = 3 $$ $$ x_i \geq 0; i = \{1,2,3\} $$ solution by simplex method (with double pass) is ...
2
votes
0answers
84 views

Higher dimensional Euclidean geometry problem

In my engineering/physics research, I am facing one math problem which I believe should be well established in mathematics... I have a linearly spanned space given by the column vectors of the ...
2
votes
1answer
854 views

Constraints of a linear programming problem

QUESTION Sandy Arledge is the program scheduling manager for WCBN‐TV. Sandy would like to plan the schedule of television shows for next Wednesday evening. Of the nine possible one‐half hour ...
2
votes
0answers
152 views

Showing a Hermitian preserving map is not necessarily positivity preserving?

Say I have a linear map, which is not positivity preserving $$\phi: \mathscr H \to \mathscr H$$where $\mathscr H$ is the set of $n \times n$ Hermitian matrices. Then does there exist a positive ...
2
votes
0answers
53 views

Linear programming: can someone explain how the time steps work here?

I'm reading a paper, "A Player Selection Heuristic for a Sports League Draft". In it, the authors have come up with a method to assist you in picking players for a fantasy sports league. I'm having ...
2
votes
0answers
54 views

Calculating second derivative of $g(\alpha) = f(\textbf{y}(\alpha))$

I'm having problems with the second derivative of the function $g(\alpha) = f(\textbf{y}(\alpha))$ (which I will define more precisely below). I tried calculating it myself, could anyone just simply ...
2
votes
0answers
732 views

Comparing two probability distributions

In my research I have to find two discrete probability distributions by solving two separate linear programs. The domain of optimization is the probability space of $m^n$ atomic events, where $n$ is ...
2
votes
0answers
641 views

Linear programming with (countably) infinitely many variables and finitely many constraints

Is it possible to do linear programming with (countably) infinitely many variables and finitely many constraints? If not, what do you propose? (Example Link): Maximum and minimum of an integral ...
2
votes
1answer
144 views

Optimizing Rectilinear Distance Traveled

I have a simple pipe network like this (not to scale): I can place a "valve" on any point on that pipe. What the valve does is it permits a certain viscous fluid to fill the pipes. However, because ...
2
votes
0answers
93 views

Existence of a Linear Optimization Problem

I am working on a linear static optimization problem. I found a solution to the problem. However, I want to formally check the solution existence. I tried some methods but I don't know if it is enough ...
2
votes
0answers
148 views

Problem generating random vectors with a randomized linear programming with equality constraints (weird clustering)

Summary For simulation problems, I need to be able to generate large numbers of random lists of numbers, say $x_1, x_2, \dots, x_n$ (where $n \approx 1000$), subject constraints similar to what one ...
2
votes
0answers
102 views

Explicitly solving linear programming problems

Linear programming problems generically involve the use of a repeated algorithm to solve. Is there a reason they can't be solved algebraically/formulaically? Ex: Minimize x1 + x2 + x3.... x1, x2, ...
2
votes
0answers
78 views

Solving linear equation with some conditions

Consider the equation $y=af+bg+ch$ where $a+b+c=1$ and $a,b,c$ are between 0 and 1. y,f,g,h are vectors with the same size and a,b and c are parameters that must be constant values. How can I solve ...
2
votes
0answers
208 views

How to visualize duality

In My course of linear programming we are given the definition of a primal/dual problem. However I cannot really get my heard around what it actually is? It helps us in later exercises. Are we ...
2
votes
0answers
73 views

Linear Program Transformations

I have a Linear Program with constrains of the form: $$a_{11}x_1+a_{12}x_2+\ldots\le 0$$ $$a_{21}x_1+a_{22}x_2+\ldots\le 0$$ $$a_{31}x_1+a_{32}x_2+\ldots\le 0$$ My problem is that if I try to ...
2
votes
1answer
1k views

Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
2
votes
1answer
580 views

Convex optimization and linear programming please help! :)

How would I write the following as a standard form LP? Minimizing $\sum_{i=1}^n x_i + c\max(a_i-x_i)$ for $a_i \ge 0$ and what is the optimal value for when $c=n$ How to express minimize $\frac{1}{2} |...
2
votes
0answers
64 views

Put positive polynomial in finite intersection of half-spaces

Denote by $V={\mathcal P}_{n,d}$ the space of polynomials in $n$ variables with degree at most $d$, with rational coefficients. Thus ${\mathcal P}_{n,d}$ had dimension $\binom{n+d}{n}$ over $\mathbb ...
2
votes
0answers
550 views

Determine if a polyhedron is a polytope

Note, a polyhedron is the intersection of finitely many half spaces in $\mathbb{R}^n$ and a polytope is a bounded polyhedron. Let $M$ be an $m \times n$ matrix of integers. Let $P$ be the (possibly ...
2
votes
0answers
226 views

Linear Optimization Problem - Assign Objects to People

Say you have a 100x5 matrix of integers between -10 and 10, including zero. Each row represents an object; each column represents a person's ranking of the objects. Of the possible ranking values <...
2
votes
0answers
129 views

Why is every nontrivial surface of a polyhedron an intersection of facets?

In the geometry of (convex) polyhedra used for linear optimization, one has the lemma: Consider the inequality $Ax \leq b$ where $A^+ x \leq b^+$ (the non-implicit inequalities of $Ax \leq b$) ...
2
votes
1answer
95 views

How can I fairly distribute identical goods bought at different prices amongst customers so that they all pay the same price?

I'm trying to allocate a product bought at different prices to different clients in a fair way. Initially, each of the $n$ client asked for a specific quantity of the product $a_1\ldots a_n$ The ...
2
votes
0answers
457 views

Sensitivity analysis on non linear problems

First of all, I would like to apologize if this question does not fit into the "soft" category. I am quite a newbie around here, and maybe I can fail to get the feeling of what exactly is a "soft" ...
2
votes
1answer
405 views

Indicator variable of the sign of a difference in a math program

I am interested in a mathematical program with objective: $\max \sum_{i \in I} x_i $ where $x_i$ is a binary defined variable as follows: $x_i = 1$ if $y_i - A \geq 0$ $x_i = 0$ if $y_i - A < 0$...
2
votes
1answer
228 views

Smooth Reformulation of NonSmooth Constraints

If I have something like : \begin{align} \min_x \max_i f_i(x) \end{align} I can reformulate this nonsmooth formulation as: $$\min_x z$$ $$z\geq f_i(x)$$ and I have a smooth formulation of the problem. ...
1
vote
0answers
20 views

LP with binary constraint coefficient matrix

Suppose I have the following LP: \begin{align} \underset{x}{max.} \quad & \sum_i^n c_{i}x_{i} \\ s.t. \quad & \mathbf{A}x \leq b, \; \mathbf{A} \in \{0,1\}^{m \times n}, b \in \mathbb{R}^{m} ...
1
vote
0answers
17 views

Solutions to system using Fourier-Motzkin Elimination

I am trying to find a solution to this system using Fourier-Motzkin Elimination, but I don't know how to finish this. Here is what I have so far. $x_1-x_2\leq 0,\quad x_1-x_3\leq 0,\quad -2x_1+2x_2+...
1
vote
0answers
49 views

Proving that a polyhedron contains a line if and only if $Ax=0$ has a non-zero solution.

I would like to check if my proof is correct. I do not have much experience of proving stuff so I would appreciate if anyone could point out and fix some mathematical/proving/wording errors if there ...
1
vote
0answers
19 views

A “lifting property” for linear maps on cubes?

Let $L : \mathbb{R}^n \twoheadrightarrow \mathbb{R}^m$ be a linear map that is surjective. Let $[0,1]^n$ denote the unit cube in $\mathbb{R}^n$, and let $Z := L([0,1]^n) \hspace{5pt}$ ($Z$ is a ...
1
vote
0answers
54 views

Why does standard quadratic programming contain $\dfrac{1}{2}$ in the objective function?

Does the $\dfrac{1}{2}$ provide any of computation convenience?
1
vote
1answer
27 views

Resource allocations

There is a certain factory and there is time for which it is necessary to consume a certain amount ($ X $) of a resource. At each specific period of this time (and the time is discrete), a factory can ...
1
vote
0answers
27 views

Is there a standard way to see if the solution set to a systems of linear equations crosses a given region?

I'm interested in the following question: Determine if there exists a solution to linear system $A\vec{x} = \vec{b}$ that lies in region $R$. Is there a general procedure for doing so? Currently, ...
1
vote
1answer
28 views

Linear Programming Price Change After X Units Sold

I have a question regarding writing some formulas for LP. How would you code the price change after X number of units sold. So lest say the base price for the first X units sold is £5 and then there ...
1
vote
0answers
28 views

Local branching in Benders Decomposition

I am trying to understand how local branching is used in Benders Decomposition. I was wondering if someone could kindly explain me how exactly local branching works. If my understanding is correct, ...
1
vote
1answer
30 views

Find average value of the function $f(x,y,z)=3x-4y+5z$ over the triangle (simplex) $x+y+z=1$ ($0\leq x,y,z<1$).

Find the average value of the function $$f(x,y,z) = 3x-4y+5z$$ over the triangle (simplex) $\left\{ (x,y,z) \mid x+y+z=1 \land 0 \leq x,y,z < 1 \right\}$. Is there a simple way to do this problem?
1
vote
1answer
28 views

Verify that the optimal basis consists of the particular slack variable without using simplex method.

In a linear programming problem, how to verify that the optimal basis consists of the slack variable of a particular constraint without using the simplex method? Consider the following problem: $$ {\...
1
vote
0answers
41 views

Making Matrix Totally Unimodular

Is there a way I can rewrite the following matrices to make the matrix (A) to be totally unimodular and still maintain the relevance of the equations. Thanks.
1
vote
0answers
75 views

Can the following be expressed as an LP with (an) additional constraint(s)?

Using Gurobi, I am trying to solve the following LP $$\text{minimize} \sum_{i=1}^d r_i \\ \text{subject to } x^TV - r = 0 \\ -1 \le x_j \le 1 \text{ for all } 1 \le j \le n $$ Here, $V$ is a set of ...
1
vote
0answers
19 views

Prove that the Basis Solutions of a Linear Programming Problem are the Extreme Points of the Polyhedron of Allowed Solutions

Given a system of $$(\text{P})\ \begin{cases} Ax=b \\ x \ge 0\end{cases}$$ where $A \in \Bbb{R}^{m \times n}, m \le n, \ \text{rank}(A) = m, b \in \Bbb{R}^m, x \in \Bbb{R}^n$. By $x \ge 0$, we mean ...
1
vote
1answer
47 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
25 views

Find the lowest difference in exchanged value

I was wondering if this type of problem can be modelled with Linear Programming or any other approach that much more efficient. Let say I've 5500 in original currency. I want to convert to other ...
1
vote
0answers
40 views

Linear transformation of overdetermined linear system

Assume that we have the following over-determined linear system \begin{cases} z_{1}=c + \phi z_0\\ z_{2}=c + \phi z_{1}\\ \dots\\ z_{n} = c + \phi z_{n-1} \end{cases} with $n>2$ and all $z_{0}, \...
1
vote
1answer
20 views

Minimizing a General n-Dimensional Linear Program

I am currently studying linear programming and am attempting to solve: minimize $c^Tx$ subject to $\sum_{i=1}^{n}x_i=0$, and $\sum_{i=1}^{n}x_i^2 = 1$. From the second constraint I know that: $-1\...
1
vote
0answers
50 views

Simple Linear Algebra/ Linear Programming Proof: Proving Existence of Vector that satisfies Properties

Hi, I've proved parts a and parts b, but I'm confused on how to prove part c. I think it should really follow directly from parts a and parts b but I'm lost. In part c, are we assuming that $x_j$ is ...
1
vote
0answers
70 views

Maths (ILP) puzzle from a programming contest

This programming contest puzzle concerns itself with "cards", each of which bears a certain pattern of either one circle, one square, one triangle, two circles, two squares, etc. up to three circles, ...
1
vote
0answers
33 views

mixed-integer linear programming problem with non-linear restrictions

I'm trying to maximize this problem using MILP (mixed-integer linear programming). K represents constant values and decision variables are x1, x2 , x3(binary); $\max \sum_{i = 1}^{p}(x2_{i}\cdot k -...
1
vote
0answers
25 views

Find all the optimal solutions to the dual problem of this maximization problem

This was posted a year ago, but no answer was posted. Here's my crack at it and hopefully I can get some critique because I want to get better at this. Maximize $z=-3x_1-x_2-x_3$ $x_4=5-x_1-2x_2$ $...
1
vote
0answers
14 views

Defining binary variables on box constraints in mixed integer linear/convex program

I have $n$ variables $y_1,\dots,y_n\in\mathbb R$ with no upper bound and no lower bound. I want to define a binary variable $b\in\{0,1\}$ on condition that $b=1\iff \wedge_{i=1}^ny_i\in[0,1]$. How ...