is a discipline to apply analytical methods for better decisions. It has many synonyms such as management science, decision science and system science.

learn more… | top users | synonyms

12
votes
3answers
267 views

When does a variable leave a basis (in linear programming)?

In the simplex algorithm in linear programming, what are conditions for a variable to leave a basis (not necessarily basis for the/an optimal solution)? I'm supposed to list as many sufficient and ...
1
vote
2answers
27 views

Shortest path in a graph with weighted edges and vertices

I am considering a problem of route planning (from a source $s$ to sink $t$) in a undirected graph with weighted edges and vertices. The goal is to find a shortest path between the source $s$ and the ...
1
vote
1answer
14 views

Tree-width of a quadratic pseudo-Boolean function

A pseudo-Boolean function $f : \mathbb{B}^n \mapsto \mathbb{R}$ is of the following form. $$ f \left(x_1, \ldots, x_n\right) = \sum_{S\subseteq V} c_S \prod_{j \in S} x_j $$ Here $c_S \in ...
3
votes
1answer
22 views

Transforming a $0$-$1$ knapsack problem into the standard form

I have the following $0$-$1$knapsack problem: $$\begin{align*} &\mathrm{Max} : \quad z= 3x_1 -4x_2+5x_3+7x_4-6x_5+x_6\\ & \mathrm{subject\ to}: -2x_1 +x_2 +10x_3 +3x_4 -5x_5+12x_6 \leq 4 ...
1
vote
1answer
3k views

simplex M-method minimization problem

Solve using the simplex method. Identify the solution of the dual in the final simplex tableau Minimize: $$z=12x_{1}+4x_{2}+2x_{3}$$ **Constraints:**$$ x_{i}\ge 0$$ $$-6x_{1}+3x_{2}\ge 9$$ ...
16
votes
2answers
177 views

Finding properties of operation defined by $x⊕y=\frac{1}{\frac{1}{x}+\frac{1}{y}}$? (“Reciprocal addition” common for parallel resistors)

I have recently found some interesting properties of the function/operation: $x⊕y = \frac{1}{\frac{1}{x}+\frac{1}{y}} = \frac{xy}{x+y}$ where $x,y\ne0$. and similarly, its inverse operation: $x⊖y = ...
1
vote
0answers
31 views

Transform an assignment problem to use the Hungarian algorithm

I have this assignement problem: There are three machines to perform four tasks. The costs of assigning to a machine each of the tasks are given by the following matrix: $$\begin{pmatrix} ...
5
votes
2answers
202 views

Convert a piecewise linear non-convex function into a linear optimisation problem.

Update: Problem and solution found here (p. 17, 61), although my prof's solution (formulation) is different. Convert $$\min z = f(x)$$ where $$f(x) = \left\{\begin{matrix} 1-x, ...
3
votes
1answer
801 views

Prove optimal solution to dual is not unique if optimal solution to the primal is degenerate and unique.

How do I prove an optimal solution to dual is not unique if an optimal solution to the primal is degenerate and unique? What I tried: Let the primal be $$\max z=cx$$ subject to $$Ax ...
0
votes
1answer
56 views

Setting up an LP problem on producing linear board in jumbo reels

I have to set up a linear programming problem corresponding to the following scenario: What I tried: I think we have 8 templates for 1 $68 \times l$ reel (or whatever): $22,22,22$ (66) ...
0
votes
0answers
8 views

Correct definition of the co-occurrence graph of a pseudo-Boolean function

In section 4.6 of Pseudo-Boolean Optimization, Boros and Hammer have defined the co-occurrence graph of a pseudo-Boolean function as follows. If a pseudo-Boolean function $f : \mathbb{B}^n \mapsto ...
1
vote
3answers
50 views

Mixed Integer Linear Programming Conditional Constraints

I have a set of variables: $x_1,x_2,x_3,x_4$ $x_1$ is a binary integer variable while the rest are real numbers all between 0 and 1 I want a constraint such that: if $x_2+x_3+x_4$>0 then $x_1=1$ ...
2
votes
1answer
554 views
1
vote
1answer
22 views

Is Pareto efficiency (Pareto Optimal) a part of Operation Research?

I know that Pareto efficiency (Pareto Optimal) is an economic concept that helps for multi-criteria decision making process. My doubt is whether any decision process is a part of Operation Research. ...
1
vote
0answers
50 views

Develop a model for determining the optimal production schedule in a manufacturing facility

I have to formulate (linearly) the following problem mathematically: What I tried: 1. Variables Let $x_{ijk} = 1$ if, in month k, product i should be made in production line j, where ...
0
votes
0answers
37 views

Weights in goal programming

I'm not quite convinced about assigning weights in goal programming. Here is an example formulation problem. What I tried: Let $x_j$ be the number of minutes for ad $j = R, T$ We want to ...
1
vote
0answers
32 views

Model linearly: Determine amount of units for production

