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

learn more… | top users | synonyms

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} ...
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 ...
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
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,...). ...
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 ...
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 ...
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 ...
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 ...
1
vote
1answer
105 views

How to use the simplex method for linear programs?

I believe to be missing something important in the Simplex algorithm, because I can't get it to work. From what I gather, there are three steps per iteration, given a matrix for a linear program in ...
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 ...
1
vote
0answers
85 views

Computing the Optimal Simplex Tableau for Linear Programming

I am learning in my class about computing the optimal simplex tableau. I learned that, if you have an initial basic feasible solution, you can apply a series of formulas to compute the optimal ...
0
votes
1answer
38 views

How to read Linear Program from an optimal tableau

Suppose we are given an optimal tableau and the objective function. How can we determine the RHS of constraints or if possible the constraint equations? For example consider the given tableau with ...
0
votes
1answer
48 views

Simplex method state after first phase

I'm implementing a simplex method solver for a standard problem $$ \begin{aligned} \operatorname{minimize} \qquad&c^T x\\ \operatorname{subjected to} \qquad&Ax = b\\ &x \geq 0\\ ...
0
votes
1answer
28 views

General question about new objective function W using the simplex method

In regards to the two-phase simplex method; When creating a new objective function that consists the sum of the constraint(s) with artificial variables, I am told that if the Min value of (wmin) w is ...
1
vote
1answer
74 views

Degeneracy in Simplex Algorithm

According to my understanding, Degeneracy in a linear optimization problem, occurs when the same extreme point of a bounded feasible region $X$ can be represented by more than one basis, that is not ...
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
121 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 ...
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
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 ...
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$ ...
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 ...
3
votes
1answer
110 views

Linear constraints to placing N queens on an N x N chessboard?

I'm trying to formulate the problem of placing N queens on an N x N chessboard such that no two queens share any row, column, or diagonal. I managed to define my decision variable as x[n][n], a ...
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 ...
1
vote
0answers
23 views

How do I show that the given matrix can be decomposed?

Suppose $P\subseteq\mathbb R^n$ is a polyhedron given by $m$ constraints $\langle a_i,x\rangle\leq b_i, i=1,2,...,m$ and let $w_1,w_2,...w_n$ be its vertices. Define $S=(s_{ij})$ by ...
2
votes
2answers
43 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
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
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 ...
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 ...
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 ...
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 ...
1
vote
1answer
1k views

Warehouse Location Problem as an integer progam instead of a mixed-integer program

Given a set of costumers $M = \{1, \dots , m \}$ and a set of of factories $N = \{1, \dots , n\}$ we have $c_{ij} \geq 0$ costs to deliver to costumer $i \in M$ from factory $j \in N$ $F_j \geq 0$ ...
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} $
1
vote
1answer
78 views

why S in SVD is a vector instead of a matrix?

I know that when applying SVD on a matrix (m * n) I should have these three outputs: ...
2
votes
0answers
28 views

Modeling Objective function using mixed integer programming formulation

I have the following objective function max 2x1 -2f(x2), where f(x2) = 3 if x2 = 0 and f(x2) = 2-5x2 if x2 > 0; can anyone help me formulate it using binary ...
0
votes
1answer
36 views

Travelling salesman problem as an integer linear program

So the travelling salesman problem is a problem wherein a salesman has to travel through all cities in a way that the total travelling distance is minimal. You can rewrite this as an integer linear ...
1
vote
1answer
79 views

What would be a linear program formulation of finding the maximum degree of a graph?

Also, what would be a possible interpretation of the dual of this linear program? My teacher mentioned that it'd be interesting to interpret the dual but neither can I formulate the problem as an LP ...
0
votes
0answers
19 views

Payout Percentage Calculation

I need an dynamic equation to calculate number of payouts and the associated %, The variables I have areas follows: Total Prize Money = $ Number of Participants = X Number of Winners = 20% of X ...
0
votes
1answer
29 views

Supremum over ellipsoid set

In Boyd's Convex Optimization Textbook, page 157, it is stated: $ \mathrm{sup}\{a_i^T x\; |\; a_i\in\mathcal{E}_i \} = \bar a_i^T x + \mathrm{sup}\{u^T P_i^T x\; |\; \lVert u \rVert_2 \leq 1 \} = ...
1
vote
1answer
29 views

Primal to Dual Linear Programming

I'm learning how to convert primal LP problems to dual, but not sure if I'm doing it correclty. primal: $$ \begin{align} maximize: \ \ \ \quad x_1 + 2x_2\qquad\quad \ \ \\ subject\ to:\ -2x_1 + x_2 + ...
0
votes
1answer
26 views

KKT Conditions for NLP [closed]

How may I state the KKT conditions for minimize $f(x) = ax^2$ subject to $Ax \leq b$, $x$ unrestricted?
0
votes
0answers
23 views

Why doesn't linear programs have analytical solutions?

In a lecture that briefly overviewed linear program, it was said that linear programs do not have analytical solutions Is that a succinct reason for why this is the case?