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

learn more… | top users | synonyms

0
votes
0answers
16 views

Creation of a cononical form

I wrote during a lecture that the canonical form of linear program was \begin{equation*} \begin{cases} \max C^Tx \\ Ax = b\\ x\ge 0 \end{cases} \end{equation*} But ...
0
votes
2answers
17 views

Constraint Set of Canonical Linear Programming Problem is Convex

I'm reading through my first textbook on linear optimization. The book states a theorem without proof and I'd like to understand why it's true. Glossary of Terms: Definition 1 The problem Maximize ...
2
votes
3answers
27 views

When to use which simplex algorithm?

in linear programming we use simplex method to find optimal solution. But I have also seen methods like Two Phase Method, Dual method, M-method. My question is, how do I know which method to use? For ...
0
votes
0answers
23 views

What is the definition for “equivalent linear programming problems”?

My question is in the title: How can we define exactly when two linear programming problems are equivalent? I used to see some definition such as "$B$ is equivalent to $A$ if $B$ is solvable, ...
0
votes
1answer
28 views

What is the dual problem in linear programming

In linear programming, Von Neumann define the dual of $$(I)\, \left\{ \begin{array}{rl} c^Tx &\to \min\\ Ax &\ge b\\ x&\ge 0 \end{array} \right. $$ is the problem $$(II)\, ...
1
vote
2answers
45 views

How to find the number of possible solutions of LP problems?

Let us assume that we have a linear optimization problem (LP) that has multiple optimal solutions. I would like to know if there is a solver or an algorithm that can provide the number of optimal ...
1
vote
0answers
12 views

An unfamiliar constraint in dual of LP for 'extreme point' optimal solution

I am trying to understand two-stage chance-constrained LP and reading a paper, which has a title "A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with ...
0
votes
0answers
13 views

Transforming an array of equations as a canonical form?

Today was my first course of linear programing, I've just read again my notes and I'm not sure how does this array of equations actually transformed itself. \begin{equation*} \begin{cases} ...
0
votes
2answers
69 views

How can I solve the following linear program?

I want to find the answer for the following linear program. Max $v$ subject to $$v-5x_1-x_2 \le 0 $$ $$ v-x_1-4x_2 \le 0 $$ $$ v-2x_1-3x_2 \le 0 $$ $$ x_1+x_2 = 1 $$ $$ x_1, x_2 \ge 0 $$ $$ v \in R ...
1
vote
1answer
39 views

Apply Simplex method using M-method

I want to solve the following linear programming problem: $$\min (3y_1-y_2+2y_3) \\ 3y_1+2y_2-y_3 \leq 9 \\ 5y_2-y_3 \leq 1 \\ 4y_1-y_2 \geq 1 \\ y_1+y_2+y_3 \leq 3 \\ y_1, y_2, y_3 \geq 0$$ In this ...
1
vote
0answers
18 views

Find max min with linear programming

I need to solve $$ \max_x \min_y x^T M y $$ subject to $$ \sum_{i=1}^n y_i = 1, \sum_{j=1}^m x_j = 1,\\ x \geq 0, y \geq 0 $$ where $ M \in \mathbb{R}^{m\times n} $, $ x \in ...
4
votes
1answer
45 views

Exercise 2.27 from Bazaraa (LP)

Consider the system $Ax=b$ where $A=[a_1,a_2,...,a_n]$ is an $m \times n$ matrix of rank $m$. Let $x$ be any solution of this system. Starting with $x$, construct a basic solution. There is a hint ...
0
votes
1answer
35 views

How to derive the dual problem of Knapsack problem

Knapsack problem is $$ \text{max} \, v^Tx$$ $$ \text{s.t.} \, w^Tx \le W, \, \, 0\le x_i \le 1 \, \, (i=1,...,n)$$ This is equivalent to $$ \text{min} \, -v^Tx$$ $$ \text{s.t.} \, ...
0
votes
1answer
24 views

How can I derive the following dual problem?

Standard form of the linear program is $$\text{Min} \, C^{T} x$$ $$ s.t. Ax=b $$ $$x\ge 0$$ Dual is $$\text{Max}\, b^Ty$$ $$s.t. C-A^{T}y \ge 0$$ By using the above definition, I want to find ...
0
votes
1answer
31 views

Linear Programming Free Variables

I am using a book called Introduction to Operations Research. I'm not sure how to deal with free variables that are not constrained i.e. they could be positive or negative. I understand how any ...
1
vote
0answers
46 views

Integer programming, system of linear inequalities.

I am woring on a problem and I got these inequalities. $t_{01}+t_{11}+t_{21}\ge 4$ $t_{02}+t_{12}+t_{22}\ge 4$ $t_{10}+t_{11}+t_{12}\ge 4$ $t_{10}+t_{01}+t_{22}\ge 4$ $t_{10}+t_{02}+t_{21}\ge 4$ ...
0
votes
0answers
50 views

Integer programming model not working

I have to formulate an Integer programming model for the following using XPRESS; There are 10 items that need to assigned to 2 categories, A and B. Each item has a weight and 30 % of the weight is ...
2
votes
1answer
105 views

Simplex method - identity matrix

I want to solve the following linear programming problem: $$\min (5y_1-10y_2+7y_3-3y_4) \\ y_1+y_2+7y_3+2y_4=3 \\ -2y_1-y_2+3y_3+3y_4=2 \\ 2y_1+2y_2+8y_3+y_4=4 \\ y_i \geq 0, i \in \{ 1, \dots, 4 ...
0
votes
1answer
34 views

Refinery - Mathematical formulation of problem

In a refinery, two types of crude oil $T_1, T_2$ get mixed with two different procedures $R$ and $W$ and produce two types of petrol $P_1, P_2$ as shown at the following matrix: $\begin{matrix} ...
0
votes
1answer
18 views

Does {$a_2,a_3$} define a basic feasible solution for the Linear Program?

Question: Consider the following linear program \begin{equation} \begin{split} \text{Minimize} \ x_2 \\ \text{subject to} \ x_1+ x_2 +x_3 = 4\\ -2x_1+x_2 = -3\\ x_1,x_2,x_3 \ge 0 \\ \end{split} ...
0
votes
0answers
25 views

Integer program with known non-integer “solutions”

I have an integer program (IP) (see the formulation here for example) with the matrix $A$ being total unimodular. In this case, the linear program (LP) relaxation of the IP provides an integer ...
0
votes
0answers
18 views

Mixed-integer (Linear) Programming (MILP) standard/canonical form

Is there a standard or canonical form for mixed-integer (linear) programming problems? For linear programms the standard form is sometimes given by: $$ \max_{\boldsymbol x} \boldsymbol c^T \boldsymbol ...
1
vote
1answer
81 views

Wrong optimal solution

If we have a linear programming problem that is of the form as the following: The initial tableau is the following: Then we get this: $\begin{matrix} B & b & P_1 & P_2 & P_3 ...
0
votes
0answers
18 views

Percentage constraint for Integer programming model

Th question is as follows: There are 10 items that need to assigned to 2 categories, A and B. Each item has a weight and 30 % of the weight is allocated to A and the remaining 70% to B.The objective ...
1
vote
2answers
42 views

Minimising a convex set. Is set of solutions convex?

We are minimising a convex function on a non-empty set defined by linear constraints (equalities and inequalities). $X^O$ is the set of all optimal solutions and we assume it is non-empty. Is it true ...
1
vote
1answer
33 views

How to write an absolute value expression in linear programming?

My objective function for the Xpress-IVE (Mosel lang) model is minimize |a-b| where a and b the number of elements in the decision variables which are arrays. Since there is no function to ...
0
votes
0answers
21 views

All facets' coefficients contain only integers -1,0,1

Suppose a polytope $C\subset \mathbb R^{kl}$ is the $l$-product of $k-1$-simplex with extreme points containing coordinates $0$ or $1$ in each coordinate. A linear transformation is given by ...
0
votes
1answer
23 views

integer valued outer normal vectors

Suppose a bounded polyhedra $C$ is given by $$x\in \mathbb R^n: Ax\leq b$$ The matrix $A\in\mathbb R^{m\times n}$ contains only elements from $\{-1,0,1\}$, which implies the outer normal vectors of ...
3
votes
0answers
103 views

Linear programming and shortest path

Given the linear programming formulation of the shortest path problem: $$ \begin{align*} \min & \sum_{u,v \in A} c_{uv} x_{uv}\\ \text{s.t } & \sum_{v \in V^{+}(s)} x_{sv} - \sum_{v \in ...
0
votes
1answer
30 views

Problem in forming linear equations in Linear Programming problem

Here is the given question: A toy manufacturer produces two types of dolls; a basic version doll $A$ and a deluxe version doll $B$. Each doll of type $B$ takes twice as long to produce as one doll of ...
0
votes
3answers
122 views

What are common Mathematical Programming Languages out there?

I've seen the term used Mathematical Programming to describe a superset of: Linear programming Quadratic programming Nonlinear programming Mixed-integer programming Mixed-integer nonlinear ...
0
votes
1answer
41 views

Books on Multi-Commodity Minimum Cost Flow Problems

I'm searching for books on Multi-Commodity Minimum Cost Flow Problems (MCMCF) with theoretical aspects (solvability, optimality conditions, similar statements like in the case of Min Cost Flow,...). ...
1
vote
1answer
57 views

MILP optimization constraint formulation

I'm trying to find a sensible way to add constraint for my optimization problem. Lets assume we have binary decision variables $x_i\in\{0,1\}$ and two constraints \begin{align*} \sum\limits_{i=1}^n ...
0
votes
0answers
12 views

How to graph polygon rising at an angle in 3D space from the origin of the coordinate axes with shaded region on the $x$-$y$ plane?

I am trying to obtain a graph just like this one that visually shows that an objective function is maximised in z-direction at a certain point and where the “ground” of the graph is the $x$-$y$ ...
0
votes
1answer
28 views

How to represent 2D lines (i.e. on $x$ and $y-axis$) on a 3D graph using either Cartesian ($z=f(x,y)$) or Parametric $(x,y,z)=f(u,v)$

How to represent 2D lines (i.e. on $x$ and $y-axis$) on a 3D graph using either Cartesian ($z=f(x,y)$) or Parametric $(x,y,z)=f(u,v)$ Hi, I've been working on a Simplex problem and would like to ...
2
votes
2answers
84 views

Formulating equation for two mutual exclusive integers

I have a problem with formulating non-binary linear equation with mutual exclusivity \begin{cases} x_1 \gt 0, \quad \text{OR} &x_2 \gt 0 \\[2ex] x_1 + x_2 = 300 \end{cases} As the result I want ...
2
votes
2answers
44 views

Convert any convex optimization problem to a linear objective

Wikipedia claims that: Any convex optimization problem can be transformed into minimizing (or maximizing) a linear function over a convex set by converting to the epigraph form. Is there a ...
0
votes
1answer
74 views

Can the “goat cabbage wolf” problem be solved using integer programming?

Question: Can you solve the "goat cabbage wolf" problem using integer programming. If so could I get an outline of the solution or a reference to one?
0
votes
1answer
29 views

Linear programming with kernel

Can anyone please help me with solving the constrained minimization problem below? $$\mathbf{x}^* = \arg\min \sum_{i=1}^m q_i e^{-2x_i} $$ $$s.t.$$ $$\sum_{i=1}^m x_i = c$$ $$x_i\geq0, i = ...
0
votes
2answers
45 views

Need a solution to a specific problem in integer programming, outlining a general solution or pointing me in a direction.

I just started studying linear programming and I have limited resources with which to work. I have to work on a number of exercises but the notes I have do not help much so I have to look online for ...
0
votes
1answer
25 views

What is the complementary slackness conditions for a primal dual pair?

I'm trying to understand what exactly the complementary slackness conditions for a primal dual pair is and how it's calculated. I understand that we have a given linear programming problem. And that ...
0
votes
1answer
40 views

Network flow as a linear/integer programming problem with special conditional constraints

Consider the classic network flow problem where the constraint is that the inflow to a vertex is equal to the sum of its outflows. Consider having a more specific constraint where the flow cannot be ...
0
votes
1answer
61 views

Math for optimal asset allocation given constraints (linear/quadratic programming?)

Say we have a set of mutual funds, with various characteristics. I'd like to run some maths and give back the ideal mixture of these funds to meet the users constraints, and I'm unsure of whether ...
0
votes
2answers
37 views

Linear programming problem using the simplex algorithm, dual problem… [closed]

I want to maximize $z = 12x + 20y$ with the following constraints: $$\eqalign{ & 2x + 8y \le 180 \cr & 4x + 4y \le 120 \cr & x,y \ge 0 \cr} $$ I need the simplex tableau to find ...
1
vote
1answer
42 views

Is this a proper alternative way for math model for TSP(Travelling Salesman Problem)?

I have never seen a model that uses indexing in any article.So I have decided to publish it to be sure. I think indexing model is more suitable for generaling the model than the subtour elimination ...
3
votes
1answer
23 views

How to create an example with exponential running time for a given implementation of the simplex algorithm?

Say I have a black box implementation of the simplex algorithm given. Even though the worst case complexity is exponential, the implementation is fast for all cases I have tried. Is there a ...
0
votes
1answer
25 views

MIP Solver with Sensitivity option

I need a MIP Solver with Sensitivity Analysis option. So far i have found LPSolve IDE, and it has Sensitivity Analysis, but it is not supported for Mixed Integer Programming, only for the decimals. ...
0
votes
1answer
48 views

Linear Programming Problem with odd objective function

I have the linear problem as it follows. I have 3 different types of devices. Type A, Type B, Type C. At any given moment, there is exactly one type of each device installed. So one device A, one ...
1
vote
0answers
24 views

Gauss-Seidel iterative method not converging

I'm trying to solve a linear system of linear equations using the Gauss-Seidel iterative method. I'm writing c code to do it for me since I have over 349 entries to solve. In other words, I have 349 ...
-1
votes
1answer
22 views

How can I derive the following Linear Programming

How can we derive the dual problem? max$_{x} v^{T} x$ subject to $w^{T} x \le W, 0 \le x_i \le 1 ( i=1,...,n )$ where $ v \in \Bbb {R}^{n}, w_i \in \Bbb {R}^{n} $ and $ W \in \Bbb {R} $