A company produces 2 products in a week. Let $x_i$ denote the number of units of product $i$ to produce. Each product requires liters of Chemical X to make. Info is given below: ...
0
votes
0answers
26 views

If the primal is unbounded, then the dual is infeasible.

In the context of duality in linear programming, prove that If the primal is unbounded, then the dual is infeasible. My book says that this is a corollary to complementary slackness. What's ...
0
votes
0answers
51 views

What values make the solutions in the optimal? infeasible? degenerate? etc

Note that $c_i$'s in the $z_j-c_j$ row are not coefficients of the $x_i$'s. I use instead: $r_1, r_2, r_3$. I'm assuming there's a non-negativity constraint. we need to state necessary ...
1
vote
2answers
62 views

Find the optimal solution without going through the ERO's

All I got is that $$12y_1 + 7y_2 + 10y_3 = 2(0) + 4(10.4) + 3(0) + 1(0.4)$$ and $y_2 = 0$ because $x_6$ is in basis. How do I find $y_1$ and $y_3$ without going through the simplex method? I ...
6
votes
1answer
3k views

Linear Programming: Three variable graphical solution

A small bank offers three type of loans: housing loans at $8.50$% interest, education loans at $13.75$% interest rates, and loans to senior citizens at $12.25$% interest. Further, it needs to ...
2
votes
2answers
819 views

Introduction into Operations Research

I am a first year graduate student who advisor wants me to learn about operations research and to use stochastic integer programming in my research. He keeps giving me papers to read but they ...
0
votes
0answers
19 views

Are any tools or techniques available to solve the “placement of safety points” problem?

Definition 0. Given a metric space $X$ and subsets $H$ and $S$ thereof, define: $$d(H,S) = \sup_{h \in H} \inf_{s \in S}d(h,s)$$ Here's some extremely dodgy intuition. Imagine $S$ is a set of ...
2
votes
0answers
22 views

Linear programming: choosing entering variable

maximize 10𝑥1 + 12𝑥2 +12𝑥3 subject to 𝑥1 + 2𝑥2 + 2𝑥3 + 𝑥4= 20 2𝑥1 + 𝑥2 + 2𝑥3+𝑥5= 20 2𝑥1 + 2𝑥2 + 𝑥3 +𝑥6= 20 𝑥1, … , 𝑥6 ≥ 0 This is my first step for simplex tableau x1 x2 ...
2
votes
0answers
170 views

Prove an artificial variable that leaves the basis will never return.

This is in the context of the Big M Method in the simplex algorithm in linear programming. Prove an artificial variable that leaves the basis will never return. I have no idea how to start this. ...
0
votes
1answer
53 views

Max $z = x_1(1-x_2)x_3$ s.t. $x_1 - x_2 + x_3 \le 1$

Using dynamic programming, Maximise $$z = x_1(1-x_2)x_3$$ subject to $$x_1 - x_2 + x_3 \le 1$$ $$x_1, x_2, x_3 \ge 0$$ Here's the outline of my solution 1. How is it? Let ...
1
vote
0answers
460 views

How do I convert max min problem into a linear programming problem?

Let $A$ be a given $m \times n$ matrix, $c$ a given $n$-vector, and $b$ a given $m$-vector. Show that this problem $$\max \min (c^T x - y^T Ax + b^Ty) \text{ such that } x,y \ge 0$$ can be reduced ...
0
votes
2answers
22 views

Simulation methods and generating random variables

Twenty aircraft are sent to bomb a target that is rectangular in shape. It has dimensions 150m by 50m. Each aircraft makes a bombing run along the horizontal x axis and drops one bomb. The point ...
1
vote
1answer
19 views

Is Graph with multiple-inputs and multiple-outputs called MIMO?

MIMO (systems with multiple-inputs and multiple-outputs) is a term in engineering areas and applied mathematics such as process-control and wireless communication. Suppose you have a directed graph ...
0
votes
1answer
424 views

Edge weight function for graph instance of scheduling and allocation problem

I have difficulties developing a proper (non-scalar) edge cost function $c_e$ for my resource scheduling problem, which I mapped into a graph problem. Processes $P_i$ need resources $R_i \in ...
1
vote
0answers
75 views

What programs or websites solve linear integer or goal programming problems?

I don't think I can use Excel. My solver doesn't work so I can't even use Excel for regular linear programming. Something like this but for integer or goal programming. This seems to allow integer ...
0
votes
1answer
35 views

Dependence of the derivative of a pseudo-Boolean function on its variables

I am going through Pseudo-Boolean optimization by Boros et al. In the section 2, the paper introduces the idea of derivative and residual of a peudo-Boolean function. It is claimed that both ...
0
votes
0answers
22 views

Travelling Salesman Variation

Is there a name for this variation and a recommended algorithm for solving this problem: You have a large boat with many leaks on it. As soon as you patch a leak, it resets, and slowly begins ...
2
votes
0answers
51 views

