Questions tagged [linear-programming]

For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.

852 questions
Filter by
Sorted by
Tagged with
35 views

Method of calculating dual as best possible lower bound when primal is a maximization

A method I learned that feels more intuitive to calculate the dual is as follows: For a minimization problem in standard form: \begin{align} &\min &&f(x) \\ &\text{s.t.} \\ & &...
• 1
27 views

Plot modification for sensitivity analysis

Hello I have this result plot for my work. There the metric 'weight' is plotted as a function of the parameter $\alpha$, and this for different values of $\gamma$. These are the results of a MILP, ...
• 21
185 views

Will this large problem have a chance of being able to be solved?

I know this of course depends on the problem, but I want to know whether it is almost certainly impossible or not to solve my problem computationally with modern linear programming solvers before I ...
1 vote
65 views

I have a LP problem like: \begin{align} \min &\quad z = c^T x \\ s.t. &\quad Ax\le b \\ &\quad x\ge 0 \end{align} Assume the optimal solution of this problem is $x^*$ and the dual optimal ...
• 13
186 views

Conditional Constraint Formulation LP

I have a continuous variable $z, {-1 < z < 1},$ and a binary variable $w$. How do I write a conditional constraint which guarantees for $z < 0$, $w = 1$, and for $z \ge 0$, $w = 0$?
45 views

General questions concering column generation

I have a basic question about the Dantig-Wolfe reformulation. How do I know which constraints go into the master problem and which into the subproblem(s)? As I understand it, constraints that connect ...
1 vote
80 views

Modification of a switch binary variable

I have the following question. I have just read this question and was wondering if it is possible to extend this problem. I am interested in whether it is also possible to identify which machine is ...
• 91
65 views

Special Case of Minimum Cost Flow Problem with Variable Cost

I am working on an optimization problem similar to MCF with variable cost, but with an adjustment in the objective function. The cost function $f$ to minimize that is continuous, piece-wise linear and ...
41 views

How to get an extreme ray in CPLEX

I am trying to get an extreme ray in a Benders decomposition when the primal subproblem is infeasible (so, the dual is unbounded). CPLEX below propose some function but no one works. If you are using ...
1 vote
49 views

Can a cut be tight across a diagonal in a polytope?

Consider a polytope in $\mathbb{R}^n$ inside the unit cube given by $$A\vec{x} \le b \\ 0 \le x_i \le 1$$ And consider one particular row of $A$ that we consider as a cut $A_ix \le b_i$. I am ...
1 vote
268 views

Can LP be solved using the previous solution during branching?

I want to solve an integer linear programming problem using the branch-and-cut method, relaxing the original ILP problem to LP problem. If the LP solution contains a non-integer value of some variable ...
144 views

How to model an optimization problem with mutual exclusivity of two variables, without introducing integer variables?

Is it even possible to model an optimization problem with mutual exclusivity of two variables, without introducing integer variables? I am trying to formulate and solve an optimization problem in ...
• 31
69 views

Optimal way to formulate a piecewise linear function

I am working on LP problem whose objective function includes a piecewise linear function. I would like to figure out the optimal way to formulate the piecewise linear function in order to minimize the ...
87 views

Enforcing Order in a Linear Programming Question

I have an optimization model to fulfill the water requirements of a city's distribution network. The model includes water sources from rainfall collection, river extraction, reservoir storage, and ...
• 31
1 vote
48 views

Multi-Commodity Flow with "group edges"

I'm currently working on a special variation of the Multi-Commodity flow problem. My goal is to solve this variation via column generation, because the graph can become very large. Description Given......
• 13
1 vote
175 views

My Professor couldn't complete the model for this optimization problem. how do i model this problem?

