# Questions tagged [linear-programming]

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

3,561 questions
Filter by
Sorted by
Tagged with
26 views

28 views

### Linear programming such that feasible solution gives optimal solution to another

Let us say that we have a linear program $P={ (min C^tx | Ax=b,x\geq0)}$ Assume that $(P)$ has an optimal solution. Write a system of linear equations and inequalities $(P_1)$ such that any feasible ...
20 views

17 views

90 views

### Null Variable in linear programming

Let $P=\{x\in\mathbb{R}^n|Ax=b,x\geq0\}$ be a nonempty polyhedron, and let $m$ be the dimension of the vector $b$. We call $x_j$ a null variable if $x_j=0$ whenever $x\in P$. (b) prove that if $x_j$ ...
49 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 ...
69 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, ...
57 views

### Two conditional constraints (either or neither) for integer binary programming [closed]

Not sure how to go on about finding this constraint. The constraint asks for; either both or neither of $x_1$ and $x_2$ should appear. What I have so far is that y can be either binary values $0$ or ...
8 views

31 views

### Real World Example for Linear Programming in Finance

I am studying operations research and have been researching real world problems/applications of such things as linear programming, integer programming, MIP ect. I found mostly complete problems in my ...
34 views

### Formulating a pipeline with several variables

The question I have one constraint as number of faculty signing a contract of length r, i am unsure what other constraints i can make to complete the program. Would it be the amount of years worked?
70 views

### Breakdown an integer value to an array of integer maintaining the sum

I am working on a project where I need to breakdown an integer value according to an array of percentage values. My end array must contain integer value and the sum of the array must be equal to the ...
44 views

### Number of $x \in [0,1]^n$ such that Ax integer

If $A$ is an integer matrix in $\mathbb{Z}^{m \times n}$, why is there only a finite number of vectors $x \in [0,1]^n$ such that $Ax$ is a vector of integers?
31 views

### Reduce integer linear program constraints

I currently have defined a pure integer linear program that works well, but the number of constraints for a given input runs out of time and/or memory. Let me introduce the problem. I have an ...
39 views

### If $P$ is an unbounded polyhedron, there exists a point $c \in P$ and a vector $d \neq 0$ such that $\forall \lambda \geq 0$, $c+ \lambda d \in P$

If $P$ is an unbounded polyhedron, there exists a point $c \in P$ and a vector $d \neq 0$ such that $\forall \lambda \geq 0$, $c+ \lambda d \in P$. Hi so I dont know if this is true or not, ...
30 views

I am trying to distribute 15 tasks to two people. Each task can only be assigned to one person and each person has a time budget. I want to express this problem as a linear program (ultimately in the ...
8 views

### Why is it necessary for the RHS values in constraints to be non-negative for the Simplex Method?

What logical problems arise with negative RHS value in constraints? What does the presence of negative RHS mean, in a real-life example?
45 views

### Finding Dual Objective

I have the following simplified optimization problem: $max \quad ax+by$ S.t. $0≤x≤\bar{X}$ $0≤y≤\bar{Y}$ $z=E−x+β.y$ where, $E$, $β$, $a$, $b$, $\bar{X}$, $\bar{Y}$ are parameters and the rest ...
19 views

### How can I reformulate the problem in terms of convex combinations of the extreme points?

Maximize $$x_1 + 2x_2$$ \begin{align} x_1 - 4x_2 &\le 4 \\ -2x_1 + x_2 &\le 2 \\ -3x_1 + 4x_2&\le 12 \\ 2x_1 + x_2 &\le 8 \end{...
18 views

### How to correctly formulate multiple constraints to multiple feasible regions into one?

I believe this is a linear programming question that basically boils down to correctly formulating a feasible regions constraints from OR statements between other feasible regions. My direct question ...
24 views

### Is this conditional sum function valid for linear programming?

Linear programming requires a linear function to maximize in order to operate properly. I am trying to figure out whether I could use linear programming to solve a problem. However, I would need a ...
33 views

### Is strict complementary slackness unique?

We have $A \in \mathbb{R}^{m \times n}$ and rank$(A)=m$. By strict complementary slackness, we know that if the primal $(P)$ (in standard equality form) has an optimal solution, then the dual $(D)$ ...
27 views

78 views

### Linear programming example need help

***I'm new here I have one example of linear programming so if you can point me in the right direction. Here is the text of exercise: The company manufactures two-unit home air conditioners, which ...