How to model task scheduling with constraints

I am trying to model a task scheduling with constraints, in order to understand which model or algorithm is better suited to compute an optimal solution. Suppose I have $n$ jobs with CPU loads ...
0
votes
0answers
15 views

Linear programming exercise verification

I am working on this exercise (translation mine): A Motel provides a 24 hour service and needs a minimum number of workers depending on the time slot: ...
0
votes
0answers
20 views

How to find extreme directions?

objective:min $−3x_1−2x_2−x_3$ The set is : $X=\lbrace (x_1,x_2,x_3):2x_1+x_2-x_3\le2; x_1,x_2,x_3\ge0 \rbrace$ Attempt: $2d_1+d_2-d_3\le0$ (a) $d_1+d_2+d_3=1$ and $d_1,d_2,d_3\ge0$ Since from ...
0
votes
0answers
25 views

Need optimal tableaus be unique assuming unique solution?

If so, why? If not, do they differ by some ERO/s? That is, they are row equivalent? This is the problem (taken from Chapter 2 here): My classmate gave an optimal tableau that is different ...
0
votes
0answers
6 views

Parallel series systems defined in OR? Isomorphism to SP-graphs in graph theory?

The series parallel graph definition is inductive with respect to series operation and parallel operation in graph theory. In comparison to series parallel systems in OR (Operations Research) and ...
0
votes
1answer
38 views

Convert non-linear into linear

What I tried: Let $$u_1 = x_1^3$$ $$u_2 = x_2 x_3$$ $$u_3 = x_3^3$$ Then we have $z = u_1 + u_2 + u _3$ s.t. $1 \le u_3 \le 343$ $u_3^{1/3}$ should be integer $u_1 \in \{0, 1\}$ $u_2 \in ...
0
votes
2answers
73 views

How do I go about splitting up 1 LP problem into 2?

I have to set up a linear programming problem corresponding to the following scenario: From Chapter 2 here.
0
votes
1answer
47 views

Interpreting optimal tableau in manufacturing

What I tried: 3a1 Make $c_3$ greater than the current $z_3$ so any value greater than 20/3? 3a2 I just do EROs to make the $x_3$ column into $[0, 0, 1]^T$ ? 3b $c_1 \ge 10$? idk 3c ...
0
votes
1answer
74 views

LP problem involving producing assemblies

I have to construct an LP problem based on the ff scenario that might be similar to a scenario in another question (in the sense that I felt the need to use $mod$): The productivities are ...
0
votes
0answers
22 views

RINS: start - incumbent and relaxation solution have all different values

RINS: Relaxation induced neighborhood search; introduced by Danna et.al in 2010 this paper. I wanted to design an example how the RINS algorithm works to make sure that I have it completly understood ...
1
vote
0answers
38 views

Strict inequalities in an LP problem

So I have to formulate an LP problem out of this scenario converting 3 variables into just 2 variables in order to use the graphical method. I guess I do that by using the demand constraint: I ...
0
votes
0answers
28 views

Use graphical analysis to solve a parameterised LP problem

For $c < 0$, we have no feasible solutions and hence no optimal solutions. For $c=0$, our only feasible solution is $z=0$ obtained by $(0,0)$. For $c > 0$, well... I graphed the ...
2
votes
1answer
54 views

How does one use the 'input/hr' column in the table below in setting up the problem?

I have to set up a linear programming problem corresponding to the following scenario: If my understanding of the problem is correct, I use $mod$: Let $i$ be $A$ or $B$. Let $x$ be amount ...
1
vote
1answer
38 views

Assigning 2 Tasks to each Agent w/ Hungarian Algorithm?

Suppose I have 4 agents and 8 tasks and I would like to assign each agent 2 tasks each. Is there a way to use the Hungarian Algorithm to solve this problem? I worked it out with 2 agents and 4 tasks ...
2
votes
1answer
26 views

Check that a Nash equilibrium point is given by $\left(0,\frac {1} {2}, \frac {1} {2}\right)$ $\left(0,\frac {1} {2}, \frac {1} {2}\right)$

Given the game matrix \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 0 \\ 1 & 0 & 2 \end{bmatrix} I already see a Nash equilibrium in pure strategies, which is $a_{11}$, ...
0
votes
0answers
22 views

Find a Nash Equilibrium point in mixed strategies using the simplex algorithm

Here is the game matrix A. First I note that $C_4<C_1$ and $C_4 <C_3$ So I can remove $C_1 $ and $C_3$ since they are dominated strategies. Then considering only $C_2,C_4$, I note that $R_3$ ...
1
vote
1answer
53 views

Are my constraints in this LP problem correct? Any redundant?

I have to set up an LP problem based on the situation below: What I tried: Let $b_i$ denote sacks bought at month i (i=1,2,3) Let $s_i$ denote sacks sold at month i (i=2,3,4) We want to ...