(Edit: there was a slight translation error, to be clear, we tried this since the start with Binary variables (IP), even then we couldn't crack it) I'm an undergraduate in Industrial Engineering and ...
77 views

How to write conditional constraints and sum the result in Linear Programming in Python?

I want to use the sum of a series of linear expressions as objective and constraints. These linear expressions are chosen to be included or not based on some conditions. I can achieve it in Excel ...
• 13
1 vote
61 views

Integrality gap vs Gurobi Gap

I was wondering what the difference is between the integrality gap (i.e. best known solution in relation to the LP relaxation) and the gap from the MIP solver from Gurobi, for example. As I understand ...
• 21
55 views

Need help for the python scheduling code

I'm working on a Python application using PuLP for optimization, and I'm having trouble ensuring that only one material is produced on a given day. The constraint prob += pulp.lpSum(production_flag[m][...
1 vote
47 views

How to set up the master and subproblem

I have the following question. I have a classical scheduling model with the following constraints: Demand coverage One shift per day Minimum and maximum number of consecutive working days Forward ...
1k views

Multiple Travelling Salesmen - How to make the second slowest salesman matter?

I'm building a Mixed Integer Linear Program for a variant of TSP I'm dealing with, where there are multiple salesmen. The way I have formulated the problem is that each agent has a time variable $T_i$ ...
39 views

How to generate random bounded polytope by MATLAB defined by Ax=b, x≥0

How can one create a random bounded polytope in MATLAB, specified by the conditions $‎\lbrace‎x:~ Ax = b,~ x \geq 0‎\rbrace‎$
1 vote
77 views

Solve scheduling model using a greedy heurisitc

I have the following scheduling problem. Relatively simple and not very complex (only serves as an example). The indexes are $I$ worker, $T$ days and $J$ shift. The decision variable is $x_{ijt}$, ...
• 71
1 vote
81 views

Best approach to initialize column generation

I was wondering what the typical approaches are for generating an initial solution for the first column in a COlumn Generation approach and which usually work best and are easiest to implement (Gurobi)...
78 views

• 1,857
105 views

• 91
39 views

Scheduling categories of jobs with completion time requirements

Consider a discrete time slotted, system with two categories of jobs $J_1$ and $J_2$, where each job from the category $J_1$ has completion time requirement of $C_1$ and the jobs from category $J_2$ ...
• 917
1 vote
85 views

Schedule monotony constraints

Suppose I have a model for creating a nurse's duty roster. The model has the indices $i$ for the person, $t$ for the day and $s$ for the shift. I have the binary variable $x_{its}$ which indicates ...
1 vote
99 views

Knapsack problem - reducing the number of decision variables

I am trying to solve something similar to a knapsack problem: $$\max \sum v_{n}P_{n}$$ subject to some basic weight constraints. However, what makes this problem difficult to solve is that $P_{n}$ is ...
• 185
1 vote
91 views

Help modeling linear constraints

I have the following variables and indices. I have $y_{ijk} \in [0;1]$ which indicates how performant a machine $i$ is on day $j$ in the interval $k$. The binary variable $z_{ijk}$ indicates whether a ...
• 91
84 views

Single Machine Job Scheduling With Release Dates and No Idling Constraint

I'm trying to model a linear job scheduling optimisation problem. There is a single machine and N jobs $J_1, J_2, ..., J_N$. Each job consists of one step with processing time $p_1, p_2, ..., p_N$. ...
1 vote
57 views

Does getting the second optimal solution in a general MILP require solving a MILP again?

This general question popped into my mind if finding all optimal solutions takes not much more time than finding just one optimal solution in a MILP why not gettting all of them in Gurobi?
• 153
131 views

How to model the constraints of min and max in cvxpy

I have a continuous variable $x_{ij}\in[0,1]$ and I need to write the following constraint: $$M_i-m_i+1\leq C_i$$ where $M_i=\max\{j: x_{ij}>0\}$ and $m_i=\min\{j: x_{ij}>0\}$
• 403
1 vote
131 views

Graphical understanding of the primal and dual problem

I have a relatively simple question. Assuming we have a simple numerical example of an LP with two decision variables and two constraints (non-negativity excluded), how can I visualize the graphical ...
• 11
124 views

Deriving linear constraints from logical notation

I have the following two logical implications. $x_{it}$ and $y_{it}$ are binary, $N$ is an integer number. $i$ and $k$ are indexes. $$\sum_{k=1}^{t}x_{ik}\ge N~\implies y_{it}=1$$ \sum_{k=1}^{t}x_{...
309 views

Linear condition between two continuous variables

There are two real variables $x$ and $y$. The conditions are such that: if $y\le 0$, then $x=0$ if $y>0$, then $x=y$ How to write linear equations or inequalities to satisfy both the conditions?
• 41
105 views

How to model this constraint in a better way?

I have a resource allocation problem. There are $M$ users and $N$ resources (machines). One user can be assigned to multiple resources/machines. But maximum $B$ machines can be activated at a time for ...
• 2,397
1 vote